Log inSign up
easyLeetCodeNot Started

Check if Number Has Alternating Bits

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

Given a positive integer n, check whether two adjacent bits in its binary representation always have different values.

Return true if every pair of adjacent bits consists of alternating values (0 and 1), or false otherwise.

Example 1 · Example 1: Alternating Pattern:

Input: n = 5
Output: true
Explanation: The binary representation of 5 is 101. Adjacent bits alternate (1 -> 0 -> 1).

Example 2 · Example 2: Consecutive Identical Bits:

Input: n = 7
Output: false
Explanation: The binary representation of 7 is 111. Bits at positions 0 and 1 are both 1, so they do not alternate.

Example 3 · Example 3: Alternating Even Pattern:

Input: n = 11
Output: false
Explanation: The binary representation of 11 is 1011. The last two bits are both 1.

Constraints:

  • 1 <= n <= 231 - 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Identify how self-shifted bitwise operations expose structural symmetries.
  • Recognize the all-ones bitmask property: m & (m + 1) == 0.
  • Safely handle 32-bit integer overflow during bit additions across multiple languages.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Asking if adjacent bits alternate (never 00 or 11).
  • Binary parity properties across shifted views of the same integer.

Algorithmic Decision Tree:

  • Calculate m = n ^ (n >> 1).
  • Verify m is of the form 2k - 1 by testing (m & (m + 1)) == 0.

Connected Patterns:

Power of TwoCounting BitsHamming Distance

1. Binary String Inspection

Intuition

Format the integer into a binary string. Loop through index 1 to length - 1. If s[i] == s[i - 1], return false. If loop finishes with no violations, return true.

When to apply: Prototype validation or quick checks where speed is non-critical.

Algorithm

  1. Step 1: Convert n to binary string.
  2. Step 2: Loop i from 1 to length - 1.
  3. Step 3: If string[i] == string[i - 1], return false.
  4. Step 4: Return true if all adjacent pairs alternate.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <bitset>
4
5using namespace std;
6
7bool hasAlternatingBitsBrute(int n) {
8 string s = "";
9 while (n > 0) {
10 s += (n % 2 == 0 ? '0' : '1');
11 n /= 2;
12 }
13 for (int i = 1; i < (int)s.length(); ++i) {
14 if (s[i] == s[i - 1]) return false;
15 }
16 return true;
17}
18
19int main() {
20 cout << boolalpha;
21 cout << "Brute (5): " << hasAlternatingBitsBrute(5) << endl; // true
22 cout << "Brute (7): " << hasAlternatingBitsBrute(7) << endl; // false
23 cout << "Brute (11): " << hasAlternatingBitsBrute(11) << endl; // false
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(log n)
  • Space complexity: O(log n)

2. Iterative Bit Shifting

Intuition

Initialize lastBit = n & 1. Right-shift n >>= 1. In a loop while n > 0, extract currBit = n & 1. If currBit == lastBit, return false. Update lastBit = currBit and shift n >>= 1. Return true when n reaches 0.

When to apply: When string conversions are disallowed and constant space is required.

Algorithm

  1. Step 1: Set lastBit = n & 1, and n >>= 1.
  2. Step 2: Loop while n > 0.
  3. Step 3: currBit = n & 1. If currBit == lastBit, return false.
  4. Step 4: Update lastBit = currBit, n >>= 1.
  5. Step 5: Return true if all bits alternated.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5bool hasAlternatingBitsIterative(int n) {
6 int lastBit = n & 1;
7 n >>= 1;
8 while (n > 0) {
9 int currBit = n & 1;
10 if (currBit == lastBit) return false;
11 lastBit = currBit;
12 n >>= 1;
13 }
14 return true;
15}
16
17int main() {
18 cout << boolalpha;
19 cout << "Better (5): " << hasAlternatingBitsIterative(5) << endl; // true
20 cout << "Better (7): " << hasAlternatingBitsIterative(7) << endl; // false
21 return 0;
22}

Time & Space Complexity

  • Time complexity: O(log n)
  • Space complexity: O(1)

3. XOR All-Ones Bit Trick

Intuition

If adjacent bits strictly alternate, then shifting n right by 1 creates the exact binary complement for every bit position. XORing n with n >> 1 flips every bit up to the most significant bit to 1. An integer m made entirely of 1s in binary (e.g. 111...1) plus 1 yields a power of two 1000...0. Thus (m & (m + 1)) == 0. To prevent 32-bit overflow when m = 2^31 - 1, we use a 64-bit integer type (unsigned long long or long).

When to apply: Optimal for production and competitive programming: branchless O(1).

Algorithm

  1. Step 1: Cast n to 64-bit long.
  2. Step 2: Compute m = n ^ (n >> 1).
  3. Step 3: Return (m & (m + 1)) == 0.

XOR All-Ones Trace for n = 5

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Compute n >> 1
Visual state
Values and pointers at this exact step
pointers
S
101
010
0
↑ operands
1
Check / comparison
n = 101, n >> 1 = 010
Decision / next transition
Opposite bits at every index position.
Why this step matters

Step 1: Compute n >> 1. 5 >> 1 = 2 (binary 010).

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 bool hasAlternatingBits(int n) {
8 long long m = (long long)n ^ ((long long)n >> 1);
9 return (m & (m + 1)) == 0;
10 }
11};
12
13int main() {
14 Solution sol;
15 cout << boolalpha;
16 cout << "Optimal (5): " << sol.hasAlternatingBits(5) << endl; // true
17 cout << "Optimal (7): " << sol.hasAlternatingBits(7) << endl; // false
18 cout << "Optimal (10): " << sol.hasAlternatingBits(10) << endl; // true
19 return 0;
20}

Time & Space Complexity

  • Time complexity: O(1)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — String ConversionO(log n)O(log n)Convert n to binary string representation, iterate through characters and compare s[i] == s[i-1].String allocation and traversal.
2.Better — Iterative Bit ShiftingO(log n)O(1)Extract the lowest bit with n & 1, shift right, and verify subsequent bit differs until n is 0.Sequential bit-by-bit checking.
3.Optimal — XOR Self-Shift TrickOptimalO(1)O(1)Compute m = n ^ (n >> 1), then test whether m & (m + 1) == 0.Single arithmetic bitwise validation.

Common Pitfalls & Crucial Edge Cases

32-bit integer overflow

If x has 31 ones (i.e. INT_MAX), x + 1 overflows a signed 32-bit integer. Cast to long or use unsigned types.

Confusing `x & (x + 1)` with `x & (x - 1)`

x & (x - 1) tests if x is a power of 2, whereas x & (x + 1) tests if x is all 1s.

Operator precedence

In C++/Java/JS, + has higher precedence than &. Always write (x & (x + 1)) == 0 with full parentheses.

Crucial Edge Cases to Validate:

  • n = 1 (binary 1) — Single bit has no adjacent conflicting neighbor; valid alternating bits.
  • n = 2 (binary 10) — Alternates 1 and 0; returns true.
  • n = 3 (binary 11) — Two consecutive 1s; returns false.
  • Large 32-bit values near 2^31 - 1 — When checking x + 1, 32-bit signed integers can overflow. Use unsigned arithmetic or 64-bit casting.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Show how you progress from the intuitive simulation (checking (n & 1) != ((n >> 1) & 1) in a loop) to the math trick (n ^ (n >> 1)).
  2. Highlight edge cases like signed integer overflow when computing x + 1.
  3. Discuss why bitwise solutions are preferred over string-based formatting due to zero memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What happens when you compute x = n ^ (n >> 1) for a number with strictly alternating bits?

2.How can you check if an integer x consists entirely of set bits (all 1s) in O(1) time?

3.What is the time complexity of the bitwise arithmetic solution for alternating bits?

Back to DSA Sheet