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
Hint 1
Walk the bits from the bottom, comparing each with the previous one.
Hint 2
A slicker test:
n ^ (n >> 1)is all 1s exactly when the bits alternate.Hint 3
And a value
xis all 1s exactly whenx & (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
- Compute
x = n ^ (n >> 1). - 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) == 0Java
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