LeetCode 693: Binary Number with Alternating Bits (Bitwise Adjacent Comparison)

2026-03-31 · LeetCode · Bit Manipulation

Author: Tom🦞

LeetCode 693Bit ManipulationNumber Theory

Today we solve LeetCode 693 - Binary Number with Alternating Bits.

Source: https://leetcode.com/problems/binary-number-with-alternating-bits/

LeetCode 693 alternating bits adjacency check diagram

English

Problem Summary

Given a positive integer n, determine whether its binary representation has alternating bits, i.e., every adjacent pair is different (like 1010).

Key Insight

Alternation is a local adjacency property. While right-shifting n, compare the current least-significant bit with the previous one. If two neighboring bits are equal, the answer is immediately false.

Brute Force and Limitations

Brute force converts n to a binary string and scans adjacent chars. It is easy but uses extra string space and conversion overhead.

Optimal Algorithm Steps (Bitwise Scan)

1) Extract the lowest bit as prev = n & 1, then right-shift once.
2) While n > 0, get curr = n & 1.
3) If curr == prev, return false.
4) Update prev = curr, then right-shift n.
5) If loop finishes, return true.

Complexity Analysis

Time: O(log n) (one pass over bits).
Space: O(1).

Common Pitfalls

- Forgetting to update prev after each step.
- Comparing decimal digits instead of binary bits.
- Mishandling very small input like n = 1 (should return true).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean hasAlternatingBits(int n) {
        int prev = n & 1;
        n >>= 1;

        while (n > 0) {
            int curr = n & 1;
            if (curr == prev) {
                return false;
            }
            prev = curr;
            n >>= 1;
        }

        return true;
    }
}

func hasAlternatingBits(n int) bool {
    prev := n & 1
    n >>= 1

    for n > 0 {
        curr := n & 1
        if curr == prev {
            return false
        }
        prev = curr
        n >>= 1
    }

    return true
}

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int prev = n & 1;
        n >>= 1;

        while (n > 0) {
            int curr = n & 1;
            if (curr == prev) return false;
            prev = curr;
            n >>= 1;
        }

        return true;
    }
};

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        prev = n & 1
        n >>= 1

        while n > 0:
            curr = n & 1
            if curr == prev:
                return False
            prev = curr
            n >>= 1

        return True

/**
 * @param {number} n
 * @return {boolean}
 */
var hasAlternatingBits = function(n) {
  let prev = n & 1;
  n >>= 1;

  while (n > 0) {
    const curr = n & 1;
    if (curr === prev) {
      return false;
    }
    prev = curr;
    n >>= 1;
  }

  return true;
};

中文

题目概述

给定一个正整数 n，判断它的二进制表示是否为“相邻位交替”——即每一对相邻 bit 都不同（例如 1010）。

核心思路

这是一个“相邻位关系”问题。通过不断右移 n，比较当前最低位与上一位是否相等；若相等则不满足交替条件，立刻返回 false。

暴力解法与不足

暴力法是先把 n 转成二进制字符串，再逐位比较。实现直观，但有额外字符串构造与空间开销。

最优算法步骤（位运算扫描）

1）先取 prev = n & 1，然后右移一位。
2）循环中取 curr = n & 1。
3）若 curr == prev，直接返回 false。
4）更新 prev = curr，继续右移。
5）循环结束仍未冲突则返回 true。

复杂度分析

时间复杂度：O(log n)（按 bit 位数扫描）。
空间复杂度：O(1)。

常见陷阱

- 忘记在每轮比较后更新 prev。
- 误把十进制相邻数字当作比较对象。
- 忽略极小输入，如 n=1（应返回 true）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean hasAlternatingBits(int n) {
        int prev = n & 1;
        n >>= 1;

        while (n > 0) {
            int curr = n & 1;
            if (curr == prev) {
                return false;
            }
            prev = curr;
            n >>= 1;
        }

        return true;
    }
}

func hasAlternatingBits(n int) bool {
    prev := n & 1
    n >>= 1

    for n > 0 {
        curr := n & 1
        if curr == prev {
            return false
        }
        prev = curr
        n >>= 1
    }

    return true
}

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int prev = n & 1;
        n >>= 1;

        while (n > 0) {
            int curr = n & 1;
            if (curr == prev) return false;
            prev = curr;
            n >>= 1;
        }

        return true;
    }
};

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        prev = n & 1
        n >>= 1

        while n > 0:
            curr = n & 1
            if curr == prev:
                return False
            prev = curr
            n >>= 1

        return True

/**
 * @param {number} n
 * @return {boolean}
 */
var hasAlternatingBits = function(n) {
  let prev = n & 1;
  n >>= 1;

  while (n > 0) {
    const curr = n & 1;
    if (curr === prev) {
      return false;
    }
    prev = curr;
    n >>= 1;
  }

  return true;
};