# Binary Number with Alternating Bits

• If a number is alternative,we can shift it one bit,mark this new number as m.
If you check m and n,you will find every bit of m is different from n in the corresponding bit.
So xor operation come .
x=n^(n>>1)
If n is alternative number,x will be like 001111. That's to say ,x ends with several 1s.
To verify whether x is ends with multi 1s,we can use the following code.
ans=(x+1)&x
return ans==0

• /* Slow and intuitive solution
class Solution {
public:
bool hasAlternatingBits(int n) {
vector<int> bits;
while(n) {
int r = n % 2;
n = n / 2;
bits.push_back(r);
}

``````    bool res = true;
for (int i = 0; i < bits.size() - 1; i++)
res = res && bits[i] ^ bits[i + 1];

return res;
}
``````

};
/*

/* Smart solution. Using the fact that if n is a alternating number then
n + (n >> 1) is all 1s, and n + (n >> 1) + 1 should be power of 2. And
since we know, any number that is a power of two, have an attribute which
is n & (n - 1) is 0. We just need to check that. */
class Solution {
public:
bool hasAlternatingBits(int n) {
long po2 = (long) n + (n >> 1) + 1; // the force conversion before n is mandatory, otherwise, it may overflow integer.
return (po2 & (po2 - 1)) == 0;
}
};

• You missed the best one!

``````function bitSolution(number){
//      10101010101
//  +    1010101010    ( number >> 1 )
//  ---------------
//  =   11111111111
//  &  100000000000
//  ---------------
//  =             0    ( power of two )
let tmp = ( number >> 1 ) + number;
return (tmp & tmp + 1) === 0;
}
``````

• ``````public boolean hasAlternatingBits(int n) {
int previous = 2;
while(n != 0){
if(previous == n%2){
return false;
}else{
previous = n%2;
n = n >> 1;
}
}
return true;
}``````

• My divide by 4 method:

``````class Solution(object):
def hasAlternatingBits(self, n):
if not n%2: #s.t. 101010 becomes 10101, note 10100 doesn't become 101
n//=2 #n/=2 for Python 2
while n: #check for 1010...01 pattern
if n%4!=1:
return False
n//=4 #n/=4 for Python 2
return True
``````

Should be a bit faster than the divide by 2 method

• @mui That's not faster but infinitely slower. Gets Time Limit Exceeded. (edit: got fixed now)

• @tony407 had the exact same sol.

int m1 = n ^ (n >> 1);

``````int m2 = m1 + 1;

if((m1 & m2) == 0)
return true;
else
return false;``````

• ``````    boolean isAlternatingBits(int a) {
return (a & (a >> 1)) == 0;
}
``````

• public boolean hasAlternatingBits(int n) {
String binaryString = Integer.toBinaryString(n);
if(!binaryString.contains("00") && !binaryString.contains("11")) {
return true;
}else {
return false;
}
}

• class Solution {
public:
bool hasAlternatingBits(int n) {
long m = n << 1;
m ^= n;
return (m & (m+1)) == 0 || (m & (m + 2)) == 0;
}
};

• private static boolean solution(int key){
if(((byte)(key % 2)^(byte)((key/2)%2))==0) return false;
else solution(key/2);
return true;
}

• C++ solution:

``````class Solution {
public:
bool hasAlternatingBits(int n) {
vector<int> vec;
while(n)
{
int nbit = n & 0x01;
if(vec.size() >= 1)
{
if(nbit ^ vec[vec.size() - 1] == 0)
return false;
}
vec.push_back(nbit);
n >>= 1;
}
return true;
}
};
``````

• class Solution:
def hasAlternatingBits(self, n):
"""
:type n: int
:rtype: bool
"""
return True if n^int(n/2) == 2**len(bin(n)[2:]) -1 else False

indentation problem (fixed in the original post)

• Python in One line:
return not('0' in bin(n)[2:][::2] or '1' in bin(n)[2:][1::2])

• A RegExp solution:

``````return /^0?(10)*1?\$/.test(input)
``````

• public boolean hasAlternatingBits(int n) {
int decider = (n ^ (n >> 1));

``````    if((decider & (decider+1)) == 0) {
return true;
} else {
return false;
}
}``````

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

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

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