LeetCode 693 - Binary Number with Alternating Bits

https://leetcode.com/problems/binary-number-with-alternating-bits/description/

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

Example 1:

Input: 5
Output: True
Explanation:
The binary representation of 5 is: 101

Example 2:

Input: 7
Output: False
Explanation:
The binary representation of 7 is: 111.

Example 3:

Input: 11
Output: False
Explanation:
The binary representation of 11 is: 1011.

Example 4:

Input: 10
Output: True
Explanation:
The binary representation of 10 is: 1010.

https://leetcode.com/problems/binary-number-with-alternating-bits/discuss/108427/Oneliners-(C%2B%2B-Java-Ruby-Python)

Solution 1 - Cancel Bits

bool hasAlternatingBits(int n) {
    return !((n ^= n/4) & n-1);
}

Xor the number with itself shifted right twice and check whether everything after the leading 1-bit became/stayed 0. Xor is 0 iff the bits are equal, so we get 0-bits iff the pair of leading 1-bit and the 0-bit in front of it are repeated until the end.

    000101010
  ^ 000001010
  = 000100000

Solution 2 - Complete Bits

bool hasAlternatingBits(int n) {
    return !((n ^= n/2) & n+1);
}

Xor the number with itself shifted right once and check whether everything after the leading 1-bit became/stayed 1. Xor is 1 iff the bits differ, so we get 1-bits iff starting with the leading 1-bit, the bits alternate between 1 and 0.

    000101010
  ^ 000010101
  = 000111111

Solution 3 - Positive RegEx

public boolean hasAlternatingBits(int n) {
    return Integer.toBinaryString(n).matches("(10)*1?");
}

It's simple to describe with a regular expression.

Solution 4 - Negative RegEx

def has_alternating_bits(n)
  n.to_s(2) !~ /00|11/
end

It's even simpler to describe what we don't want: two zeros or ones in a row.

Solution 5 - Negative String

def hasAlternatingBits(self, n):
    return '00' not in bin(n) and '11' not in bin(n)

Same as before, just not using regex.

Solution 6 - Golfed

def has_alternating_bits(n)
  (n^=n/2)&n+1<1
end

Solution 7 - Recursion

def has_alternating_bits(n)
  n < 3 || n%2 != n/2%2 && has_alternating_bits(n/2)
end

Compare the last two bits and recurse with the last bit shifted out.

Solution 8 - Complete Bits + RegEx

public boolean hasAlternatingBits(int n) {
    return Integer.toBinaryString(n ^ n/2).matches("1+");
}

• Time Complexity: $O(1)$. For arbitrary inputs, we do $O(w)$ work, where $w$ is the number of bits in n. However, $w \leq 32$.
• Space complexity: $O(1)$, or alternatively $O(w)$.

    public boolean hasAlternatingBits(int n) {
        String bits = Integer.toBinaryString(n);
        for (int i = 0; i < bits.length() - 1; i++) {
            if (bits.charAt(i) == bits.charAt(i+1)) {
                return false;
            }
        }
        return true;
    }

https://leetcode.com/problems/binary-number-with-alternating-bits/discuss/113933/Java-super-simple-explanation-with-inline-example

    public boolean hasAlternatingBits(int n) {
        int cur = 0, pre = -1;
        while(n != 0) {
            cur = n & 1;
            if(cur == pre) return false;
            n >>>= 1;
            pre = cur;
        }
        return true;
    }

Approach #2: Divide By Two [Accepted]

We can get the last bit and the rest of the bits via n % 2 and n // 2 operations. Let's remember cur, the last bit of n. If the last bit ever equals the last bit of the remaining, then two adjacent bits have the same value, and the answer is False. Otherwise, the answer is True.

Also note that instead of n % 2 and n // 2, we could have used operators n & 1 and n >>= 1 instead.

Time Complexity: $O(1)$. For arbitrary inputs, we do $O(w)$ work, where $w$ is the number of bits in n. However, $w \leq 32$.

    public boolean hasAlternatingBits(int n) {
        int cur = n % 2;
        n /= 2;
        while (n > 0) {
            if (cur == n % 2) return false;
            cur = n % 2;
            n /= 2;
        }
        return true;
    }