位运算

693. Binary Number with Alternating Bits

n ^ (n >> 1)：判断是否相邻bit都不同，若不同则异或结果全为
not a & (a + 1)：判断是否所有bit都是

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        return not (a := n ^ (n >> 1)) & (a + 1)

• 时间复杂度：
• 空间复杂度：

461. Hamming Distance

Approach I** 逐位比较
i：二进制位向右移动的bit**位数

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return sum(1 for i in range(32) if x >> i & 1 != y >> i & 1)

• 时间复杂度：固定为
• 空间复杂度：

Approach II** 位移统计**
bin(num)：得到的二进制表示的字符串是0bxxxxxx

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return sum(1 for i in range(len(bin(max(x, y))) - 2) if (x >> i & 1) ^ (y >> i & 1))

• 时间复杂度：固定为
• 空间复杂度：

Approach II** lowbit**

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return bin(x ^ y).count('1')

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        def lowbit(x):                # 找到x最低位的1表示的数
            return x & -x
        res = 0
        i = x ^ y
        while i:
            i -= lowbit(i)
            res += 1
        return res

• 时间复杂度：固定为
• 空间复杂度：

477. Total Hamming Distance

数据量为，使用暴力解法两两匹配计算会超出时间限制。
：转换思路，考虑根据每一bit位来累积计算总汉明距离；对于每一个num，只考虑在nums中的其他数中有多少个第位与其不同，而不需要关心具体是哪些数。

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        res = 0
        for i in range(32):         # 对于每一个bit位（共32位）
            cnt_0 = cnt_1 = 0
            for num in nums:        # 遍历所有num，计算当前bit位0和1的数量
                if num >> i & 1:    # 采用位移的方式逐位累积
                    cnt_1 += 1
                else:
                    cnt_0 += 1
            res += cnt_0 * cnt_1
        return res

• 时间复杂度：固定为
• 空间复杂度：

136. Single Number

异或运算的性质：

1. 
2. 
3. 交换律 & 结合律

• 进阶：540. Single Element in a Sorted Array
• 

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        xor = 0
        for num in nums:
            xor ^= num
        return xor

• 时间复杂度：
• 空间复杂度：