# Oneliners (C++, 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+");
}``````

• Love your negative regex solution!

• Here is my stab on this problem

In either n^(n<<1) or n^(n>>1) should set all bits set from most significant bit onwards. Adding 1 to it makes it power of 2

``````class Solution(object):
def hasAlternatingBits(self, n):
"""
:type n: int
:rtype: bool
"""

aux = 0
if n & 1:
aux = ( n ^ (n<<1) ) + 1
else:
aux = ( n ^ (n>>1) ) + 1

return aux & (aux-1) == 0
``````

• All your solutions are a BIT too short.

I'm glad even I came up with xor toggle solution :D

``````public boolean hasAlternatingBits(int n) {
int prev = n & (1);
n >>= 1;
while(n > 0) {
if(((n & 1) ^ prev) == 0) return false;
prev = n & 1;
n >>= 1;
}
return true;
}``````

• ((n ^= n/4) & n-1);

I think !((n ^= n/4) & n-1) is undefined behavior. I would rather split it in two statements:
n ^= n >> 2;
return !(n & (n - 1));

• Love your negative regex solution!

It's actually my favorite. So simple. And in Ruby it has the advantage that `!~` already gives me a boolean, whereas `=~` gives me an index or `nil`, which I'd then have to convert to boolean myself.

• ((n ^= n/4) & n-1);

I think !((n ^= n/4) & n-1) is undefined behavior. I would rather split it in two statements:
n ^= n >> 2;
return !(n & (n - 1));

Yeah, I think you're right. I probably should've used a language where it's not undefined :-)

• I've been coding from 5-6 years and all your solutions look like a different language all together.. You're great...

• Nice! Gheez, so simple, wow.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.