What is the main approach to solving the Binary Number with Alternating Bits problem?

The main approach uses bitwise operations like XOR to check if the binary representation alternates between 1s and 0s.

How do I use XOR to solve this problem?

XOR the number with itself right-shifted by 1 and check if the result equals a number with all bits set to 1, which would confirm alternating bits.

Why is the solution for Binary Number with Alternating Bits O(1)?

The solution only involves a constant number of bitwise operations, regardless of the size of the input number.

What is the bitwise AND operation used for in this problem?

The bitwise AND operation helps verify if all bits of the result from XOR are set to 1, which is necessary to confirm alternating bits.

What are the common pitfalls to avoid in solving the Binary Number with Alternating Bits problem?

Avoid overcomplicating the solution with loops, incorrectly using bitwise operations, or misunderstanding the alternating pattern.

#693

Easy

auto_awesome位运算·操作·driven·solution·strategy

LeetCode 题解工作台

交替位二进制数

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。示例 1：输入： n = 5 输出： true 解释： 5 的二进制表示是：101 示例 2：输入： n = 7 输出： false 解释： 7 的二进制表示是：111. 示例 3：…

位运算

题目描述

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

示例 1：

输入：n = 5
输出：true
解释：5 的二进制表示是：101

示例 2：

输入：n = 7
输出：false
解释：7 的二进制表示是：111.

示例 3：

输入：n = 11
输出：false
解释：11 的二进制表示是：1011.

提示：

1 <= n <= 2³¹ - 1

lightbulb

解题思路

方法一：模拟

我们将 $n$ 循环右移直至为 $0$ ，依次检测 $n$ 的二进制位是否交替出现。若循环过程中发现 $0$ , $1$ 没有交替出现，直接返回 $\textit{false}$ 。否则循环结束返回 $\textit{true}$ 。

时间复杂度 $O(\log n)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        prev = -1
        while n:
            curr = n & 1
            if prev == curr:
                return False
            prev = curr
            n >>= 1
        return True

speed

复杂度分析

指标	值
时间	O(1)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for a clear understanding of bit manipulation techniques, especially XOR and bitwise AND operations.
question_mark
Expect the candidate to explain the constant time complexity and why this is efficient for the given problem.
question_mark
Be cautious of candidates who try to overcomplicate the problem with loops or other approaches.

warning

常见陷阱

外企场景

error
Misunderstanding the bitwise XOR operation and applying it incorrectly.
error
Assuming that the number should have an even number of bits, instead of focusing on alternating 1s and 0s.
error
Not recognizing the need for constant time solutions when the problem constraints allow it.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implement the solution for negative numbers and edge cases (e.g., minimum values).
arrow_right_alt
Adapt the solution to check for alternating bits in a given range of numbers.
arrow_right_alt
Optimize the solution further if the problem's constraints change.

help

常见问题

外企场景

继续练习

#691 贴纸拼词 #698 划分为k个相等的子集 #672 灯泡开关 Ⅱ