如何高效判断数字的二进制表示中所有相邻比特位均不相同？

功能要求 #

校验输入数字的二进制表示不存在相邻的重复比特位：

• 输入42返回true：二进制为101010，无相邻重复比特
• 输入45返回false：二进制为101101，存在连续的11重复比特

实现思路 #

使用位运算实现，时间复杂度O(1)，无需遍历每一位：

1. 将原数n右移1位得到n >> 1
2. 两数做异或运算：如果原数没有相邻重复比特，异或结果的每一位都会是1
3. 校验异或结果是否为全1：将异或结果加1后和自身做与运算，若结果为0则说明是全1，符合要求

代码示例 #

Python 实现 #

def has_no_adjacent_duplicate_bits(n: int) -> bool:
    xor = n ^ (n >> 1)
    return (xor & (xor + 1)) == 0

测试验证 #

print(has_no_adjacent_duplicate_bits(42))  # 输出 True
print(has_no_adjacent_duplicate_bits(45))  # 输出 False

JavaScript 实现 #

function hasNoAdjacentDuplicateBits(n) {
    const xor = n ^ (n >> 1);
    return (xor & (xor + 1)) === 0;
}

内容的提问来源于stack exchange，提问作者SIMPLE_IS_BETTER.