693. Binary Number with Alternating Bits

EasyView on LeetCode

Bit Manipulation

Time: O(1)

Space: O(1)

Problem Overview

Check if binary representation alternates 0s and 1s.

Intuition

Check if binary representation alternates 0s and 1s. n XOR (n>>1) should be all 1s (2^k - 1 for some k).

Algorithm

1Compute m = n XOR (n >> 1).
2Check if m is of form 2^k - 1 (all 1s in binary): (m & (m+1)) == 0.

Example Walkthrough

Input: n=5 (101)

1.5 XOR 2 = 7 (111).
2.7 & 8 = 0 ?.

Output: true

Common Pitfalls

•This works because alternating bits XOR with their neighbor (shift right) produces all 1s.

693.cs

// Approach: XOR n with n>>2; if the result has exactly one set bit
// (is a power of two or 1), the bits alternate.
// Time: O(1) Space: O(1)

public class Solution
{
    public bool HasAlternatingBits(int n)
    {
        //            n = 0b010101
        //       n >> 2 = 0b000101
        // n ^ (n >> 2) = 0b010000 = a
        //        a - 1 = 0b001111
        //  a & (a - 1) = 0
        int a = n ^ (n >> 2);
        return (a & (a - 1)) == 0;
    }
}

Was this solution helpful?