最后更新：
2026年9月18日

位运算

二进制数

二进制数采用以2为基数的计数系统，仅使用两个符号，通常是“0”和“1”。

某一位的值为1时，称该位已置位；值为0时，称该位已清零。

二进制数(aₖ aₖ₋₁ … a₁ a₀)₂表示的数值为：

aₖ·2ᵏ + aₖ₋₁·2ᵏ⁻¹ + … + a₁·2 + a₀

例如，二进制数1101₂表示十进制数13：

1101₂ = 1·2³ + 1·2² + 0·2¹ + 1·2⁰ = 13

计算机把整数表示为二进制数。正整数（包括有符号和无符号类型）直接用其二进制位表示；有符号负整数通常使用补码表示。

unsigned int unsigned_number = 13;
assert(unsigned_number == 0b1101);

int positive_signed_number = 13;
assert(positive_signed_number == 0b1101);

int negative_signed_number = -13;
assert(negative_signed_number == 0b1111'1111'1111'1111'1111'1111'1111'0011);

CPU能通过专门的运算快速操作这些位。某些问题可以利用二进制表示缩短执行时间。在组合数学、动态规划等需要记录从给定集合中已选择哪些对象的问题里，还可以使用足够宽的整数：每一位代表一个对象，选择时置位，移除时清零。

位运算符

对于固定宽度整数，以下运算在CPU上都可快速完成，原文将其速度与加法相提并论。

按位运算符

&：按位与，逐位比较两个操作数。只有两位都为1时，结果对应位才为1；否则为0。
|：按位或，逐位比较两个操作数。只要有一位为1，结果对应位就为1；否则为0。
⊕：按位异或（C++中写作^），逐位比较两个操作数。一位为0、另一位为1时，结果对应位为1；否则为0。
~：按位取反，翻转整数的每一位，1变为0，0变为1。

示例：

n         = 01011000
n-1       = 01010111
--------------------
n & (n-1) = 01010000

n         = 01011000
n-1       = 01010111
--------------------
n | (n-1) = 01011111

n         = 01011000
n-1       = 01010111
--------------------
n ^ (n-1) = 00001111

n         = 01011000
--------------------
~n        = 10100111

移位运算符

移位运算符有两种。

>>：右移，移除整数末尾的若干二进制位。对非负整数而言，每右移一位相当于整除2，因此右移k位相当于整除2ᵏ。

例如，5 >> 2 = 101₂ >> 2 = 1₂ = 1，与5 / 2² = 5 / 4的整数商1相同。原文指出，计算机移位通常比除法更快。
<<：左移，在末尾补零。与右移类似，左移k位相当于乘以2ᵏ，前提是结果在相关类型和语言规则允许的范围内。

例如，5 << 3 = 101₂ << 3 = 101000₂ = 40，与5 × 2³ = 5 × 8 = 40相同。

固定宽度整数的高位可能被丢弃。原文概括说，移位过多可能最终得到0；但C++还要求满足位宽与类型规则，具体限制见本节提示。

实用技巧

设置、翻转与清除某一位

利用移位和基本位运算，可以很容易地设置、翻转或清除某一位。1 << x只有第x位为1，~(1 << x)则只有第x位为0，其余位为1。

n | (1 << x)：设置n的第x位。
n ^ (1 << x)：翻转n的第x位。
n & ~(1 << x)：清除n的第x位。

检查某一位是否置位

把整数右移x位，使第x位位于最低位，再与1按位与，即可获取该位的值。

bool is_set(unsigned int number, int x) {
    return (number >> x) & 1;
}

检查整数能否被2的幂整除

通过按位与可以判断奇偶：偶数满足n & 1 = 0，奇数满足n & 1 = 1。更一般地，n能被2ᵏ整除，当且仅当n & (2ᵏ − 1) = 0。

bool isDivisibleByPowerOf2(int n, int k) {
    int powerOf2 = 1 << k;
    return (n & (powerOf2 - 1)) == 0;
}

把1左移k位可以计算2ᵏ。此技巧成立，是因为2ᵏ − 1恰好包含k个连续的1，而能被2ᵏ整除的整数，在这些位置必须全为0。

检查整数是否为2的幂

2的幂只有一个置位，例如32 = 0010 0000₂。它的前一个整数，在该位为0、之后所有位为1，例如31 = 0001 1111₂。因此，二者没有共同置位，按位与的结果为0。这种情况仅发生在2的幂以及本来没有任何置位的0上，所以还要单独排除0。

bool isPowerOfTwo(unsigned int n) {
    return n && !(n & (n - 1));
}

清除最右侧的置位

表达式n & (n − 1)可以清除n最右侧的置位。n − 1会翻转该位以及其后的所有位，这些位置都与原数不同；按位与后，它们全部变为0，结果即原数清除最右侧置位后的值。

例如，考虑52 = 0011 0100₂：

n         = 00110100
n-1       = 00110011
--------------------
n & (n-1) = 00110000

Brian Kernighan 算法

利用上述表达式，可以统计置位数量。

每次只处理整数中为1的位：计数后清除最右侧的置位，下次循环再处理新的最右侧置位。

int countSetBits(int n)
{
    int count = 0;
    while (n)
    {
        n = n & (n - 1);
        count++;
    }
    return count;
}

统计0到n的置位总数

要统计从0到n（含n）所有整数的置位总数，可以逐个运行Brian Kernighan算法，但竞赛提交可能因此超时。

可以利用这一规律：从1到2ˣ − 1的所有整数，共有x × 2ˣ⁻¹个置位。下表展示了这个规律：

0 ->   0 0 0 0
1 ->   0 0 0 1
2 ->   0 0 1 0
3 ->   0 0 1 1
4 ->   0 1 0 0
5 ->   0 1 0 1
6 ->   0 1 1 0
7 ->   0 1 1 1
8 ->   1 0 0 0

除最左侧以外，每列都有4（即2²）个置位。因此，从0到2³ − 1，总置位数为3 × 2³⁻¹。

利用这一规律，可以构造以下算法：

找到最大的指数x，使2ˣ不大于给定整数n。
用公式x × 2ˣ⁻¹计算从1到2ˣ − 1的置位总数。
统计2ˣ到n之间最高位的置位数，并加到总数中。
从n中减去2ˣ，用新的n重复以上步骤。

long long popcount_sum(unsigned n) {
    long long count = 0;
    while (n > 1) {
        int x = std::bit_width(n) - 1;
        count += (long long)x << (x - 1); // set bits below 2^x
        n -= 1u << x;
        count += n + 1;                   // leading bits of 2^x..n
    }
    return count + n;
}

其他技巧

n & (n + 1)清除末尾所有连续的1：0011 0111₂ → 0011 0000₂。
n | (n + 1)设置最右侧的0：0011 0101₂ → 0011 0111₂。
n & −n提取最右侧的置位：0011 0100₂ → 0000 0100₂。

更多技巧见《Hacker’s Delight》。

语言与编译器支持

C++20起，标准库bit提供了一些相关操作：

has_single_bit：检查整数是否为2的幂。
bit_ceil / bit_floor：向上或向下取整到相邻的2的幂。
rotl / rotr：循环移动整数中的位。
countl_zero / countr_zero / countl_one / countr_one：统计前导或末尾连续的0、1。
popcount：统计置位数量。

一些编译器也提供了辅助位操作的内置函数。例如，GCC的Built-in Functions Provided by GCC列表中的函数，较旧C++版本也可使用：

__builtin_popcount(unsigned int)返回置位数，例如__builtin_popcount(0b0001'0010'1100) == 4。
__builtin_ffs(int)返回第一个（最右侧）置位的位置，位置从1开始，例如__builtin_ffs(0b0001'0010'1100) == 3。
__builtin_clz(unsigned int)返回前导零的数量。例如，在32位unsigned int上，__builtin_clz(0b0001'0010'1100) == 23。
__builtin_ctz(unsigned int)返回末尾零的数量，例如__builtin_ctz(0b0001'0010'1100) == 2。
__builtin_parity(x)返回二进制表示中1的数量的奇偶性。

原文提醒：如果没有用#pragma GCC target("popcnt")启用特定编译目标，部分操作（包括C++20函数和编译器内置函数）在GCC中可能较慢。

练习题

jakobkogler (43.85%)
Carlos Javier Blanco (35.38%)
ganeshvarbalaji (11.15%)
ntanthedev (3.85%)
Harshdev098 (3.85%)
konstantinosalatzas (0.38%)
adamant-pwn (0.38%)
FinalTheory (0.38%)
aknayar (0.38%)
hieplpvip (0.38%)

正文相关链接

Two’s complement

文章版权归作者所有，未经允许请勿转载。

THE END

技术译文