位运算实用详解教程

介绍位运算的基础知识与实用技巧

发表于 2023/02/06 更新于 2026/04/06

作者 James Taylor

21 分钟阅读

位运算实用详解教程

本教程部分参考了 Matrix67 的《位运算简介及实用技巧》，运算符采用 C 语言系的表示方法，常用的许多高级语言都使用相同的运算符表示，如 Python 等。

位运算基础

位运算简介

位运算（Bitwise operation）是对整数的二进制位直接进行的运算。现代广泛使用的计算机中，数据、代码都是以二进制的形式储存的，二进制运算在计算机硬件上是 first class 的，其花费的指令周期比我们在高级语言中写下的加减乘除要少得多，且使用计算资源少。当然，现代的编译器已经能做到将加减乘除优化成高效的位运算指令，所以学位运算的目的并不在于将你所写的所有表达式都改成位运算，这样不仅可能妨碍编译器优化，还破坏了代码的可读性。学习位运算的目的是在需要直接使用位运算的情景下，能够自如地看懂和应用位运算直接操纵二进制位，比如单片机程序中直接写寄存器、特定场合下的特殊数据结构如编解码、某些使用精妙的位运算达成高效运算的场合，亦或者是在逆向工程中查看汇编代码，等等。在由二进制建构起来的计算机体系上，位运算是不可跳过的内容。

位运算使用

位运算概览如下表所示：

描述	常用符号	运算规则
逐位与 AND	a & b	两个位同时为1时结果为1，否则为0
逐位或 OR	a \| b	两个位同时为0时结果为0，否则为1
逐位取反 NOT	~a	0变成1，1变成0
逐位异或 XOR	a ^ b	两个位相同结果为0，相异为1
逐位左移	a « b	a向左移动b位，左边舍弃，右边补0
逐位右移	a » b	a向右移动b位，右边舍弃，左边补0

逐位与（AND）

对应逻辑上的与，逐位与对操作数的每一位进行与操作，其真值表如下：

A	B	A & B
0	0	0
0	1	0
1	0	0
1	1	1

可以看到，只有两位都为 1，结果才为 1。这里我们可以得到一个结论，如果我们用 1 去与一个未知数，那么结果取决于未知数；如果我们用 0 去与一个未知数，那么结果肯定为 0。

举个实际应用的例子，110101 & 000111 == 000101。我们可以这样理解，用 b 将 a 的第 4~6 位（从低位开始数）的比特位清零，这是逐位与操作的第一个主要用途，即用掩码（mask）将某些位置 0。或者我们也可以这样理解，b 将 a 的第 1 到第 3 位取出，这就是逐位与操作的第二个主要用途，即用掩码将特定位取出用于判断。

经典用法就是用来判断奇偶性，a & 1 为真则为奇数，否则为偶数。当然再次强调没有必要在这种操作上使用位运算，换成 if (a % 2) 或者 if (isOdd(a)) 可读性会好很多，编译器会优化成位运算的。

逐位或（OR）

对应逻辑或，逐位或对操作数的每一位进行或操作，其真值表如下：

A	B	A \| B
0	0	0
0	1	1
1	0	1
1	1	1

可以看到，只要有一位为 1，结果就为 1。我们同样可以得到一个结论，如果用 1 去或一个未知数，那么结果肯定为 1；如果用 0 去或一个未知数，那么结果就取决于未知数。

举个例子，100101 | 000111 == 100111。可以这样理解，用 b 将 a 的第 1~3 位的比特位置 1，而其它位保持不变。当然，也可以理解成 a 将 b 的第 1、3、6 位置 1。这就是逐位或的一个主要用途，用掩码将某些位置 1。

一般来说，将某一位置 0 是使用逐位与，但需要将最低位置 0 时也可以用逐位或，即 (a | 1) - 1，这样无论最低位是 0 还是 1 结果都是 0，从而不用构造出 111110 的掩码。

逐位取反（NOT）

逐位取反操作是很好理解的，其真值表为：

A	~A
0	1
1	0

值得注意的是，到目前为止我们讨论的都是无符号整数，即二进制 101101 直接转成十进制 45 。如果是有符号整数，取反时依然是逐位取反，但是转化成十进制时则需要使用补码规则解读。

逐位异或（XOR）

逐位异或（Exclusive OR）是一个比较特别的位运算，其真值表为：

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

当a和b不同时结果为 1，相同为 0。对于异或，我们可以有多种理解方式，异或的定义是一种，另一种是看成未知数异或 0 则不变，异或 1 则取反。这些理解方式都有具体的应用，比如用掩码将特定位取反，或者一个数异或自己等于 0。

两次异或同一个数结果不变，也就是说异或运算的逆运算是它本身。这可以用于简单的加密，比如密钥 b 是 100110 ，用 b 加密数据 a 110011 结果为 110011 ^ 100110 == 010101 ，解密就是再次用密钥 b 异或密文 010101 ^ 100110 == 110011 。

逐位异或的另一个经典用法就是不引入第三个变量交换两个变量：

  
{
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;
}

如果不是很理解的话，可以先看看下面的这段同样不引入第三个变量的交换代码：

  
{
    x = x + y;
    y = x - y;
    x = x - y;
}

实际上，对于两个互为逆运算的运算符都可以写成以上形式，执行第一行后 x 变成了两数的和，于是第二行将两数之和减去 y 得到 x 原本的值赋给了 y，第三行将两数之和减去 x 原本的值（放在变量 y 里）得到 y 原本的值放在变量 x 里，就完成了两变量的交换。

再次提醒，这种写法只当学习用，在现在的机器上与普通的三变量写法是一样快的，甚至GCC有一个专门的处理函数将这些奇技淫巧变成三变量的写法。第一没有速度上的区别，第二降低可读性，第三这种方法只适用于整数。

逐位左移&逐位右移

逐位左移和逐位右移是很好理解的，000111 << 2 的结果就是 011100，000111 >> 2 的结果是 000001，很明显地，由于是对二进制位的位移，那么左移n位相当于乘以 2^n，右移n位相当于除以 2^n，溢出、小数的部分丢弃。

位移还有逻辑位移和算术位移之分，上面所说的就是逻辑位移。对于左移，逻辑左移和算数左移是相同的，都是在后面补 0。对于算数右移，有符号整数在左边补的是符号位，也就是说，正数的算数右移在左边补 0，负数的算数右移在左边补 1，这样位移的符号是不变的。

有些编程语言会专门区分出逻辑和算数右移，比如 Java 中 >> 表示有符号右移（算数），>>> 表示无符号右移（逻辑）。在 C/C++ 中的位移行为是实现定义的（C++20有了良好定义），但是大部分编译器的实现都是算术位移，如果想要逻辑右移，那么先转型成无符号整数就可以了。

位移可以用来产生掩码，比如我想要前 8 位的掩码 0000000011111111，那么就写 (1 << 8) - 1。

位运算的常用应用

注：运算符优先级参考此处

功能	示例	位运算
去掉最后一位	110011->11001	x » 1
末尾加一个0	110011->1100110	x « 1
末尾加一个1	110011->1100111	(x « 1) + 1
末位置0	110011->110010	(x \| 1) - 1
末位置1	110010->110011	x \| 1
末位取反	101101->101100	x ^ 1
末尾起第k位置0	101101->101001,k=3	x & ~(1 « k - 1)
末尾起第k位置1	101001->101101,k=3	x \| (1 « k - 1)
末尾起第k位取反	101001->101101,k=3	x ^ (1 « k - 1)
取出末尾三位	1100101->101	x & 7
取出末尾n位	1101101->01101,n=5	x & ((1 « k) - 1)
取出末尾起第k位	1101101->1,k=4	(x » k - 1) & 1
末尾起n位全置1	101001->101111,n=4	x \| ((1 « k) - 1)
末尾起n位取反	101001->100110,n=4	x ^ ((1 « k) - 1)
把末尾起始连续的1置0	100101111->100100000	x & x + 1
把末尾起始连续的0置1	11011000->11011111	x \| x - 1
把末尾起第一个0置1	100101111->100111111	x \| x + 1
取末尾起所有连续的1	100101111->1111	x & ~(x + 1)或(x ^ x + 1) » 1
去掉末尾起第一个1的左边	100101000->1000	x & (x ^ x - 1)

位运算进阶

位运算操作的集大成者，推荐阅读《Hacker’s Delight》。

计算二进制中1的奇偶数

计算一个32位整数的二进制中1有奇数个还是偶数个，若偶数个1则输出0，若奇数个则输出1。例如11010011有5个1，则输出1。

简单实现使用循环计数：

  
int count1parity(uint32_t x)
{
    int count = 0;
    for (int i = 0; i < 32; i++)
    {
        count += x & 1;
        x >>= 1;
    }
    return count & 1;
}

复杂度为O(n)，即进行32次计算。

但实际上可以这样：

  
int count1parity(uint32_t x)
{
    x = x ^ (x >> 1);
    x = x ^ (x >> 2);
    x = x ^ (x >> 4);
    x = x ^ (x >> 8);
    x = x ^ (x >> 16);
    return x & 1;
}

这是什么原理呢？我们以11010011为例，第一次异或的结果表示第i位与第i+1位上1的奇偶数，如图所示，灰色的数字是我们不关心的，因为如此操作将整个数字切成4份，我们只关心1、3、5、7位上的结果。

对第一次异或结果再次进行移位异或，这次右移2位，由于先前的运算结果中的1、3、5、7位保存了本位与前一位的奇偶数，因此第二次运算相当于把结果合并一半。

同理，第三次运算完成了8位数字奇偶性计算的结果合并。

从计算的过程可以看出，这其实是分而治之的思想，复杂度为O(logn)，在32位下只需计算5次。

计算二进制中1的个数

这次我们不止想知道一个32位整数中的1的奇偶数，还想知道1的具体数量，我们同样可以运用分而治之的思想。

对于2位二进制，1的个数与结果的对应关系是：

00->00
01->01
10->01
11->10

其实就相当于第1位和第2位的数字相加，因此我们可以用：

  
(x & 1) + (x >> 1 & 1)

那么拓展到32位整数，第一次计算拓展为：

  
x = (x & 0x55555555) + (x >> 1 & 0x55555555);

同理，完整实现如下：

  
int bitcount(uint32_t x)
{
    x = (x & 0x55555555) + (x >> 1 & 0x55555555);
    x = (x & 0x33333333) + (x >> 2 & 0x33333333);
    x = (x & 0x0F0F0F0F) + (x >> 4 & 0x0F0F0F0F);
    x = (x & 0x00FF00FF) + (x >> 8 & 0x00FF00FF);
    x = (x & 0x0000FFFF) + (x >> 16 & 0x0000FFFF);
    return x;
}

注意到，第4步数据已经压缩到了1个完整的字节，而第5步压缩到了2个字节，因此从第4步开始可以考虑将4个字节直接相加：

  
x = (x & 0xFF) + (x >> 8 & 0xFF) + (x >> 16 & 0xFF) + (x >> 24 & 0xFF);

可以通过先左移再右移的方式等效0xFF的截断操作：

  
x = ((x << 24) >> 24) + ((x << 16) >> 24) + ((x << 8) >> 24) + ((x << 0) >> 24);

等效于：

  
x = (x << 24) + (x << 16) + (x << 8) + (x << 0);
x >>= 24;

等效于：

  
// x = (x * 2^24) + (x * 2^16) + (x * 2^8) + (x * 2^0);
x = (x * 0x01010101) >> 24;

最终实现如下：

  
int bitcount(uint32_t x)
{
    x = (x & 0x55555555) + (x >> 1 & 0x55555555);
    x = (x & 0x33333333) + (x >> 2 & 0x33333333);
    x = (x & 0x0F0F0F0F) + (x >> 4 & 0x0F0F0F0F);
    x = (x * 0x01010101) >> 24;
    return x;
}

这其实就是著名的SWAR算法，除此之外这个算法还有各种改进版，这个只是最基础版本。另外在某些CPU上是支持popcnt指令的，只需一条指令即可得到结果。

计算二进制中前导0个数

同样可以使用分而治之的方法：

  
int count_leading_zero(uint32_t x)
{
    if (x == 0) return 32;
    int n = 0;
    if ((x >> 16) == 0) { n += 16; x <<= 16; }
    if ((x >> 24) == 0) { n += 8; x <<= 8; }
    if ((x >> 28) == 0) { n += 4; x <<= 4; }
    if ((x >> 30) == 0) { n += 2; x <<= 2; }
    if ((x >> 31) == 0) { n += 1; }
    return n;
}

最后一步可以简化为：

  
int count_leading_zero(uint32_t x)
{
    if (x == 0) return 32;
    int n = 1; // 先假设第2位为0
    if ((x >> 16) == 0) { n += 16; x <<= 16; }
    if ((x >> 24) == 0) { n += 8; x <<= 8; }
    if ((x >> 28) == 0) { n += 4; x <<= 4; }
    if ((x >> 30) == 0) { n += 2; x <<= 2; }
    n -= x >> 31;
    return n;
}

计算二进制逆序

此操作可以用来转换大小端。方法依旧分而治之，首先交换相邻两个bit，然后以交换过的数作为整体，继续交换相邻的数，直到完成所有交换。

  
int reverse_bit(uint32_t x)
{
    x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1;
    x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2;
    x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4;
    x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >> 8;
    x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16;
    return x;
}

经验教程

位运算 C/C++

本文由作者按照 CC BY-NC-SA 4.0 进行授权