Blog of AgioPan
0%

数据结构与算法自学笔记（10）- 异或运算和位运算的骚操作

Posted on Edited on In ,

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series
本笔记包括了异或运算和位运算的高效技巧与应用，包括了class030 -> class031的内容

030【必备】异或运算的骚操作

异或运算的核心性质

前置知识

异或运算是计算机科学中一种重要的位运算，符号为^。在Python中实现位运算题目时需要特别注意溢出和符号扩展问题，通常需要手动处理：

1
2
# Python中处理溢出的常见方法
result = (n << shift_amount) & 0xFFFFFFFF

异或运算的四大核心性质

1. 异或运算就是无进位相加

这是理解异或运算最重要的性质，其他所有性质都可以由此推导得出。

1
2
3
4
5
示例：5 ^ 3
5: 101
3: 011
   ---
   110  (结果为6)

异或预算取下标

2. 异或运算满足交换律和结合律

同一批数字，不管异或顺序如何，最终结果都相同：

  • a ^ b = b ^ a（交换律）
  • (a ^ b) ^ c = a ^ (b ^ c)（结合律）

3. 特殊值性质

1
2
3
4
5
# 任何数与0异或等于自己
0 ^ n = n

# 任何数与自己异或等于0
n ^ n = 0

n或n

4. 整体异或和性质

如果整体异或和为x，其中某部分异或和为y，那么剩余部分的异或和为x ^ y。

这个性质在很多题目中都有应用，特别是区间异或和相关的问题。

有趣的数学问题

让我们从一个有趣的概率问题开始：

问题：袋子里有a个白球，b个黑球。每次取2个球：

  • 取出2个白球或2个黑球 → 放回1个白球
  • 取出1白1黑 → 放回1个黑球

最终袋子里剩1个球，问这个球是黑球的概率？

答案：

  • 如果黑球数量为偶数，最终是黑球的概率为0%
  • 如果黑球数量为奇数，最终是黑球的概率为100%
  • 完全与白球数量无关！

黑白球结果

这个结果与异或运算的性质有关：黑球数量的奇偶性在整个过程中保持不变。

经典应用题目

题目1：用异或运算交换两数的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def swap(arr, i, j):
    # 注意：当i==j时会出错，实际开发中不推荐使用
    if i != j:  # 添加安全检查
        arr[i] = arr[i] ^ arr[j]  # 第一步
        arr[j] = arr[i] ^ arr[j]  # 第二步：arr[j]变成原arr[i]
        arr[i] = arr[i] ^ arr[j]  # 第三步：arr[i]变成原arr[j]

# 更简洁的变量交换
def swap_variables():
    a, b = -2323, 10
    a = a ^ b  # a现在是原a^原b
    b = a ^ b  # b现在是原a^原b^原b = 原a
    a = a ^ b  # a现在是原a^原b^原a = 原b
    return a, b
# 示例用法
if __name__ == "__main__":
    a = -2323  # 定义a
    b = 10     # 定义b  因为a^b=b^a ，这么操作的前提是a和b都有自己的内存空间
    a = a ^ b  # 第一步，a和b异或后的结果给a
    b = a ^ b  # 第二步，a和b再次异或的结果赋给b，b'=(a^b)^b
    a = a ^ b  # 第三步，a和b再次异或的结果赋给a,a''=a^b^((a^b)^b)=a^b^a^b^b=a^b^a，根据交换律，a^b^a=a^a^b=b
    print(a)   # 输出此时的a
    print(b)   # 输出此时的b

    arr = [3, 5]          # 定义一个数组
    swap(arr, 0, 1)       # 交换arr[0]和arr[1]
    print(arr[0])         # 输出交换后的arr[0],输出3
    print(arr[1])         # 输出交换后的arr[1],输出5
    swap(arr, 0, 0)       # 交换同一个元素（java会出错，需谨慎，但是python不会） Python的整数对象是不可变的，每次赋值都会创建新的整数对象。更重要的是，Python的异或运算对于相同值的结果是 0，这是数学上正确的，内存模型不同：Java：直接操作内存中的值Python：操作的是对象的引用，整数是不可变对象
    print(arr[0])         # 输出arr[0]，输出3
    print(arr[1])         # 输出arr[1]，输出5

原理分析：

  1. 第一步：a = a ^ b，a存储了原始a和b的异或结果
  2. 第二步：b = a ^ b ，则 b'=(a^b)^b
  3. 第三步：a = a ^ b ，则 a''=a^b^((a^b)^b)=a^b^a^b^b=a^b^a，根据交换律，a^b^a=a^a^b=b

题目2：不用判断语句返回两数最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 测试链接 : https://www.nowcoder.com/practice/d2707eaf98124f1e8f1d9c18ad487f76
def flip(n):
    """翻转0和1"""
    return n ^ 1  # 0变1，1变0

def sign(n):
    """非负数返回1，负数返回0"""
    return flip((n >> 31) & 1)
    #因为负数符号位为1，正数符号位为0，所以负数右移31位后符号位为1，正数右移31位后符号位为0
    # 右移后得到的值，可能不是严格的0或1，尤其在Python里，负数右移得到的是全1（二进制全是1，对应十进制-1）。
    # 所以为了保证只取最低1位（也就是现在的符号位），要 & 1。
    # 如果结果是0，0 & 1 = 0。
    # 如果结果是-1，-1 & 1 = 1（因为-1的二进制补码是全1)
def getMax1(a, b):
    # 有溢出风险的实现，若c溢出了的话会出错
    c = a - b                    # 计算差值
    returnA = sign(c)            # 差值非负则返回a
    returnB = flip(returnA)      # 差值负则返回b
    return a * returnA + b * returnB  # 保证互斥就行

def getMax2(a, b):
    # 没有溢出风险的实现，增加了一个判断a、b符号的逻辑
    c = a - b                    # 差值
    sa = sign(a)                 # a的符号，非负返回1，负数返回0
    sb = sign(b)                 # b的符号
    sc = sign(c)                 # 差值的符号
    diffAB = sa ^ sb             # 判断a和b的符号是否一样，如果符号不同，则为1；符号一样，则为0
    sameAB = flip(diffAB)        # 符号相同，则为1
    returnA = diffAB * sa + sameAB * sc  # 决定返回哪个，diffAB和sameAB只有一个能为1，a和b的符号不同，且a非负，则返回1；a和b的符号相同，且c非负，则返回1，整合起来就是判断a
    returnB = flip(returnA)                # 另一个
    return a * returnA + b * returnB       # 返回最大值

#示例用法
if __name__ == "__main__":
    a = -2**31                # Integer.MIN_VALUE
    b = 2**31 - 1             # Integer.MAX_VALUE
    # getMax1方法会错误，因为溢出
    print(getMax1(a, b))      # 可能错误
    # getMax2方法永远正确
    print(getMax2(a, b))      # 永远正确

核心思想：

  • 通过位运算判断数字符号
  • 用乘法实现条件选择，避免if语句
  • 处理溢出情况，确保算法的鲁棒性

题目3：找到缺失的数字

题目：给定包含n个不同数字的数组，数字范围为[0,n]，找出缺失的那个数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 测试链接 : https://leetcode.cn/problems/missing-number/
def missingNumber(nums):
    # eorAll用于异或0~n，0到10之间的数字缺了一个
    # eorHas用于异或数组内所有数
    eorAll = 0                  # 初始化eorAll
    eorHas = 0                  # 初始化eorHas
    for i in range(len(nums)):  # 遍历数组
        eorAll ^= i             # 累计异或0~n-1，把下标0-n-1全都异或起来
        eorHas ^= nums[i]       # 累计异或数组元素，
    eorAll ^= len(nums)         # 最后再异或n
    return eorAll ^ eorHas      # 缺失的数即为两者异或结果，这是由于交换律，所有出现两次的数字会相互抵消，最后只剩下缺失的数字
# 示例用法
# print(missingNumber([3,0,1]))  # 输出2

原理：

  • 完整序列：0,1,2,…,n
  • 给定数组：缺少一个数字
  • 两者异或后，相同数字抵消，剩下的就是缺失数字

题目4：找到出现奇数次的数字

题目：数组中只有一种数出现奇数次，其他数都出现偶数次，找到这个数。

1
2
3
4
5
6
7
8
# 测试链接 : https://leetcode.cn/problems/single-number/
def singleNumber(nums):
    eor = 0                     # 初始化eor
    for num in nums:            # 遍历数组
        eor ^= num              # 累计异或
    return eor                  # 返回结果，原理同code03
# 示例用法
# print(singleNumber([2,2,1]))  # 输出1

题目5：找到两个出现奇数次的数字

题目：数组中有2种数出现奇数次，其他数都出现偶数次，返回这2种数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# https://leetcode.cn/problems/single-number-iii/
def singleNumber(nums):
    eor1 = 0
    for num in nums:
        # nums中有2种数a、b出现了奇数次，其他的数都出现了偶数次
        eor1 ^= num                        # 累计异或所有数，得到a^b
    # eor1 : a ^ b
    # Brian Kernighan算法
    # 提取出二进制里最右侧的1
    rightOne = eor1 & -eor1                # &是与运算，返回1和1相与为1，0和0相与为0，1和0相与为0；
    # n 的二进制表示中，最右边的 1 之前可能有若干个 0。
    # -n 的二进制表示会反转所有位，然后加1，相当于把最右边的 1 及其右边的 0 都翻转了。
    # 这样，n & -n 只会留下最右边的 1，其余位都变成0。
    # 因为~n= n的取反+1，所以能够提取最右侧的1，所以就拿这个最右侧的1来分组
    eor2 = 0
    # 此外因为a^b不尽相同，则从左到右，a和b的二进制状态中，必然有一位不同（能找到一个位置上是1，假设是第k位），则可以利用这个不同进行分组
    # 分成两组，一组是第k位为0的数，另一组是第k位为1的数，而q，b一定分别落在不同的组里
    # 所以额外引入一个变量eor2来得到a或者b
    for num in nums:
        if (num & rightOne) == 0:          # 分组，最后返回，
            eor2 ^= num                    # 分组后累加异或，对分到“那一位为0”这一组的数进行异或。
    # 这组里除了 a 或 b 以外，其他数都成对出现（偶数次），异或后消掉了，只剩下一个（假设是 a）。
    return [eor2, eor1 ^ eor2]             # 返回那两个数

# 示例用法
# print(singleNumber([1,2,1,3,2,5]))  # 输出[3,5]（顺序无关）

关键技巧：

  • n & -n：提取最右侧的1
  • 用这个位进行分组，将a和b分到不同组
  • 每组内除了a或b，其他数都成对出现

Brian Kernighan算法原理：

1
2
3
假设 eor1 = 6 (二进制: 110)
-eor1 = -6 (二进制: ...11111010)  // 补码表示
eor1 & -eor1 = 110 & ...11111010 = 010 = 2

题目6：通用的k次方法

题目：数组中只有1种数出现次数少于m次，其他数都出现m次，找到这个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 测试链接 : https://leetcode.cn/problems/single-number-ii/
# 注意 : 测试题目只是通用方法的一个特例，课上讲了更通用的情况
def singleNumber(nums):
    return find(nums, 3)  # 调用更通用的方法，m=3

# 更通用的方法
# 已知数组中只有1种数出现次数少于m次，其他数都出现了m次
# 返回出现次数小于m次的那种数
def find(arr, m):
    # 统计每个位有多少个1，如果一个位置的1的个数不是m的整数倍，说明该位属于出现次数小于m次的数
    # cnts[0] : 0位上有多少个1
    # cnts[i] : i位上有多少个1
    # cnts[31] : 31位上有多少个1
    cnts = [0] * 32
    for num in arr:
        for i in range(32):
            cnts[i] += (num >> i) & 1   # 统计每个位有多少个1
    ans = 0
    for i in range(32):
        if cnts[i] % m != 0:            # 如果不是m的整数倍，说明该位属于少于m次的数
            ans |= 1 << i               # 把该位设置为1，|= 是“按位或赋值”运算符，相当于 ans = ans | (1 << i)
    # 处理负数
    if (ans & (1 << 31)) != 0:          # 如果最高位是1，说明是负数
        # 检查ans的第31位（最高位）是否为1。在32位整数里，第31位是符号位，1表示负数（补码）
        ans -= 1 << 32                  # 当检测到ans的第31位（最高位）为1时，把它转化为Python中的负数表示
        #在32位二进制补码表示中，负数的真实值等于它的二进制表示减去2^32，而Python的int没有溢出，补码负数要手动转换
    return ans

# 示例用法
# print(singleNumber([2,2,3,2]))  # 输出3

算法思路：

  1. 统计每一位上1的个数
  2. 如果某位上1的个数不是m的整数倍，说明目标数字在该位为1
  3. 重新构造答案

时间复杂度分析

操作 时间复杂度 空间复杂度 说明度
交换两数 O(1) O(1) 常数时间操作
找最大值 O(1) O(1) 位运算替代条件判断
找缺失数字 O(n) O(1) 遍历数组一次
找一个奇数次数字 O(n) O(1) 异或运算线性时间
找两个奇数次数字 O(n) O(1) 两次遍历，分组处理
通用k次方法 O(n) O(1) 虽然有32层循环但32是常数

核心技巧总结

1. 位运算技巧

1
2
3
4
5
6
7
8
9
10
11
# 提取最右侧的1
rightOne = n & -n

# 判断数字符号
sign = (n >> 31) & 1

# 翻转0和1
flip = n ^ 1

# 设置某位为1
ans |= 1 << i

2. 异或运算应用模式

  1. 消除配对：相同数字异或为0，利用这个性质找到不配对的数字
  2. 分组策略：根据某一位的不同将数组分成两组
  3. 位统计：统计每一位上1的个数，重构答案

3. Python特有注意事项

1
2
3
4
5
6
# 处理负数
if (ans & (1 << 31)) != 0:
    ans -= 1 << 32

# 处理溢出
result = (n << shift_amount) & 0xFFFFFFFF

异或运算虽然看起来简单，但在算法设计中有着广泛而巧妙的应用。掌握这些核心性质和应用模式，能够帮助我们解决很多看似困难的问题。特别是在处理数组中的配对、查找问题时，异或运算往往能提供O(1)空间复杂度的优雅解法。

031【必备】位运算的骚操作

前言

位运算有很多奇技淫巧，位运算的速度非常快，仅次于赋值操作，常数时间极好！
属于是大佬骚解，左神讲解，苯人copy就对了。

特别提醒：Python实现位运算的题目需要特别注意，需要自己去手动处理溢出和符号扩展等问题。

1
2
# Python中处理溢出的常见方法
result = (n << shift_amount) & 0xFFFFFFFF

核心算法：Brian Kernighan算法

Brian Kernighan算法是位运算中的经典算法，用于提取二进制数中最右侧的1。

算法原理

1
2
# 提取最右侧的1
rightOne = n & -n

工作原理：

  1. n的二进制表示中，最右边的1右边可能有若干个0
  2. -n是n的补码表示（所有位取反后加1），所以可以进位到最右边的1，这个1左边的和n 的左边也都是完全相反的
  3. n & -n只会保留最右边的1，其余位都变成0

示例演示：

1
2
3
假设 n = 12 (二进制: 1100)
-n = -12 (二进制: ...11110100)  // 补码表示
n & -n = 1100 & ...11110100 = 0100 = 4

这个算法在很多高级位运算技巧中都有应用，是理解后续算法的基础。

经典应用题目

题目1：判断一个整数是不是2的幂

问题描述：给定一个整数n，判断它是否为2的幂次方。

1
2
3
4
5
6
7
8
9
10
11
# 测试链接: https://leetcode.cn/problems/power-of-two/
def isPowerOfTwo(n):
    # n > 0 确保正数
    # n & -n 提取最右侧的1，如果n是2的幂，只会有一个1
    # n == (n & -n) 则说明n只有一个1
    return n > 0 and n == (n & -n)

# 示例用法
print(isPowerOfTwo(4))   # True (4 = 2^2)
print(isPowerOfTwo(6))   # False (6的二进制是110，有两个1)
print(isPowerOfTwo(16))  # True (16 = 2^4)

算法原理：

  • 2的幂的特点：二进制表示中只有一个1
  • 例如：1(1), 2(10), 4(100), 8(1000), 16(10000)
  • 利用Brian Kernighan算法提取最右侧的1
  • 如果提取的结果等于原数，说明只有一个1

时间复杂度：O(1)
空间复杂度：O(1)

题目2：判断一个整数是不是3的幂

问题描述：给定一个整数n，判断它是否为3的幂次方。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 测试链接: https://leetcode.cn/problems/power-of-three/
def isPowerOfThree(n):
    # 如果一个数字是3的某次幂，那么这个数一定只含有3这个质数因子
    # 1162261467是int型范围内，最大的3的幂，它是3的19次方
    # 这个1162261467只含有3这个质数因子，如果n也是只含有3这个质数因子，那么
    # 1162261467 % n == 0
    # 反之如果1162261467 % n != 0 说明n一定含有其他因子
    return n > 0 and 1162261467 % n == 0

# 示例用法
print(isPowerOfThree(27))  # True (27 = 3^3)
print(isPowerOfThree(45))  # False (45 = 3^2 * 5)
print(isPowerOfThree(81))  # True (81 = 3^4)

算法原理：

  • 利用数论知识：如果n是3的幂，那么n只含有质数因子3
  • 1162261467 = 3^19，是32位整数范围内最大的3的幂
  • 如果n也只含有质数因子3，那么1162261467一定能被n整除
  • 这种方法引入了额外的先验知识，是一种巧妙的数学技巧

关键洞察：

  • 3^19 = 1162261467 (32位int范围内最大的3的幂)
  • 如果n是3的幂，则n只有质数因子3
  • 因此最大的3的幂能被所有较小的3的幂整除

时间复杂度：O(1)
空间复杂度：O(1)

题目3：返回大于等于n的最小的2的幂

问题描述：给定一个非负整数n，返回大于等于n的最小的2的幂次方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def near2power(n):
    if n <= 0:
        return 1  # 非正数直接返回1
    n -= 1        # 先减1，保证等于2的幂时不变，这样处理可以保证：如果 n 本身就是 2 的幂，返回的还是 n 本身。
    # 例如 n = 8，n-1 = 7 (0111)，后面填充后再加1，结果还是 8
    n |= n >> 1   #这个是或逻辑，右移1位再取或可以保证用1填充右边
    n |= n >> 2  
    n |= n >> 4   
    n |= n >> 8   
    n |= n >> 16  # 这一坨代码的作用是把左边第一个1开始，往右的1都变成1
    n += 1        # 再加1得到最小2的幂
    # Python没有int溢出，可以直接返回
    if n > 0x7fffffff:
        return -0x80000000  # 超过int范围，返回整数最小值
    return n

# 示例用法
print(near2power(100))  # 128 (2^7)
print(near2power(16))   # 16 (本身就是2的幂)
print(near2power(33))   # 64 (2^6)

算法原理详解：

让我们以n = 100为例，详细演示算法过程：

Step 1：n = 100，先减1得到n = 99

1
99 的二进制：01100011

Step 2：逐步填充最高位右边的所有位

1
2
3
4
5
6
7
8
9
10
11
n = 99        : 01100011
n >> 1        : 00110001
n |= n >> 1   : 01110011  (把最高位向右扩展1位)

n >> 2        : 00011100
n |= n >> 2   : 01111111  (继续向右扩展2位)

n >> 4        : 00000111
n |= n >> 4   : 01111111  (继续向右扩展4位)

... (8位和16位移动不会改变结果，因为数字较小)

Step 3：n + 1 = 01111111 + 1 = 10000000 = 128

核心思想：

  1. 先减1：确保如果n本身是2的幂，结果仍然是n
  2. 逐步填充：将最高位1右边的所有位都填充为1
  3. 加1：得到下一个2的幂

为什么先减1？

  • 如果n=16(10000)，我们希望结果是16而不是32
  • 减1后：15(01111)
  • 填充后：15(01111)
  • 加1后：16(10000) ✓

位运算技巧解析：

1
2
3
4
5
6
# 通过连续的右移和或运算，将最高位的1向右"传播"
n |= n >> 1   # 传播1位
n |= n >> 2   # 传播2位  
n |= n >> 4   # 传播4位
n |= n >> 8   # 传播8位
n |= n >> 16  # 传播16位（覆盖32位整数的所有位）

时间复杂度：O(1) - 固定数量的位运算
空间复杂度：O(1) - 只使用常数额外空间

题目4：区间[left, right]内所有数字按位与的结果

问题描述：给定两个整数left和right，返回区间[left, right]内所有数字按位与的结果。

1
2
3
4
5
6
7
8
# 测试链接: https://leetcode.cn/problems/bitwise-and-of-numbers-range/
def rangeBitwiseAnd(left, right):
    while left < right:
        right -= right & -right  # 每次消掉right最右边的1
    return right #当 left == right 时，区间内只有1个数，直接返回即可；若left>right, 也照样返回right

# 示例用法
print(rangeBitwiseAnd(5, 7))   # 输出4

算法原理：

按位与的关键特性：

  • 如果区间[left, right]内某一位在这段区间内经历了从0到1的变化，那么最终结果这一位一定为0
  • 只有left和right的公共前缀部分才可能保留为1

消去变化的位：

  • right & -right取出right的最右侧的1（最低位的1）
  • 每次把right的最右边的1消掉，right变小，靠近left
  • 只要left < right，说明区间还有变化，继续消掉最低位的1

详细示例分析：

1
2
3
4
5
6
7
8
9
10
11
区间[5, 7]的按位与：
5: 101
6: 110  
7: 111
-----
结果: 100 = 4

分析过程：
- 最低位：5(1), 6(0), 7(1) → 有0有1 → 结果为0
- 第2位：5(0), 6(1), 7(1) → 有0有1 → 结果为0  
- 第3位：5(1), 6(1), 7(1) → 全为1 → 结果为1

算法执行过程：

1
2
3
4
5
6
7
8
left=5(101), right=7(111)
第1次：right & -right = 111 & 001 = 001
       right = 111 - 001 = 110
       left=5, right=6，继续
第2次：right & -right = 110 & 010 = 010  
       right = 110 - 010 = 100
       left=5, right=4，left > right，结束
返回right=4

时间复杂度：O(log n) - 最多执行log(right)次循环
空间复杂度：O(1)

看题目5和题目6前的提醒

  • 题目5和题目6代码看着跟脑子有大病一样，承认很强但似乎有点太嘚瑟了，是这样吗？
  • 不是的，条件判断相比于赋值、位运算、算术运算是稍慢的，所以其实有现实意义
  • 但是不需要追求在练算法过程中尽量少写条件判断，
  • 那样会带来很多不必要的困扰，还是要写尽量直白、尤其是自己能理解的代码最好
  • 大牛的实现欣赏完理解就好，下次当模版直接用
  • 还是那句话：属于是大佬骚解，左神讲解，苯人copy就对了

题目5：反转二进制位（超自然版）

问题描述：将一个32位无符号整数的二进制位完全反转。

1
2
3
4
5
6
7
8
9
10
11
12
# 测试链接: https://leetcode.cn/problems/reverse-bits/
def reverseBits(n):
    # 逆序二进制的状态，分治思想：1v1 → 2v2 → 4v4 → 8v8 → 16v16
    n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)   # 交换奇偶位
    n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)   # 交换每两位
    n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)   # 交换每四位
    n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)   # 交换每八位
    n = (n >> 16) | ((n & 0xffff) << 16)                    # 交换高低16位
    return n & 0xffffffff  # 保证结果32位

# 示例用法
print(reverseBits(43261596))  # 输出964176192

算法原理深度解析：

这是著名的位分组逆序法（Bitwise reversal by mask），采用分治思想：

第1步：交换奇偶位

1
2
3
4
5
6
7
8
# 0xaaaaaaaa = 10101010...10101010 (偶数位为1)
# 0x55555555 = 01010101...01010101 (奇数位为1)

例如：n = 11010110
奇数位(从右数第1,3,5,7位): 1_1_1_1_ = 1111
偶数位(从右数第2,4,6,8位): _1_0_0_0 = 1000

交换后：01101101

第2步：交换每两位

1
2
3
4
5
6
# 0xcccccccc = 11001100...11001100 (每两位的高位)
# 0x33333333 = 00110011...00110011 (每两位的低位)

例如：n = 01101101
分组：01|10|11|01
交换：10|01|11|10 = 10011110

第3步-5步：类似地交换4位、8位、16位

完整示例演示：

1
2
3
4
5
6
7
原数：11010110 (从左到右)
目标：01101011 (反转后)

Step1(交换奇偶位)：01101101
Step2(交换每2位)：  10011110  
Step3(交换每4位)：  11101001
Step4(交换每8位)：  01101011 ✓

为什么效率极高？

  • 没有任何条件判断和循环
  • 全部是位操作：按位与、或、移位
  • 5次操作完成32位反转，而传统方法需要32次循环

时间复杂度：O(1) - 固定5次位运算
空间复杂度：O(1)

题目6：统计二进制中1的个数（超自然版）

问题描述：计算两个整数的汉明距离（二进制位不同的位置数目）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 测试链接: https://leetcode.cn/problems/hamming-distance/
def hammingDistance(x, y):
    return cntOnes(x ^ y)  # 先异或，统计不同位数

def cntOnes(n):
    # 分组统计法：每次合并相邻组的1的个数
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555)     # 每两位一组
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333)     # 每四位一组  
    n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f)     # 每八位一组
    n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff)     # 每十六位一组
    n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff)    # 全部加起来
    return n

# 示例用法
print(hammingDistance(1, 4))  # 输出2 (1:001, 4:100, 异或:101, 有2个1)
print(cntOnes(13))           # 输出3 (13:1101, 有3个1)

算法原理深度解析：

这是分组统计法，核心思想是逐步合并局部的1的个数：

详细示例（n = 13 = 1101）：

初始状态：

1
n = 1101 (二进制)

第1步：每两位统计1的个数

1
2
3
4
5
# 0x55555555 = 01010101...01010101
n & 0x55555555     = 1101 & 0101 = 0101  # 保留奇数位
(n >> 1) & 0x55555555 = 0110 & 0101 = 0100  # 保留偶数位(右移后)

相加：0101 + 0100 = 1001

此时n的每2位表示该2位内1的个数：

  • 10（二进制）= 2（十进制）：前2位有2个1
  • 01（二进制）= 1（十进制）：后2位有1个1

第2步：每四位统计1的个数

1
2
3
4
5
# 0x33333333 = 00110011...00110011  
n & 0x33333333     = 1001 & 0011 = 0001
(n >> 2) & 0x33333333 = 0010 & 0011 = 0010

相加：0001 + 0010 = 0011

此时n=0011，表示整个4位中有3个1。

后续步骤类似，最终得到总的1的个数，更高位依此类推，每一步后，n的每2^k位表示这2^k位内1的总个数，最终全加到最低位

状态变化图解：

1
2
3
4
5
6
原始：  1101 (每位表示原始位值)
Step1： 1001 (每2位表示该2位内1的个数)  
Step2： 0011 (每4位表示该4位内1的个数)
Step3： 0011 (8位内1的个数，但只有4位所以不变)
...
最终：  3 (总共3个1)

为什么叫”分组统计”？

  1. 不是独立统计每组，而是累加合并
  2. 每步都使用上一步的统计结果
  3. 最终所有1的个数聚合到最低位

核心技巧总结：

  • 利用掩码分离不同位置的位
  • 用加法累积局部统计结果
  • 分治思想：部分→整体

时间复杂度：O(1) - 固定5次位运算
空间复杂度：O(1)

算法性能对比与应用场景

性能对比表

算法 时间复杂度 空间复杂度 核心技巧 适用场景
判断2的幂 O(1) O(1) Brian Kernighan算法 内存分配、哈希表大小
判断3的幂 O(1) O(1) 数论+预计算 数学问题、特殊判断
最小2的幂 O(1) O(1) 位填充技术 内存对齐、缓存优化
区间按位与 O(log n) O(1) 公共前缀 区间查询、数据结构
反转二进制 O(1) O(1) 分治+掩码 图像处理、编码转换
统计1的个数 O(1) O(1) 分组统计 数据压缩、校验算法

实际应用场景

1. 系统编程中的应用

1
2
3
4
5
6
7
# 内存对齐检查
def isAligned(address, alignment):
    return isPowerOfTwo(alignment) and (address & (alignment - 1)) == 0

# 快速向上对齐到2的幂
def alignUp(size, alignment):
    return (size + alignment - 1) & ~(alignment - 1)

2. 数据结构优化

1
2
3
4
5
6
7
8
# 哈希表大小优化
class HashTable:
    def __init__(self, initial_size):
        self.size = near2power(initial_size)  # 确保是2的幂
        self.table = [None] * self.size
    
    def hash(self, key):
        return hash(key) & (self.size - 1)  # 快速取模

3. 图像处理应用

1
2
3
4
5
6
7
# 图像位操作
def mirrorImage(pixel_data):
    return [reverseBits(pixel) for pixel in pixel_data]

# 图像特征提取
def hammingDistance(img1, img2):
    return sum(cntOnes(p1 ^ p2) for p1, p2 in zip(img1, img2))

核心技巧模板总结

1. Brian Kernighan系列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 基础：提取最右侧的1
rightOne = n & -n

# 应用1：判断2的幂
isPowerOfTwo = n > 0 and n == (n & -n)

# 应用2：清除最右侧的1  
n = n & (n - 1)

# 应用3：计算1的个数（朴素版）
def countOnes(n):
    count = 0
    while n:
        n = n & (n - 1)  # 每次清除最右侧的1
        count += 1
    return count

2. 位填充技术模板

1
2
3
4
5
6
7
8
9
10
11
12
# 标准位填充（用于找下一个2的幂）
def fillBits(n):
    n |= n >> 1
    n |= n >> 2
    n |= n >> 4  
    n |= n >> 8
    n |= n >> 16
    return n

def nextPowerOfTwo(n):
    if n <= 1: return 1
    return fillBits(n - 1) + 1

3. 分治+掩码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 反转二进制位模板
def reverseBits(n, bits=32):
    if bits == 32:
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
        n = (n >> 16) | ((n & 0xffff) << 16)
    return n

# 分组统计模板  
def countOnes(n):
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555)
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
    n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f)
    n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff)
    n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff)
    return n

4. Python位运算注意事项

1
2
3
4
5
6
7
8
9
10
11
12
13
# 符号处理
def handleSign(n):
    if (n & (1 << 31)) != 0:  # 检查符号位
        n -= 1 << 32          # 转换为Python负数
    return n

# 溢出检查
def checkOverflow(n):
    return -0x80000000 <= n <= 0x7fffffff

# 掩码应用
def mask32bit(n):
    return n & 0xffffffff

扩展思考

1. 为什么位运算如此高效？

  • CPU层面：位运算是最接近硬件的操作，执行速度极快
  • 并行性：现代CPU可以并行处理多个位
  • 无条件判断：避免了分支预测失误的性能损失

2. 什么时候不应该使用这些技巧？

  • 代码可读性：团队协作时，清晰比技巧更重要
  • 过度优化：在非性能关键路径上使用可能得不偿失
  • 平台差异：某些技巧在不同架构上表现可能不同

3. 如何掌握位运算？

  1. 理解原理：每个技巧背后的数学/逻辑基础
  2. 动手实践：在纸上画出二进制变化过程
  3. 模板化：将常用技巧整理成模板
  4. 适度应用：在合适的场景使用，不要炫技

位运算虽然看起来神秘，但其本质是对二进制数据的高效操作。掌握了这些核心技巧后，不仅能解决特定的算法问题，更能在系统编程、性能优化等场景中发挥重要作用。关键是要在”技巧性”和”可读性”之间找到平衡，让代码既高效又易维护。