Binary Number with Alternating Bits

Easy
429.

Binary Number with Alternating Bits

Binary Number with Alternating Bits is an easy coding problem on bit manipulation, asked in Amazon, Adobe and Yahoo interviews.

Given a positive integer n, return true if its binary representation has strictly alternating bits — no two adjacent bits are the same.

Example 1

Input
n = 5
Output
true
Explanation
101 alternates.

Example 2

Input
n = 7
Output
false
Explanation
111 does not.

Example 3

Input
n = 11
Output
false

Constraints

  • 1 <= n <= 2147483647
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {boolean}
 */
var hasAlternatingBits = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary Number with Alternating Bits — Problem & Solution

Binary Number with Alternating Bits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Binary Number with Alternating Bits is an easy coding problem on bit manipulation, asked in Amazon, Adobe and Yahoo interviews.

  • Difficulty: Easy
  • Topics: Bit Manipulation
  • Asked at: Amazon, Adobe, Yahoo
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a positive integer n, return true if its binary representation has strictly alternating bits — no two adjacent bits are the same.

Example 1

Input: n = 5
Output: true
Explanation: 101 alternates.

Example 2

Input: n = 7
Output: false
Explanation: 111 does not.

Example 3

Input: n = 11
Output: false

Constraints

  • 1 <= n <= 2147483647

Hints for Binary Number with Alternating Bits

  1. Hint 1

    Walk the bits from the bottom, comparing each with the previous one.

  2. Hint 2

    A slicker test: n ^ (n >> 1) is all 1s exactly when the bits alternate.

  3. Hint 3

    And a value x is all 1s exactly when x & (x + 1) == 0.

How to solve Binary Number with Alternating Bits

n ^ (n >> 1) is all ones exactly when the bits alternate, and x is all ones exactly when x & (x + 1) == 0.

Approach

  1. Compute x = n ^ (n >> 1).
  2. Return x & (x + 1) == 0.

Why it works

Adjacent bits differ everywhere iff every bit of n differs from the one below it, which the shifted XOR tests; adding one to an all-ones value carries out completely, leaving zero overlap.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • A bit-by-bit loop comparing each bit with the previous is the readable alternative.

Reference solution

Python

def hasAlternatingBits(n: int) -> bool:
    x = n ^ (n >> 1)
    return x & (x + 1) == 0

Java

public static boolean hasAlternatingBits(int n) {
    long x = (long) n ^ ((long) n >> 1);
    return (x & (x + 1)) == 0;
}

C++

bool hasAlternatingBits(int n) {
    long long x = (long long) n ^ ((long long) n >> 1);
    return (x & (x + 1)) == 0;
}

JavaScript

var hasAlternatingBits = function(n) {
    let v = n;
    let prev = v % 2;
    v = Math.floor(v / 2);
    while (v > 0) {
        const cur = v % 2;
        if (cur === prev) return false;
        prev = cur;
        v = Math.floor(v / 2);
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 146 bit manipulation problems · the whole catalogue

Learn the technique: Bit Manipulation