dmjcb个人博客

c/c++ 位操作

 
  • 2021年 11月14日

位操作(Bitwise Operations)是 C/C++ 中最贴近硬件底层的操作之一, 它不仅执行速度极快, 而且在状态压缩、权限控制、密码学、嵌入式开发以及算法竞赛中有着不可替代的作用

基础位运算符

位运算直接对整数在内存中的二进制补码进行操作

为演示清晰, 以下示例均以 4 位二进制数为例

按位取反

对操作数各二进制位按位取反, 即0变为1, 1变为0

位与(&)

同为 1 才为 1, 否则为 0

核心用途：清零、提取特定位(掩码操作)

A \ B 0 1
0 0 0
1 0 1 
// 4
6 & 5

flowchart TB
    %% 样式定义
    classDef opBox fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,color:#92400e,font-weight:bold;
    classDef bitOne fill:#dcfce7,stroke:#22c55e,stroke-width:2px,color:#166534,font-family:monospace,font-size:18px,font-weight:bold;
    classDef bitZero fill:#f1f5f9,stroke:#cbd5e1,stroke-width:2px,color:#64748b,font-family:monospace,font-size:18px;
    classDef resOne fill:#bbf7d0,stroke:#16a34a,stroke-width:3px,color:#14532d,font-family:monospace,font-size:18px,font-weight:bold;
    classDef resZero fill:#e2e8f0,stroke:#94a3b8,stroke-width:3px,color:#475569,font-family:monospace,font-size:18px;
    classDef linkAnd stroke:#f59e0b,stroke-width:2px;
    classDef linkOr stroke:#94a3b8,stroke-width:1.5px,stroke-dasharray: 4 4;

    subgraph Op6 ["🔢 操作数 A = 6"]
        direction TB
        b0["1"]
        b1["1"]
        b2["0"]
        b0 ~~~ b1 ~~~ b2
    end

    subgraph Op5 ["🔢 操作数 B = 5"]
        direction TB
        a0["1"]
        a1["0"]
        a2["1"]
        a0 ~~~ a1 ~~~ a2
    end

    subgraph Res4 ["✅ 结果 = 4"]
        direction TB
        c0["1"]
        c1["0"]
        c2["0"]
        c0 ~~~ c1 ~~~ c2
    end

    %% 连线：同为1则结果为1(实线高亮), 否则为0(虚线弱化)
    b0 ==>|"&"| a0
    a0 ==> c0
    b1 -.->|"&"| a1
    a1 -.-> c1
    b2 -.->|"&"| a2
    a2 -.-> c2

    %% 应用样式：结果位为1的标绿, 为0的标灰
    class Op6 opBox;
    class Op5 opBox;
    class Res4 opBox;

    class b0,b1 bitOne;
    class b2 bitZero;
    class a0,a2 bitOne;
    class a1 bitZero;
    class c0 resOne;
    class c1,c2 resZero;
  • 示例, 获取数字区间值
#include <stdio.h>

int main() {
    int a = 0x12345678;

    // 获取数字低8位值
    int a1 = a & 0xFF;

    // 获取数字低10位值
    int a2 = a & 0x3FF;

    // 获取数字10-19位值
    int a3 = (a >> 10) & 0x3FF;

    return 0;
}

位或(|)

有 1 则为 1, 全 0 才为 0

核心用途：将特定位置 1、组合数据

A \ B 0 1
0 0 1
1 1 1 
// 7
6 | 5

flowchart TB
    %% 样式定义
    classDef opBox fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,color:#92400e,font-weight:bold;
    classDef bitOne fill:#dcfce7,stroke:#22c55e,stroke-width:2px,color:#166534,font-family:monospace,font-size:18px,font-weight:bold;
    classDef bitZero fill:#f1f5f9,stroke:#cbd5e1,stroke-width:2px,color:#64748b,font-family:monospace,font-size:18px;
    classDef resOne fill:#bbf7d0,stroke:#16a34a,stroke-width:3px,color:#14532d,font-family:monospace,font-size:18px,font-weight:bold;
    classDef resZero fill:#e2e8f0,stroke:#94a3b8,stroke-width:3px,color:#475569,font-family:monospace,font-size:18px;
    classDef linkAnd stroke:#f59e0b,stroke-width:2px;
    classDef linkOr stroke:#94a3b8,stroke-width:1.5px,stroke-dasharray: 4 4;

    subgraph Op6 ["🔢 操作数 A = 6"]
        direction TB
        b0["1"]
        b1["1"]
        b2["0"]
        b0 ~~~ b1 ~~~ b2
    end

    subgraph Op5 ["🔢 操作数 B = 5"]
        direction TB
        a0["1"]
        a1["0"]
        a2["1"]
        a0 ~~~ a1 ~~~ a2
    end

    subgraph Res4 ["✅ 结果 = 7"]
        direction TB
        c0["1"]
        c1["1"]
        c2["1"]
        c0 ~~~ c1 ~~~ c2
    end

    %% 连线：同为1则结果为1(实线高亮), 否则为0(虚线弱化)
    b0 ==>|"|"| a0
    a0 ==> c0
    b1 -.->|"|"| a1
    a1 -.-> c1
    b2 -.->|"|"| a2
    a2 -.-> c2

    %% 应用样式：结果位为1的标绿, 为0的标灰
    class Op6 opBox;
    class Op5 opBox;
    class Res4 opBox;

    class b0,b1 bitOne;
    class b2 bitZero;
    class a0,a2 bitOne;
    class a1 bitZero;
    class c0,c1,c2 resOne;
  • 示例, 组合数字
#include <stdio.h>

int main() {
    unsigned char v[4] = {0x12, 0x34, 0x56, 0x78};
    int r = 0;

    // 必须显式转换为 int 再左移, 防止溢出和符号扩展问题
    r |= ((int)v[0] << 24);
    r |= ((int)v[1] << 16);
    r |= ((int)v[2] << 8);
    r |= ((int)v[3]);

    // 12345678
    printf("%x\n", r);
    return 0;
}

异或(^)

A \ B 0 1
0 0 1
1 1 0 
// 3
6 ^ 5

flowchart TB
    %% 样式定义
    classDef opBox fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,color:#92400e,font-weight:bold;
    classDef bitOne fill:#dcfce7,stroke:#22c55e,stroke-width:2px,color:#166534,font-family:monospace,font-size:18px,font-weight:bold;
    classDef bitZero fill:#f1f5f9,stroke:#cbd5e1,stroke-width:2px,color:#64748b,font-family:monospace,font-size:18px;
    classDef resOne fill:#bbf7d0,stroke:#16a34a,stroke-width:3px,color:#14532d,font-family:monospace,font-size:18px,font-weight:bold;
    classDef resZero fill:#e2e8f0,stroke:#94a3b8,stroke-width:3px,color:#475569,font-family:monospace,font-size:18px;
    classDef linkAnd stroke:#f59e0b,stroke-width:2px;
    classDef linkOr stroke:#94a3b8,stroke-width:1.5px,stroke-dasharray: 4 4;

    subgraph Op6 ["🔢 操作数 A = 6"]
        direction TB
        b0["1"]
        b1["1"]
        b2["0"]
        b0 ~~~ b1 ~~~ b2
    end

    subgraph Op5 ["🔢 操作数 B = 5"]
        direction TB
        a0["1"]
        a1["0"]
        a2["1"]
        a0 ~~~ a1 ~~~ a2
    end

    subgraph Res4 ["✅ 结果 = 7"]
        direction TB
        c0["0"]
        c1["1"]
        c2["1"]
        c0 ~~~ c1 ~~~ c2
    end

    %% 连线：同为1则结果为1(实线高亮), 否则为0(虚线弱化)
    b0 ==>|"^"| a0
    a0 ==> c0
    b1 -.->|"^"| a1
    a1 -.-> c1
    b2 -.->|"^"| a2
    a2 -.-> c2

    %% 应用样式：结果位为1的标绿, 为0的标灰
    class Op6 opBox;
    class Op5 opBox;
    class Res4 opBox;

    class b0,b1 bitOne;
    class b2 bitZero;
    class a0,a2 bitOne;
    class a1,c0 bitZero;
    class c1,c2 resOne;
  • 示例, 交换变量值
void swap(int &a, int &b) {
    // 注意：如果 a 和 b 是同一个内存地址(即 &a == &b), 此方法会将值清零！
    // 安全写法：if (&a != &b) { ... }
    a = a ^ b;
    b = b ^ a; // 此时 b = (a^b)^b = a
    a = a ^ b; // 此时 a = (a^b)^a = b
}

移位运算符

移位操作在底层直接对应 CPU 的移位指令, 是替代乘除法(针对 2 的幂)的高效手段

左移(«)

变量二进制值左移$n$位, 右侧补 0, 相当于乘$2^{n}$

int a = 3;      // 0011
int b = a << 2; // 1100 (即 12)

flowchart LR
    %% 样式定义 (与位与/位或图表保持系列一致)
    classDef opBox fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,color:#92400e,font-weight:bold;
    classDef resBox fill:#dbeafe,stroke:#3b82f6,stroke-width:2px,color:#1e3a8a,font-weight:bold;
    classDef bitOne fill:#dcfce7,stroke:#22c55e,stroke-width:2px,color:#166534,font-family:monospace,font-size:18px,font-weight:bold;
    classDef bitZero fill:#f1f5f9,stroke:#cbd5e1,stroke-width:2px,color:#64748b,font-family:monospace,font-size:18px;
    classDef bitNew fill:#fce7f3,stroke:#ec4899,stroke-width:2px,color:#9d174d,font-family:monospace,font-size:18px,font-weight:bold;
    classDef bitOut fill:#fee2e2,stroke:#f87171,stroke-width:2px,color:#991b1b,font-family:monospace,font-size:18px,text-decoration:line-through;
    classDef moveArrow stroke:#3b82f6,stroke-width:2.5px;
    classDef fadeArrow stroke:#cbd5e1,stroke-width:1.5px,stroke-dasharray: 4 4;

    %% ==================== 左移 << ====================
    subgraph L_Shift ["⬅️ 左移: 3 << 2"]
        direction TB
        subgraph L_Op ["原值 a = 3"]
            direction LR
            a0["0"]
            a1["0"]
            a2["1"]
            a3["1"]
            a0 ~~~ a1 ~~~ a2 ~~~ a3
        end
        subgraph L_Res ["结果 b = 12"]
            direction LR
            b0["1"]
            b1["1"]
            b2["0"]
            b3["0"]
            b0 ~~~ b1 ~~~ b2 ~~~ b3
        end
    end

    %% 左移连线：有效位移动
    a2 ==>|"<<"| b0
    a3 ==> b1
    %% 右侧补 0 (新位)
    L_New2["0 ✨"]:::bitNew -.->|"补0"| b2
    L_New3["0 ✨"]:::bitNew -.->|"补0"| b3

    %% 溢出位标记
    L_Out0["0"]:::bitOut
    L_Out1["0"]:::bitOut
    L_Out0 -.->|"溢出丢弃"| a0
    L_Out1 -.->|"溢出丢弃"| a1

    class L_Op opBox;
    class L_Res resBox;
    class a2,a3 bitOne;
    class a0,a1 bitZero;
    class b0,b1 bitOne;
    class b2,b3 bitZero;

右移

二进制值右移$n$位, 相当于除$2^{n}$(向下取整)

算术右移 vs 逻辑右移

  • 无符号数：执行逻辑右移, 左侧补 0
  • 有符号数：C/C++ 标准未明确规定, 但绝大多数现代编译器(GCC/Clang/MSVC)执行算术右移, 左侧补符号位(正数补 0, 负数补 1), 以保持负数的符号不变
int x = -8;       // 补码: 1111...1000
int y = x >> 2;   // 算术右移: 1111...1110 (即 -2)

unsigned int u = 8; 
unsigned int v = u >> 2; // 逻辑右移: 0000...0010 (即 2)

flowchart LR
    %% 样式定义 (与位与/位或图表保持系列一致)
    classDef opBox fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,color:#92400e,font-weight:bold;
    classDef resBox fill:#dbeafe,stroke:#3b82f6,stroke-width:2px,color:#1e3a8a,font-weight:bold;
    classDef bitOne fill:#dcfce7,stroke:#22c55e,stroke-width:2px,color:#166534,font-family:monospace,font-size:18px,font-weight:bold;
    classDef bitZero fill:#f1f5f9,stroke:#cbd5e1,stroke-width:2px,color:#64748b,font-family:monospace,font-size:18px;
    classDef bitNew fill:#fce7f3,stroke:#ec4899,stroke-width:2px,color:#9d174d,font-family:monospace,font-size:18px,font-weight:bold;
    classDef bitOut fill:#fee2e2,stroke:#f87171,stroke-width:2px,color:#991b1b,font-family:monospace,font-size:18px,text-decoration:line-through;
    classDef moveArrow stroke:#3b82f6,stroke-width:2.5px;
    classDef fadeArrow stroke:#cbd5e1,stroke-width:1.5px,stroke-dasharray: 4 4;

    %% ==================== 右移 >> ====================
    subgraph R_Shift ["➡️ 右移: 6 \>> 2"]
        direction TB
        subgraph R_Op ["原值 a = 6"]
            direction LR
            c0["0"]
            c1["1"]
            c2["1"]
            c3["0"]
            c0 ~~~ c1 ~~~ c2 ~~~ c3
        end
        subgraph R_Res ["结果 b = 1"]
            direction LR
            d0["0"]
            d1["0"]
            d2["0"]
            d3["1"]
            d0 ~~~ d1 ~~~ d2 ~~~ d3
        end
    end

    %% 右移连线：有效位移动
    c1 ==>|">>"| d3
    c2 ==> d2
    %% 左侧补 0 (逻辑右移/正数算术右移)
    R_New0["0 ✨"]:::bitNew -.->|"补0"| d0
    R_New1["0 ✨"]:::bitNew -.->|"补0"| d1

    %% 溢出位标记
    R_Out2["0"]:::bitOut
    R_Out3["0"]:::bitOut
    R_Out2 -.->|"溢出丢弃"| c3
    R_Out3 -.->|"溢出丢弃"| c0

    class R_Op opBox;
    class R_Res resBox;
    class c1,c2 bitOne;
    class c0,c3 bitZero;
    class d3 bitOne;
    class d0,d1,d2 bitZero;
  • 获取$x$第$i$位值(索引从 0 开始)
// 获取 x 的第 i 位(0 表示最低位)
int get_bit(int x, int i) {
    return (x >> i) & 1;
}

二进制枚举

在算法与离散数学中, 常需要枚举一个集合的所有子集

利用二进制位, 可以将集合的包含关系完美映射到整数的二进制位上, 这被称为状态压缩

设定

设存在集合$S$, 含$n$个元素($a_1$, $a_2$ $\cdots$ $a_n$)

  • 用一个 n 位二进制数表示一个子集

  • 第 i 位(从右往左, 索引从 $0$ 开始)为 $1$, 表示子集包含 $a_i$; 为 $0$ 表示不包含

  • $n$个元素集合子集个数为$2^n$, 对应0到$2^n - 1$

推导过程

$S$ = {$a_0$, $a_1$ $\cdots$ $a_n$}

将集合中从0开始计数第i个元素与二进制数从右往左数第i位一一对应

元素$a_1$对应二进制数第0位, 元素$a_2$对应二进制数第1位

flowchart TB
    %% 样式定义 (与系列图表保持视觉统一)
    classDef bitsBox fill:#eff6ff,stroke:#3b82f6,stroke-width:2px,color:#1e3a8a,font-weight:bold;
    classDef elemsBox fill:#f0fdf4,stroke:#22c55e,stroke-width:2px,color:#166534,font-weight:bold;
    classDef bitNode fill:#dbeafe,stroke:#60a5fa,stroke-width:1.5px,color:#1e40af,font-family:monospace,font-size:16px;
    classDef elemNode fill:#dcfce7,stroke:#4ade80,stroke-width:1.5px,color:#166534,font-family:monospace,font-size:16px;

    subgraph Bits ["🔢 二进制位 (从右向左计数)"]
        direction LR
        v_i["<b>第 i 位</b>"]
        v_x["<b>...</b>"]
        v_2["<b>第 2 位</b>"]
        v_1["<b>第 1 位</b>"]
        v_0["<b>第 0 位</b>"]
        v_i ~~~ v_x ~~~ v_2 ~~~ v_1 ~~~ v_0
    end

    subgraph Elems ["📦 集合 S 的元素"]
        direction LR
        a_i["<b>aᵢ</b>"]
        a_x["<b>...</b>"]
        a_2["<b>a₂</b>"]
        a_1["<b>a₁</b>"]
        a_0["<b>a₀</b>"]
        a_i ~~~ a_x ~~~ a_2 ~~~ a_1 ~~~ a_0
    end

    %% 映射连线：实线表示明确对应, 虚线表示省略
    v_i ==>|"对应"| a_i
    v_x -.-> a_x
    v_2 ==>|"对应"| a_2
    v_1 ==>|"对应"| a_1
    v_0 ==>|"对应"| a_0

    %% 应用样式
    class Bits bitsBox;
    class Elems elemsBox;
    class v_i,v_x,v_2,v_1,v_0 bitNode;
    class a_i,a_x,a_2,a_1,a_0 elemNode;

于是集合$S$所有子集可以表示为,

  • 空集: $(0000…0000)_2$, 即0

  • ${a_0}$: $(0000…0001)_2$, 即1

  • ${a_1}$: $(0000…0010)_2$, 即2

  • ${a_0, a_1}$: $(0000…0011)_2$, 即3

…..

子集序号 序号二进制 子集大小 包含元素
$1$ $\underbrace{00 \cdots 0001}_n$ $1$ $a_0$
$2$ $\underbrace{00 \cdots 0010}_n$ $1$ $a_1$
$3$ $\underbrace{00 \cdots 0011}_n$ $2$ $a_0, a_1$
$4$ $\underbrace{00 \cdots 0100}_n$ $1$ $a_2$
$5$ $\underbrace{00 \cdots 0101}_n$ $2$ $a_0, a_2$
$6$ $\underbrace{00 \cdots 0110}_n$ $2$ $a_1, a_2$
$7$ $\underbrace{00 \cdots 0111}_n$ $3$ $a_0, a_1, a_2$
$\cdots$ $\cdots$ $\cdots$ $\cdots$
$2^n$ $\underbrace{11 \cdots 1111}_n$ $n$ $a_0, a_1 \cdots a_n$

通过上表总结对于子集 $i$, 若 $i$ 二进制值第 $x$ 位为 $1$, 则子集包含$a_x$元素, 若为 $0$则子集不包含$a_x$元素

子集 $i$, $i$ 二进制值中含1数量为子集大小

程序

例如对于含 $5$ 个元素集合$S$, 其第 $11$ 个子集

因$(11)_2 = 01011$, 第$0, 1, 3$位为$1$, 因此包含$a_0, a_1, a_3$三个元素

flowchart TB
    %% 样式定义 (与系列图表保持视觉统一)
    classDef codeBox fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,color:#92400e,font-weight:bold;
    classDef elemBox fill:#f0fdf4,stroke:#22c55e,stroke-width:2px,color:#166534,font-weight:bold;
    
    classDef bitOne fill:#dcfce7,stroke:#22c55e,stroke-width:2px,color:#166534,font-family:monospace,font-size:18px,font-weight:bold;
    classDef bitZero fill:#f1f5f9,stroke:#cbd5e1,stroke-width:2px,color:#64748b,font-family:monospace,font-size:18px;
    
    classDef elemSel fill:#bbf7d0,stroke:#16a34a,stroke-width:3px,color:#14532d,font-family:monospace,font-size:16px,font-weight:bold;
    classDef elemUnsel fill:#e2e8f0,stroke:#94a3b8,stroke-width:1.5px,color:#94a3b8,font-family:monospace,font-size:16px;

    subgraph Code ["🔢 二进制编码 (11 = 01011)"]
        direction LR
        a0["0"]
        a1["0"]
        a2["1"]
        a3["0"]
        a4["1"]
        a5["1"]
        a0 ~~~ a1 ~~~ a2 ~~~ a3 ~~~ a4 ~~~ a5
    end

    subgraph Elems ["📦 集合元素 (选中 a₀, a₁, a₃)"]
        direction LR
        b0["a₅"]
        b1["a₄"]
        b2["a₃"]
        b3["a₂"]
        b4["a₁"]
        b5["a₀"]
        b0 ~~~ b1 ~~~ b2 ~~~ b3 ~~~ b4 ~~~ b5
    end

    %% 连线：1为实线高亮, 0为虚线弱化
    a0 -.-> b0
    a1 -.-> b1
    a2 ==>|"选"| b2
    a3 -.-> b3
    a4 ==>|"选"| b4
    a5 ==>|"选"| b5

    %% 应用样式
    class Code codeBox;
    class Elems elemBox;
    
    class a0,a1,a3 bitZero;
    class a2,a4,a5 bitOne;
    
    class b2,b4,b5 elemSel;
    class b0,b1,b3 elemUnsel;

c

// 元素数量
const int n = 5;

int a[5] = {1, 2, 3, 4, 5};

for(int i = 1; i <= (1 << n); i++){
    for(int j = 0; j < n; j++){
        // 若子集i中第j位为1, 则子集i包含a(j)
        if ((i >> j) & 1){
            // 选择a(j)
        }
    }
}

python

n = 3

a = [...]

for i in range(1, 1 << n):
    for j in range(n):
        if (i >> j) & 1:
            ...
© dmjcb个人博客 2021
搜索