Vinn's Studio

Bitwise Operation

Word count: 6.3kReading time: 25 min
2022/01/06 Share

计算机中的数在内存中都是以二进制 (Binary) 形式进行存储的，用位运算 (Bitwise Operation) 可以直接对整数在内存中的二进制位进行操作，因此其执行效率非常高，在程序中尽量使用位运算进行操作，这会大大提高程序的性能。

0. 进制前缀

下表中的转化函数为 Python 函数：

前缀 进制 转化函数 范例
无 十进制 int() 2, 3, 5, 8, 18, 26, ...
0b 二进制 bin() 0b10, 0b11, 0b101, 0b1000, 0b10010, 0b11010, ...
0o 八进制 oct() 0o2, 0o3, 0o5, 0o10, 0o22, 0o32, ...
0x 十六进制 hex() 0x2, 0x3, 0x5, 0x8, 0x12, 0x1a, ...

1. 位操作符

1.1. 位与运算

&，或者写为 and：当两个位都是 1 时才为 1；否则为 0

1
2
0b10011 & 0b11001 -> 0b10001
19 & 25 -> 17

1.2. 位或运算

|，或者写为 or：只要有一位是 1 时，就为 1；当两个位都是 0 时才为 0

1
2
0b10011 | 0b11001 -> 0b11011
19 | 25 -> 27

1.3. 异或运算

^：两个位不同则为 1；否则为 0

1
2
0b10011 ^ 0b11001 -> 0b1010
19 ^ 25 -> 10

1.4. 取反运算

~：将 0 变为 1；将 1 变为 0；对于无符号数，直接输出取反结果；对于有符号数，考虑补码进行计算

1
2
3
4
5
6
# 无符号数
~0b10011 -> 0b1100
~19 -> 12
# 有符号数
~0b10011 -> -0b10100
~19 -> -20

1.4.1. 具体逻辑

以 8 位二进制有符号数为例，有：

  • 原码：一个数的原码就是其 8 位二进制表示，例如 2 的原码为 00000010；

  • 反码：一个数的反码就是其 8 位二进制表示按位取反的结果，例如 2 的反码为 11111101；

  • 补码：

    • 一个正整数的补码就是其 8 位二进制表示（即原码），例如 2 的补码为 00000010；
    • 一个负整数的补码就是其对应的正整数的 8 位二进制表示按位取反后加 1 的结果，例如 -2 的补码为 11111110；

而事实上，在计算机系统中，数值一律用补码来表示和存储，并且将补码的第一位视为符号位：显然，符号位为 0 表示这是一个正数，符号位为 1 表示这是一个负数。

以 19 的取反结果是 -20 为例：

  • 8 位二进制下，19 的补码为 00010011，其按位取反的结果 ~19 实际上为 11101100（而不是无符号整数直观想法中的 10011 取反为 01100）;
  • 而这个取反结果的第一位是 1，说明这是一个负数的补码，根据负数补码的定义反推回去，这个补码对应的数字应该是 -20（具体过程为：将 11101100 减去 1 后得到 11101011，然后全部按位取反得到 00010100，它是 20 的原码，因此这个数字其实是 -20）。

1.4.2. 重要结论

根据补码的定义，有以下结论：一个数按位取反加一后就是这个数的负数，即 ~a + 1 = -a，因此 ~ 运算符计算的结果可以通过 ~a = -a - 1 直接得到；

1.4.3. 定义原因

为什么要这样定义补码：补码的定义主要是为了解决计算机中负数的储存问题。

  • 实际上，某个正整数对应的负整数满足：正整数 + 负整数 = 0；
  • 因此，如果考虑将某个正整数的原码按位取反，则必有：该正整数 + 按位取反的结果 = 11111111；
  • 此时如果再加上 1，就能得到 0（进位溢出忽略）：该正整数 + 按位取反的结果 + 1 = 00000000，因此，按位取反 + 1 = 该正整数对应的负数。

1.5. 左移运算

<<：向左进行移位操作，最高位丢弃，低位补 0

1
2
0b100 << 3 -> 0b100000
4 << 3 -> 32

1.6. 右移运算

>>：向右进行移位操作，对无符号数，高位补 0；对于有符号数，考虑补码进行计算，高位补符号位（正数补 0；负数补 1）

1
2
3
4
5
6
# 无符号数
0b10100 >> 3 -> 0b10
20 >> 3 -> 2
# 有符号数
-0b10100 >> 3 -> -0b11
-20 >> 3 -> -3

以 -20 右移 3 位等于 -3 为例：

  • 8 位二进制有符号数 -20 的补码为 11101100，右移 3 位且高位补 1 后得到 11111101；
  • 该结果的第一位是 1，说明这是一个负数的补码，根据负数补码的定义反推回去，这个补码对应的数字应该是 -3（具体过程为：将 11111101 减去 1 后得到 11111100，然后全部按位取反得到 00000011，它是 3 的原码，因此这个数字其实是 -3）。

2. 常见操作

2.1. 位操作实现乘除法

数 a 向右移一位，相当于将 a 除以 2；数 a 向左移一位，相当于将 a 乘以 2。

1
2
3
4
8 >> 1 -> 4
8 >> 2 -> 2
8 << 1 -> 16
8 << 2 -> 32

注意：除法操作，使用 a >> 1 的运行速度比 a // 2 更快。

2.2. 位操作判断奇偶数

只要根据二进制的最后一位就能判断一个数的奇偶：最后一位为 0 就是偶数，为 1 就是奇数。只需将这个数与 1 做位与运算就能得到该数的二进制最后一位。

1
2
3
4
if a & 1 == 0:
    return 'a is even'
if a & 1 != 0:
    return 'a is odd'

注意：使用位操作 a & 1 == 0 判断奇偶数的运行速度比使用 a % 2 == 0 更快。

2.3. 位操作模拟加法

2.3.1. 加法的拆分

十进制的加法运算可以拆分为不进位加法部分和仅计算进位部分：

  • 不进位加法：每个位置只计算这一位上的加法结果，若有进位也只保留结果的个位
  • 仅计算进位：每个位置只记录是否有来自下一位的进位（仅计算下一个位置的进位，再之后的不考虑），如果有则这个位置为 1；如果没有则这个位置为 0

以 759 + 674 = 1433 为例：

  • 不进位加法：759 + 674 = 323
  • 仅计算进位：759 + 674 = 1110

最终的加法结果为两个部分结果之和：323 + 1110 = 1433

2.3.2. 位运算模拟

这样的拆分在二进制下也成立。位运算可以分别模拟二进制加法拆分的两个部分，对于整数 x 和 y：

  • 不进位加法：answer = x ^ y
  • 仅计算进位：carry = (x & y) << 1

answer 和 carry 分别为两个部分的结果，answer + carry 的结果就是 x + y 的结果。注意此处需要继续模拟 answer 和 carry 的求和，因此可以将 x 和 y 分别更新为 answer 和 carry，循环上述计算直到 y 等于 0（即进位部分 carry 等于 0，表示不再有进位发生），此时的 x 就是最终的求和结果（没有进位时显然 answer 就是求和结果）：

1
2
3
4
5
6
def addBinary(x, y):
    while y:
        answer = x ^ y
        carry = (x & y) << 1
        x, y = answer, carry
    return x

2.4. 位计算操作符号

根据 1.4.2. 中的重要结论：一个数按位取反加一后就是这个数的负数（~a + 1 = -a），可以使用位运算对符号进行操作。

2.4.1. 位计算求相反数

可以使用位运算将正数变成负数，负数变成正数：

1
2
def reversal(a):
    return ~a + 1

2.4.2. 位计算求绝对值

正数的绝对值是其本身，负数的绝对值可以对其进行取反加一求得。因此，先根据数的符号位判断其正负，然后做对应的操作就能得到其绝对值：

  • 符号位即补码的第一位，正数的符号位为 0，负数的则为 1；
  • 以 8 位二进制有符号数 a 为例，其符号位可以通过 a >> 7 计算：
    • 当 a 为正数时，其最高位（符号位）为 0，显然 a >> 7 的结果为 00000000，即十进制数 0；
    • 当 a 为负数时，其最高位（符号位）为 1，显然 a >> 7 的结果为 11111111，这是十进制数 -1 的补码；
  • 因此，当 a >> 7 等于 0 时，a 的绝对值就是它本身；当 a >> 7 等于 -1 时，a 的绝对值就是 ~a + 1；

一般来说，整数以 64 位二进制有符号数补码的形式储存，因此实际使用时使用 a >> 63 来判断符号位：

1
2
3
def myAbs(a):
    sign = a >> 63 # 符号位
    return a if sign == 0 else ~a+1

上面的操作还可以进行优化，可以将 sign == 0 的条件判断语句去掉。以 8 位二进制有符号数 a 为例：

  • 实际上，对于负数 a，对应的 sign = a >> 7 值为 -1，其二进制补码为 11111111，它与 a 进行异或运算的结果相当于对 a 的每一位取反，即 a ^ sign = ~a，因此再加上 1 就是 (a ^ sign) + 1 = ~a + 1 即 a 的相反数，此处由于 sign = -1，因此也可以写为 (a ^ sign) - sign；
  • 对于正数 a，对应的 sign = a >> 7 值为 0，显然有 (a ^ sign) - sign 值为 a 本身；

因此，综上有：不论 a 是正数还是负数，(a ^ sign) - sign 都能表示 a 的绝对值：

1
2
3
def myAbs(a):
    sign = a >> 63 # 符号位
    return (a ^ sign) - sign

2.5. （Brian Kernighan 算法）消去二进制中最后一个 1

对于某个数 x，将它对应的二进制的最后一个 1 改为 0 的操作为：

1
x & (x - 1)

逻辑如下：

  • 若 x 为奇数，则显然最后一位上的数字就为 1，x - 1 就是将 x 最后一位上的 1 改为 0，其他位置不变，因此 x & (x - 1) 就是将最后一位 1 改为 0 的结果；
  • 若 x 为偶数，则 x - 1 会将 x 的二进制序列中的最后一个 1 改为 0，这个位置之后的所有位置（都是 0）都改为 1，这个位置之前的所有位置不变，因此 x & (x - 1) 也是将最后一位 1 改为 0 的结果；

2.6. 奇偶等特殊位置操作

存在一些特殊的数，它们的二进制序列有着一些特殊的 patetrn，能在针对 32 位二进制数进行计算时提供帮助：

十六进制 二进制 Pattern
0xaaaaaaaa 0b10101010101010101010101010101010 偶数位为 1，奇数位为 0
0x55555555 0b01010101010101010101010101010101 偶数位为 0，奇数位为 1
0x33333333 0b00110011001100110011001100110011 1 和 0 每隔两位交替出现，结尾为 1
0xcccccccc 0b11001100110011001100110011001100 1 和 0 每隔两位交替出现，结尾为 0
0x0f0f0f0f 0b00001111000011110000111100001111 1 和 0 每隔四位交替出现，结尾为 1
0xf0f0f0f0 0b11110000111100001111000011110000 1 和 0 每隔四位交替出现，结尾为 0
0x3f3f3f3f 0b00111111001111110011111100111111 可用于模拟正无穷大
0xbfbfbfbf 0b10111111101111111011111110111111 可用于模拟负无穷大

对于某个数 x，如下操作可以通过上述特殊数字实现（基本思路为：二进制中 1 和任何数或运算结果都为 1；0 和任何数与运算结果都为 0）：

1
2
3
4
5
x & 0xaaaaaaaa # 将 x 的二进制序列所有奇数位替换为 0
x | 0xaaaaaaaa # 将 x 的二进制序列所有偶数位替换为 1
x & 0x55555555 # 将 x 的二进制序列所有偶数位替换为 0
x | 0x55555555 # 将 x 的二进制序列所有奇数位替换为 1
...

2.7. 重复异或运算

对于整数 x 和 y，有如下性质：

1
x ^ y ^ y == x

证明：

  1. 显然异或运算满足交换律，即 a ^ b == b ^ a；

  2. 接下来证明异或运算满足结合律：假设 a[i] 表示整数 a 的二进制序列中第 i 位的值，则显然有：

    a[i] ^ b[i] == (a[i] + b[i]) % 2

    对于任意 i，有：

    (a[i] ^ b[i]) ^ c[i] == ((a[i] + b[i]) % 2 + c[i]) % 2 == (a[i] + b[i] + c[i]) % 2

    a[i] ^ (b[i] ^ c[i]) == (a[i] + (b[i] + c[i]) % 2) % 2 == (a[i] + b[i] + c[i]) % 2

    即：(a ^ b) ^ c == a ^ (b ^ c) 总是成立，异或运算满足结合律

  3. 由于异或运算满足交换律和结合律，因此 (x ^ y) ^ y == x ^ (y ^ y) == x ^ 0 == x

该性质还可以写作：

1
2
3
4
# 如果
z == x ^ y
# 则有
x == z ^ y

证明：

已知 z == x ^ y，则有：z ^ y == x ^ y ^ y，根据上述性质则有：z ^ y == x ^ y ^ y == x，即 x == z ^ y 成立。

2.8. 状态压缩（二进制掩码 Bit Mask）

任意集合/状态（不含重复元素）都可以按照一定的规则映射为一个唯一的二进制序列（该序列的每一个位置对应一种元素：0 表示该集合不包含这种元素；1 表示该集合包含了这种元素），该序列对应的数字就能作为该集合的一个掩码（mask）。

2.9. 位操作进行高低位交换

通过移位操作可以简单将数字的高低位进行交换。例如：给定一个 16 位的无符号整数，要求将其高 8 位与低 8 位进行交换，求出交换后的值。只需将将 a >> 8 和 a << 8 进行位或运算，取结果的后 16 位即可：

1
2
3
a = 34520 # 34520 的二进制表示为 0b0b1000011011011000
b = bin( (a >> 8) | (a << 8) )[-16:]
b = int(b, 2) # 将结果 b 写为十进制，为 55430

3. 具体应用

3.1. 用 O(1) 时间检测正整数是否为 2 的幂次方

使用操作：2.5. 消去二进制中最后一个 1

如果某个数（大于 0）是 2 的幂次方，则其二进制序列满足：

  • 这个数的二进制序列有且仅有一个 1，其他位置都是 0

因此，对于正整数 x，使用 x & (x - 1)将其最后一个 1 消去后，如果结果为 0，则表示 x 是 2 的幂次方：

1
2
def checkPowerOf2(x):
    return x & (x - 1) == 0

3.2. 用 O(1) 时间检测正整数是否为 4 的幂次方

使用操作：2.5. 消去二进制中最后一个 1；2.6. 奇偶等特殊位置操作

如果某个数（大于 0）是 4 的幂次方，则其二进制序列满足：

  • 这个数的二进制序列有且仅有一个 1，其他位置都是 0
  • 这个 1 处于奇数位，且不在最低位

对于第一个条件，只需使用 x & (x - 1)将其最后一个 1 消去后，如果结果为 0 则满足条件；

对于第二个条件，可以使用 x & 0x55555555 进行判断，该操作将 x 的所有偶数位替换为 0，如果替换后结果不为 0，则表示唯一的那个 1 处于奇数位，因此满足条件；

1
2
def checkPowerOf4(x):
    return x & (x - 1) == 0 and x & 0x55555555 != 0

注意：一个数是 4 的幂次方的充要条件还可以表示为：

  • 这个数是 2 的幂次方
  • 这个数减去 1 后是 3 的倍数

3.3. 整数的二进制表示中有多少个 1

使用操作：2.5. 消去二进制中最后一个 1

循环使用 x & (x - 1)，每次消去该整数二进制表示中的最后一个 1，直到这个整数等于 0，计算循环的总次数即可：

1
2
3
4
5
6
def countOnes(x):
    cnt = 0
    while x:
        x = x & (x - 1)
        cnt += 1
    return cnt

3.4. 给定一个含不同整数的集合，返回其所有的子集

使用操作：2.8. 二进制掩码

可以使用二进制进行子集枚举。目标集合的每个子集都可以用一个二进制序列表示：序列的第 i 位表示该子集中是否包含了目标集合的第 i 个元素。则每个子集就对应了一个整数。假设目标集合有 n 个元素，则 \(0\) 到 \(2^n-1\) 这一共 \(2^n\) 个整数正好一一对应目标集合的 \(2^n\) 个子集，按顺序输出即可。

3.5. 找出数组中仅出现一次的数 (LeetCode 136. Single Number)

使用操作：2.7. 重复异或运算

3.5.1. 基础

数组中，只有一个数仅出现一次，剩下都出现两次，要求找出仅出现一次的那个数。可以考虑按顺序将所有数进行异或运算，由于异或运算满足交换律和结合律，最终结果为 a ^ b ^ b ^ c ^ c ^ ...，根据 2.7. 中的性质，最终结果就等于唯一的那一个数 a。

1
2
3
4
5
def singleNumber(nums):
    output = 0
    for num in nums:
        output ^= num
    return output

3.5.2. 拓展一

数组中，只有两个数仅出现一次，剩下都出现两次，要求找出仅出现一次的那两个数。假设仅出现一次的两个数为 x 和 y，则有：

  • 根据 3.5.1. 中的思路，如果同样将所有数进行异或运算，则最终得到的结果应为 output == x ^ y；
  • 且由于 x != y，因此 output == x ^ y 一定不等于 0，则 output 的二进制序列中一定有至少一个位置是 1；
  • 在 output 的二进制序列中随机选择一个等于 1 的位置，将原数组中的所有数字按照这个位置的值分为两个子数组：其中一个子数组中所有数字的二进制表示在这个位置的值均为 0，另一个子数组中所有数字的二进制表示在这个位置的值均为 1；
  • 由于 output == x ^ y 在这个位置的值为 1，因此显然 x 和 y 对应的二进制序列必然其中一个在这个位置的值为 0，另一个序列在这个位置的值为 1，即 x 和 y分别属于两个子数组；
  • 对于成对出现的其他数字，相同数字的二进制序列在这个位置的值一定是相等的，即相同的数字一定在同一个子数组中；
  • 这样，题目就分解成了在两个子数组中分别找出 x 和 y 即可，即两次求解 3.5.1；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def twoSingleNumber(nums):
    # 异或运算得到 output
    output = 0 # output 为所有数字的异或结果
    for num in nums:
        output ^= num
    
    # 找到 output 的二进制序列中一个 1 的位置
    pos = 0 # 用于记录output 的二进制序列中最后一个 1 的位置
    for i in range(32):
        if (output >> i) & 1 == 1: # 找到 output 的二进制序列中最后一个 1 的位置
            pos = i
            break
    
    # 分组异或
    first, second = 0, 0 # 分别记录两个子数组的异或结果 
    for num in nums:
        if (num >> pos) & 1 == 0: # 第一组
            first ^= num
        else: # 第二组
            second ^= num
    
    return first, second

3.5.3. 拓展二

数组中，只有一个数仅出现一次，剩下都出现三次，要求找出仅出现一次的那个数。思考思路：

  • 如果不考虑那个只出现过一次的数，那么对于每一个二进制位，如果统计所有数字中这个位置上 1 出现的次数，则显然结果都应该是 3 的倍数；
  • 将那个只出现过一次的数也纳入统计，则只有该数字二进制表示中所有 1 对应的二进制位上的统计结果不能被 3 整除；
  • 因此通过统计每个二进制位上 1 出现的次数是否能被 3 整除，就可以推断出目标数字的二进制序列在该位置上的值（能被 3 整除则为 0，不能被 3 整除则为 1），从而确定了这个数字；

推广一下，所有其他数字出现 N（N>=2）次，而一个数字出现 1 次的情况，都可以用这种思路来推导出这个出现 1 次的数字。

1
2
3
4
5
6
7
8
9
10
11
def singleNumber3(nums):
    bit = [0] * 32 # 用于统计每个二进制位上 1 出现的次数
    for num in nums: # 遍历每个数字
        for i in range(32): # 遍历每个二进制位
            bit[i] += (num >> i) & 1
    
    res = 0
    for i in range(32):
        if bit[i] % 3 != 0: # 是否能被 3 整除
            res += 1 << i
    return res

还可以考虑在遍历数组的时候维护三个变量 one、two 以及 three，使得：

  • one 的二进制序列的某个位置等于 1，表示：遍历到目前为止，该位置上 1 出现的次数 n 满足 n % 3 == 1；
  • two 的二进制序列的某个位置等于 1，表示：遍历到目前为止，该位置上 1 出现的次数 n 满足 n % 3 == 2；
  • three 的二进制序列的某个位置等于 1，表示：遍历到目前为止，该位置上 1 出现的次数 n 满足 n % 3 == 0；

根据之前的分析，只需在遍历结束之后输出 one 的值即可。

当遍历到一个新的数字 num 时，具体的维护思路为：

  • two 中的 \(0 \to 1\)：对于 num 的二进制序列中所有等于 1 的位置，如果当前 one 的对应位置也等于 1，则这些位置（即 one & num 中等于 1 的位置）上 1 出现的次数在将 num 纳入计算后满足了 n % 3 == 2，因此 two 中的这些位置都要更新为 1，即 two |= one & num；（有些原本在 two 中值为 1 的位置在将 num 纳入计算后将变成满足 n % 3 == 0，这些位置的值应该改为 0，之后会处理）

  • one 中的 \(0 \to 1\)：对于 num 的二进制序列中所有等于 1 的位置，如果当前 one 的对应位置等于 0，则这些位置上 1 出现的次数在将 num 纳入计算后可能满足 n % 3 ==0 或 n % 3 == 1，可以暂时先将 one 中这些位置都更新为 1，即 one ^= num；（那些满足 n % 3 == 0 的位置的值应该改为 0，之后会处理）

  • three 的计算：对于某个二进制位，如果当前的 one 和当前的 two 中这个位置均为 1，则显然这个位置应该是满足 n % 3 == 0 的位置，即 three = one & two；

  • one 和 two 中的 \(1 \to 0\)：前两步操作只是将 one 和 two 中那些应该改为 1 的位置从 0 改成了 1，但是没有处理应该从 1 改成 0 的位置（满足 n % 3 == 0 的位置），而这些位置显然就是当前 three 中值为 1 的位置，因此将 one 和 two 中这些位置均更新为 0，即 one &= ~three 以及 two &= ~three；

1
2
3
4
5
6
7
8
9
10
def singleNumber3(nums):
    one, two, three = 0, 0, 0
    
    for num in nums:
        two |= one & num
        one ^= num
        three = one & two
        one &= ~three
        two &= ~three
    return one

3.6. 位操作交换两数

使用操作：2.7. 重复异或运算

操作交换两数可以不需要第三个临时变量（虽然普通操作也可以做到，但是效率较低）：

1
2
3
4
5
def swap(a, b):
    a ^= b # a' = (a ^ b)
    b ^= a # b' = b ^ a' = b ^ (a ^ b) = a ^ b ^ b = a
    a ^= b # a'' = a' ^ b' = (a ^ b) ^ a = b ^ a ^ a = b
    return a, b

3.7. 位操作进行二进制逆序

使用操作：2.6. 奇偶等特殊位置操作；2.9. 位操作进行高低位互换

将无符号数的二进制表示进行逆序，求取逆序后的结果，如：

1
2
3
4
5
6
数34520的二进制表示：
10000110 11011000

逆序后则为：
00011011 01100001
它的十进制为7009

在字符串逆序过程中，可以从字符串的首尾开始，依次交换两端的数据。在二进制中使用位的高低位交换会更方便进行处理，这里我们分组进行多步处理：

  • 第一步：以每 2 位为一组，组内进行高低位交换

    1
    2
    交换前： 10 00 01 10 11 01 10 00
    交换后： 01 00 10 01 11 10 01 00

  • 第二步：在上面的基础上，以每 4 位为 1 组，组内高低位进行交换

    1
    2
    交换前： 0100 1001 1110 0100
    交换后： 0001 0110 1011 0001

  • 第三步：以每 8 位为一组，组内高低位进行交换

    1
    2
    交换前： 00010110 10110001
    交换后： 01100001 00011011

  • 第四步：以每 16 位为一组，组内高低位进行交换

    1
    2
    交换前： 0110000100011011
    交换后： 0001101101100001

即可得到最终的交换结果。

上述第一步可以用如下操作模拟：（注意：此处所有操作都默认目标数字限定为 16 位无符号数，限定位数省略了截取最后 16 位的操作）

1
2
3
4
5
6
7
8
9
原数：10000110 11011000 # 数字 a

将所有偶数位设为 0，仅保留奇数位： 10000010 10001000 # 可用 a & 0xAAAA 模拟
将所有奇数位设为 0，仅保留偶数位： 00000100 01010000 # 可用 a & 0x5555 模拟

仅保留奇数位的结果右移一位：0 10000010 1000100 # a & 0xAAAA >> 1
仅保留偶数位的结果左移一位：0000100 01010000 0 # a & 0x5555 << 1

两数相或即可得到第一步交换的结果： 01001001 11100100 # a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)

同理，可以得到其第二、三和四步的位运算操作，最终整个交换流程为：

1
2
3
4
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1) # 第一步
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2) # 第二步
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4) # 第三步
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8) # 第四步

Author：Lingfeng Zhu

Original Link：https://lingfengzhu.github.io/2022/01/06/BitwiseOperation/

Published：January 6th 2022, 3:54:30 pm

Updated：March 1st 2022, 10:09:14 am

Copyright：This Article Uses Attribution-NonCommercial 4.0 International as the license

CATALOG
  1. 0. 进制前缀
  2. 1. 位操作符
    1. 1.1. 位与运算
    2. 1.2. 位或运算
    3. 1.3. 异或运算
    4. 1.4. 取反运算
      1. 1.4.1. 具体逻辑
      2. 1.4.2. 重要结论
      3. 1.4.3. 定义原因
    5. 1.5. 左移运算
    6. 1.6. 右移运算
  3. 2. 常见操作
    1. 2.1. 位操作实现乘除法
    2. 2.2. 位操作判断奇偶数
    3. 2.3. 位操作模拟加法
      1. 2.3.1. 加法的拆分
      2. 2.3.2. 位运算模拟
    4. 2.4. 位计算操作符号
      1. 2.4.1. 位计算求相反数
      2. 2.4.2. 位计算求绝对值
    5. 2.5. （Brian Kernighan 算法）消去二进制中最后一个 1
    6. 2.6. 奇偶等特殊位置操作
    7. 2.7. 重复异或运算
    8. 2.8. 状态压缩（二进制掩码 Bit Mask）
    9. 2.9. 位操作进行高低位交换
  4. 3. 具体应用
    1. 3.1. 用 O(1) 时间检测正整数是否为 2 的幂次方
    2. 3.2. 用 O(1) 时间检测正整数是否为 4 的幂次方
    3. 3.3. 整数的二进制表示中有多少个 1
    4. 3.4. 给定一个含不同整数的集合，返回其所有的子集
    5. 3.5. 找出数组中仅出现一次的数 (LeetCode 136. Single Number)
      1. 3.5.1. 基础
      2. 3.5.2. 拓展一
      3. 3.5.3. 拓展二
    6. 3.6. 位操作交换两数
    7. 3.7. 位操作进行二进制逆序
Total : 33
2022
2021
2020
NLP Survival Analysis COVID-19 Conda Docker Python Hexo Web-Frontend Pytorch RecSys
Deep-Learning Algorithm Statistics Syntax Machine-Learning Finance