第2.17章: 位运算与 <bit> 头文件

位（bit）详解

位是二进制数字：要么是 0，要么是 1。在无符号整数中，每个位位置代表 2 的某个幂。

Bit position: 7   6   5   4   3   2   1   0
Power of two: 128  64  32  16   8   4   2   1
Binary value: 0   1   0   0   1   0   1   1
Decimal sum = 64 + 8 + 2 + 1 = 75
      

不要把位运算与逻辑运算混淆

位运算符（&、|、^、~）作用于整数的各个位。 逻辑运算符（&&、||、!）作用于布尔值，并返回 true/false。 例如，a & b 按位组合；a && b 检查两者是否都非零。

运算汇总表

下表展示每个运算符的作用与示例结果（二进制输出使用 fast_io::bin<true,true>）。

带二进制输出的位运算

使用 fast_io::bin<true,true> 可以带 0b 前缀和零填充地打印一个值的二进制形式。

#include <fast_io.h>

int main() {
    using namespace ::fast_io::iomnp;

    unsigned a{0b1010u}; // 10, 0b00001010
    unsigned b{0b1100u}; // 12, 0b00001100

    println("a = ", a, " ", bin<true,true>(a)); 
    // a = 10 0b00001010

    println("b = ", b, " ", bin<true,true>(b)); 
    // b = 12 0b00001100

    auto andv{a & b};
    println("a & b = ", andv, " ", bin<true,true>(andv)); 
    // a & b = 8 0b00001000

    auto orv{a | b};
    println("a | b = ", orv, " ", bin<true,true>(orv)); 
    // a | b = 14 0b00001110

    auto xorv{a ^ b};
    println("a ^ b = ", xorv, " ", bin<true,true>(xorv)); 
    // a ^ b = 6 0b00000110

    auto notv{~a};
    println("~a = ", notv, " ", bin<true,true>(notv)); 
    // ~a = (platform-dependent). For 32-bit unsigned: 4294967285 0b11111111111111111111111111110101

    auto lshift{a << 1};
    println("a << 1 = ", lshift, " ", bin<true,true>(lshift)); 
    // a << 1 = 20 0b00010100

    auto rshift{b >> 2};
    println("b >> 2 = ", rshift, " ", bin<true,true>(rshift)); 
    // b >> 2 = 3 0b00000011
}

移位直观图（ASCII 图）

Start: 0 b 0 0 0 0 1 0 1 0   (= 10)
Left shift by 1 →  0 b 0 0 0 1 0 1 0 0   (= 20)

Start: 0 b 0 0 0 0 1 1 0 0   (= 12)
Right shift by 2 → 0 b 0 0 0 0 0 0 1 1   (= 3)
      

左移把位往左移（右侧补 0）；右移把位往右移（无符号类型左侧补 0）。

<bit> 头文件工具

<bit> 头文件提供了分析与变换位模式的工具。 参见 cppreference：cppreference：<bit> 头文件。

• ::std::popcount(x)：被置为 1 的位数。
• ::std::countl_zero(x)：前导零的个数（依宽度而定）。
• ::std::countr_zero(x)：尾部零的个数。
• ::std::rotl(x, s)：循环左移 s 位。
• ::std::rotr(x, s)：循环右移 s 位。
• ::std::bit_width(x)：表示 x 所需的位数。

#include <fast_io.h>
#include <bit>

int main() {
    using namespace ::fast_io::iomnp;

    unsigned x{0b101100u}; // 44, 0b00101100

    println("x = ", x, " ", bin<true,true>(x)); 
    // x = 44 0b00101100

    println("popcount = ", ::std::popcount(x)); 
    // popcount = 3

    println("countl_zero = ", ::std::countl_zero(x)); 
    // countl_zero = (depends on width; e.g., 26 for 32-bit unsigned)

    println("countr_zero = ", ::std::countr_zero(x)); 
    // countr_zero = 2

    auto rotl2{::std::rotl(x,2)};
    println("rotl(x,2) = ", rotl2, " ", bin<true,true>(rotl2)); 
    // rotl(x,2) = 176 0b10110000

    auto rotr2{::std::rotr(x,2)};
    println("rotr(x,2) = ", rotr2, " ", bin<true,true>(rotr2)); 
    // rotr(x,2) = 11 0b00001011

    println("bit_width = ", ::std::bit_width(x)); 
    // bit_width = 6 (needs 6 bits to represent 44)
}

要点

• 二进制洞察：用 fast_io::bin<true,true> 打印，即可看到各位的变化。
• 位运算 vs 逻辑运算：不要把 &/| 与 &&/|| 混淆。
• 运算符：AND、OR、XOR、NOT、移位都在操作位模式；对无符号类型，移位会补入零。
• 工具：用 <bit> 中的函数来计数、旋转移位，以及测量位宽。