Alternating Bit
Solve this Problem
Given a positive integer
n, determine whether its binary representation has strictly alternating bits — no two adjacent bits are ever the same.
Comparing each bit to the one before it works directly, but there's a shortcut: XOR-ing n with itself shifted right by one bit turns every "differs from its neighbor" position into a 1. If the original bits truly alternated everywhere, that XOR result is a solid run of 1s from the lowest bit up — a pattern that AND-ed with its own successor (x & (x + 1)) collapses to 0, the same identity used earlier to test for an all-ones run.
Test Case 1:
Input:n = 5
Output:true
Explanation:5 = 101 — bits alternate cleanly between 1 and 0.
Test Case 2:
Input:n = 7
Output:false
Explanation:7 = 111 — the two rightmost bits are both 1, breaking the pattern.
Test Case 3:
Input:n = 10
Output:true
Explanation:10 = 1010 — alternates starting from 0.
Constraints
- ◆
1 ≤ n ≤ 2³¹ − 1
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Compare Adjacent Bits
BrutePull off the lowest bit, shift it away, and compare the next lowest bit against the one before it — every adjacent pair must differ for the whole number to qualify.
Time
O(log n)Space
O(1)Java
1class Solution {
2 public boolean hasAlternatingBits(int n) {
3 int prev = n & 1;
4 n >>>= 1;
5 while (n > 0) {
6 int cur = n & 1;
7 if (cur == prev) {
8 return false;
9 }
10 prev = cur;
11 n >>>= 1;
12 }
13 return true;
14 }
15}Optimal — XOR Shift Trick
OptimalXOR-ing n with itself shifted right by one bit turns every "differs from its neighbor" position into a 1. If the original bits truly alternated everywhere, that XOR result is a solid run of 1s from the lowest bit up — the same all-ones pattern tested earlier with x & (x + 1), which collapses to 0 exactly when x is that kind of run.
Time
O(1)Space
O(1)Java
1class Solution {
2 public boolean hasAlternatingBits(int n) {
3 int x = n ^ (n >>> 1);
4 return (x & (x + 1)) == 0;
5 }
6}