# C++ power of 2, regex, recursive, and iterative solutions

• Solution 0: power of 2. If n contains alternating bits, then n+(n>>1) contains a contiguous chunk of 1s. For example 21=16+4+1=10101, and 21+(21>>1)=31=11111. 31+1=32=100000. And 32 is a power of 2, so return true.

``````class Solution {
public:
bool hasAlternatingBits(int n) {
n+=(n>>1)+1;
return (n&(n-1))==0;
}
};
``````

Solution 1: regular expression ( C++ version of @2499370956's Java solution )

``````class Solution {
public:
bool hasAlternatingBits(int n) {
return regex_match(bitset<32>(n).to_string(),regex("(0)*(10)*1{0,1}"));
}
};
``````

Solution 2: recursion, keeping track of the last right-most bit

``````class Solution {
public:
bool hasAlternatingBits(int n) {
bool last=(n&1);
return n==0 ? false : helper(n,!last);
}

bool helper(int n, bool last){
return n==0 ? last==true : (n&1)==last ? false : helper(n>>1,!last);
}

};
``````

Solution 3: iterative loop

``````class Solution {
public:
bool hasAlternatingBits(int n) {
if (n==0) return false;
bool last=n&1;
while(n>>=1 > 0){
if ((n&1)==last) return false;
last=!last;
}
return true;
}
};
``````
``````class Solution {
public:
bool hasAlternatingBits(int n) {
while(n){
if ((n&1)==((n&2)>>1)) return false;
n>>=1;
}
return true;
}
};
``````

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