Binary Number with Alternating Bits

Problem

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

Constraints

• 1 <= n <= 231 - 1

Solution

The problem Binary Number with Alternating Bits can be solved using the characteristic of alternating bits. If an integer has alternating bits 101010..., then by right shifting it by 1 would yield 010101... and adding them together would result in 111111.... In other words, if an integer n is comprised of alternating bits, n + (n >> 1) would result in 2x-1. Therefore, by checking if the operation returns 2x-1, we can find whether or not the given number has alternating bits.

Implementation

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