第十七 位运算

位运算概述

计算机底层数据以二进制形式存储，每一位（bit）只能是 0 或 1。位运算直接对二进制位进行操作，是计算机最底层的运算方式。与加减乘除等算术运算相比，位运算具有以下优势：

• 速度快：位运算是 CPU 原生支持的指令，通常只需一个时钟周期
• 空间省：一个位即可表示一个布尔状态，可用于紧凑的数据编码
• 用途广：权限控制、数据压缩、加密算法、图形处理等都离不开位运算

Rust 作为一门系统级编程语言，完整支持所有位运算操作，并通过 std::ops 模块提供了对应的运算符 trait，允许用户自定义类型的位运算行为。

位运算

六种基本位运算一览

与（AND）运算

运算符：&

真值表

只有当两个对应位都为 1 时，结果的该位才为 1，否则为 0。

常见用途

1. 掩码（Mask）——提取特定位

掩码是与运算最经典的应用。通过构造一个特定的二进制数（掩码），可以提取目标数据中的指定位。

fn main() {
    let value: u8 = 0b1011_0110; // 182

    // 提取低4位
    let low_4 = value & 0b0000_1111; // 0b0110 = 6
    println!("低4位: {:04b} = {}", low_4, low_4);

    // 提取高4位
    let high_4 = (value & 0b1111_0000) >> 4; // 0b1011 = 11
    println!("高4位: {:04b} = {}", high_4, high_4);

    // 提取第3位（从0开始计数）
    let bit_3 = (value >> 3) & 1;
    println!("第3位: {}", bit_3);
}

2. 清零特定位

要将某一位或某几位清零，只需构造一个掩码，目标位为 0，其余位为 1，然后做与运算。

fn main() {
    let mut flags: u8 = 0b1111_1111; // 所有标志位都开启

    // 将第2位和第5位清零
    let mask = !(0b0100_0100); // 0b1011_1011
    flags = flags & mask;
    println!("清零后: {:08b}", flags); // 10111011
}

3. 判断奇偶

一个数的二进制最低位决定了它的奇偶性：最低位为 1 是奇数，为 0 是偶数。

fn is_odd(n: i32) -> bool {
    n & 1 == 1
}

fn is_even(n: i32) -> bool {
    n & 1 == 0
}

fn main() {
    println!("5是奇数: {}", is_odd(5));   // true
    println!("8是偶数: {}", is_even(8));  // true
}

相比 n % 2 == 0，位运算方式避免了除法操作，效率更高。

Brian Kernighan 算法

Brian Kernighan 算法是位运算中最优雅的技巧之一。核心思想是：n & (n - 1) 可以将 n 的二进制表示中最低位的 1 置为 0。

原理分析：对于一个二进制数 n，n - 1 会将最低位的 1 变为 0，并将该位之后的所有 0 变为 1。因此 n & (n - 1) 恰好消除了最低位的 1。

$$n & (n-1) \Rightarrow \text{消除最低位的 } 1$$

/// 统计二进制中1的个数（Brian Kernighan算法）
fn count_ones(n: u64) -> u64 {
    let mut n = n;
    let mut count = 0;
    while n != 0 {
        n = n & (n - 1); // 每次消除一个1
        count += 1;
    }
    count
}

fn main() {
    println!("15(1111)中1的个数: {}", count_ones(15));  // 4
    println!("7(0111)中1的个数: {}", count_ones(7));    // 3
    println!("0中1的个数: {}", count_ones(0));           // 0
    println!("1024中1的个数: {}", count_ones(1024));     // 1
}

时间复杂度：$O(k)$，其中 $k$ 为二进制中 1 的个数，而非总位数。最坏情况下为 $O(\log n)$。

判断2的幂

利用 Brian Kernighan 算法的思想，可以高效判断一个数是否为 2 的幂。2 的幂的二进制表示中有且仅有一个 1。

$$n & (n-1) == 0 \text{ 且 } n > 0 \Rightarrow n \text{ 是2的幂}$$

fn is_power_of_two(n: u32) -> bool {
    n != 0 && (n & (n - 1)) == 0
}

fn main() {
    for i in 1..=32 {
        if is_power_of_two(i) {
            println!("{} 是2的幂", i);
        }
    }
    // 输出: 1, 2, 4, 8, 16, 32
}

或（OR）运算

运算符：|

真值表

只要两个对应位中有一个为 1，结果的该位就为 1。

常见用途

1. 置位（Set Bit）

要将某一位或某几位设置为 1，构造一个掩码，目标位为 1，其余位为 0，然后做或运算。

fn set_bit(mut value: u8, bit_index: usize) -> u8 {
    value | (1 << bit_index)
}

fn main() {
    let mut x: u8 = 0b1010_0000;
    x = set_bit(x, 0); // 设置第0位
    println!("设置第0位后: {:08b}", x); // 10100001
    x = set_bit(x, 3); // 设置第3位
    println!("设置第3位后: {:08b}", x); // 10101001
}

2. 权限组合（位标志）

位标志（bit flags）是或运算最典型的应用场景。每个标志占一个位，通过或运算可以组合多个标志。

#[derive(Debug, Clone, Copy)]
struct Permissions(u8);

const READ: u8    = 0b0000_0001; // 1
const WRITE: u8   = 0b0000_0010; // 2
const EXECUTE: u8 = 0b0000_0100; // 4

impl Permissions {
    fn new() -> Self {
        Permissions(0)
    }

    fn add(&mut self, perm: u8) {
        self.0 |= perm;
    }

    fn has(&self, perm: u8) -> bool {
        (self.0 & perm) != 0
    }

    fn remove(&mut self, perm: u8) {
        self.0 &= !perm;
    }
}

fn main() {
    let mut perms = Permissions::new();
    perms.add(READ | WRITE); // 组合权限
    println!("权限: {:08b}", perms.0); // 00000011

    println!("可读: {}", perms.has(READ));    // true
    println!("可写: {}", perms.has(WRITE));   // true
    println!("可执行: {}", perms.has(EXECUTE)); // false

    perms.remove(WRITE);
    println!("移除写权限后可写: {}", perms.has(WRITE)); // false
}

在实际开发中，Rust 的 bitflags crate 提供了更完善的位标志支持，可以安全、方便地定义和操作位标志。

非（NOT）运算

运算符：!（Rust 中推荐使用）或 ~

真值表

按位取反：将每一位 0 变 1、1 变 0。

补码表示

在计算机中，有符号整数采用**补码（two’s complement）**表示。取反运算的结果需要结合补码来理解：

$$\text{补码} = \text{原码取反} + 1$$

fn main() {
    let x: u8 = 0b0000_1111; // 15
    let y = !x;
    println!("!{:08b} = {:08b}", x, y); // !00001111 = 11110000 = 240

    // 对于有符号数，!的结果是补码表示
    let a: i8 = 5;  // 00000101
    let b = !a;      // 11111010 = -6（补码）
    println!("!{} = {}", a, b); // !5 = -6

    let c: i8 = 60;
    let d = !c;      // 11110011 = -61（补码）
    println!("!{} = {}", c, d); // !60 = -61
}

Rust 中的区别

Rust 中 ! 运算符既用于按位取反（整数类型），也用于逻辑非（bool 类型），具体行为取决于操作数的类型：

fn main() {
    // 整数类型：按位取反
    let x: i32 = 0b0000_1111;
    println!("按位取反: {}", !x); // -16

    // bool类型：逻辑非
    let flag = true;
    println!("逻辑非: {}", !flag); // false

    // ~ 运算符在Rust中已弃用，统一使用 !
    // 旧版Rust中 ~ 用于整数取反，现已不推荐
}

注意：在 Rust 中，~ 运算符已被弃用，统一使用 ! 进行按位取反。这与 C/C++ 中 ~ 用于取反、! 用于逻辑非的惯例不同。

异或（XOR）运算

运算符：^

真值表

相同为 0，不同为 1。异或运算也称为“不进位加法“。

异或运算(XOR)

异或运算 XOR 教程

运算法则

异或运算具有丰富的数学性质，是解决许多位运算问题的核心工具：

1. 归零律：$a \oplus a = 0$

   任何数异或其本身都等于 0。因为每一位都相同，按异或定义结果全为 0。

2. 恒等律：$a \oplus 0 = a$

   任何数异或 0 都等于其本身。因为 0 不改变任何位的值。

3. 交换律：$a \oplus b = b \oplus a$

   异或运算不依赖操作数的顺序，与加法类似。

4. 结合律：$a \oplus b \oplus c = a \oplus (b \oplus c) = (a \oplus b) \oplus c$

   多个数连续异或时，可以任意调整计算顺序。

5. 自反性：$a \oplus b \oplus a = b$

   由归零律和交换律推导：$a \oplus b \oplus a = a \oplus a \oplus b = 0 \oplus b = b$。这是异或交换变量的理论基础。

6. 可逆性：若 $d = a \oplus b \oplus c$，则 $a = d \oplus b \oplus c$

   异或运算可以“撤销“：知道结果和除一个操作数外的所有操作数，可以恢复那个操作数。

7. 逐位运算示例：若 $x = \text{0b0101}$，$y = \text{0b1011}$，则 $x \oplus y = \text{0b1110}$

   0101
   1011
   ----
   1110
   

8. 连续四整数归零：$\forall i \in \mathbb{Z}$，有 $4i \oplus (4i+1) \oplus (4i+2) \oplus (4i+3) = 0$

   四个连续整数异或结果为 0，因为它们覆盖了所有两位组合（00, 01, 10, 11），每一位上恰好有两个 0 和两个 1。

常见用途

1. 交换变量（不用临时变量）

利用自反性 $a \oplus b \oplus a = b$，可以在不借助临时变量的情况下交换两个数：

fn xor_swap(a: &mut i32, b: &mut i32) {
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

fn main() {
    let mut x = 42;
    let mut y = 99;
    xor_swap(&mut x, &mut y);
    println!("x = {}, y = {}", x, y); // x = 99, y = 42
}

注意：实际开发中建议使用 std::mem::swap，异或交换在两个变量指向同一内存地址时会产生错误结果（变为 0）。

2. 加密解密

异或运算具有对称性：$A \oplus K = C$，$C \oplus K = A$。用同一个密钥加密和解密。

fn xor_encrypt(plaintext: &[u8], key: u8) -> Vec<u8> {
    plaintext.iter().map(|&b| b ^ key).collect()
}

fn xor_decrypt(ciphertext: &[u8], key: u8) -> Vec<u8> {
    // 解密和加密是同一操作
    xor_encrypt(ciphertext, key)
}

fn main() {
    let message = b"Hello, Rust!";
    let key = 0x42;

    let encrypted = xor_encrypt(message, key);
    let decrypted = xor_decrypt(&encrypted, key);

    println!("原文: {:?}", String::from_utf8_lossy(message));
    println!("密文: {:?}", encrypted);
    println!("解密: {:?}", String::from_utf8_lossy(&decrypted));
}

3. 查找唯一数（LeetCode 实战）

题目：136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现一次的元素。

思路：利用归零律和交换律，所有出现两次的数异或后互相抵消为 0，最终结果就是唯一数。

$$a \oplus a \oplus b \oplus b \oplus \cdots \oplus x = 0 \oplus 0 \oplus \cdots \oplus x = x$$

pub fn single_number(nums: Vec<i32>) -> i32 {
    nums.into_iter().fold(0, |acc, x| acc ^ x)
}

fn main() {
    let nums = vec![4, 1, 2, 1, 2];
    println!("只出现一次的数字: {}", single_number(nums)); // 4
}

时间复杂度：$O(n)$，空间复杂度：$O(1)$。

左移（SHL）运算

运算符：<<

原理

左移运算将所有位向左移动指定位数，右边空出的位补 0。左移 n 位等价于乘以 $2^n$：

$$x \ll n = x \times 2^n$$

fn main() {
    let x: i32 = 5;
    let y = x << 1; // 5 * 2 = 10
    let z = x << 3; // 5 * 8 = 40
    println!("{} << 1 = {}", x, y); // 10
    println!("{} << 3 = {}", x, z); // 40

    // 快速计算 2 的幂
    println!("1 << 10 = {}", 1 << 10); // 1024
    println!("1 << 20 = {}", 1 << 20); // 1048576
}

溢出处理

左移时，如果移出的高位被丢弃，可能导致溢出。Rust 在 debug 模式下会检查整数溢出，在 release 模式下会自动回绕（wrapping）。

fn main() {
    let x: u8 = 128; // 10000000
    let y = x << 1;  // debug模式下panic，release模式下为0

    // 使用wrapping方法显式处理溢出
    let safe = x.wrapping_shl(1);
    println!("wrapping左移: {}", safe); // 0

    // 使用checked方法检查溢出
    match x.checked_shl(1) {
        Some(v) => println!("结果: {}", v),
        None => println!("左移溢出！"),
    }
}

右移（SHR）运算

运算符：>>

原理

右移运算将所有位向右移动指定位数。右移 n 位等价于整除 $2^n$：

$$x \gg n = \lfloor x / 2^n \rfloor$$

fn main() {
    // 偶数右移
    let x = 1024;
    let y = x >> 1; // 1024 / 2 = 512
    println!("{} >> 1 = {}", x, y); // 512

    // 奇数右移（向下取整）
    let x = 11;
    let y = x >> 1; // 11 / 2 = 5（截断小数部分）
    println!("{} >> 1 = {}", x, y); // 5

    // 快速除以 8
    let x = 1000;
    let y = x >> 3; // 1000 / 8 = 125
    println!("{} >> 3 = {}", x, y); // 125
}

算术右移 vs 逻辑右移

右移分为两种：

• 逻辑右移：高位补 0（用于无符号数）
• 算术右移：高位补符号位（用于有符号数，保持正负不变）

fn main() {
    // 无符号数：逻辑右移（高位补0）
    let x: u8 = 0b1000_0000; // 128
    let y = x >> 1;            // 0b0100_0000 = 64
    println!("无符号右移: {:08b} -> {:08b} ({} -> {})", x, y, x, y);

    // 有符号数：算术右移（高位补符号位）
    let x: i8 = -128; // 10000000（补码）
    let y = x >> 1;    // 11000000 = -64（高位补1）
    println!("有符号右移: {} -> {}", x, y);

    // 正数有符号右移（高位补0）
    let x: i8 = 127;  // 01111111
    let y = x >> 1;    // 00111111 = 63
    println!("正数有符号右移: {} -> {}", x, y);
}

Rust 中的位运算 trait

Rust 通过 std::ops 模块提供了一组 trait，允许自定义类型支持位运算操作符：

std::ops::BitAnd The bitwise AND operator &. std::ops::BitAndAssign The bitwise AND assignment operator &=. std::ops::BitOr The bitwise OR operator |. std::ops::BitOrAssign The bitwise OR assignment operator |=. std::ops::BitXor The bitwise XOR operator ^. std::ops::Not

use std::ops::{BitAnd, BitOr, BitXor, Not};

#[derive(Debug, Clone, Copy)]
struct Flags(u8);

impl BitAnd for Flags {
    type Output = Self;
    fn bitand(self, rhs: Self) -> Self::Output {
        Flags(self.0 & rhs.0)
    }
}

impl BitOr for Flags {
    type Output = Self;
    fn bitor(self, rhs: Self) -> Self::Output {
        Flags(self.0 | rhs.0)
    }
}

impl BitXor for Flags {
    type Output = Self;
    fn bitxor(self, rhs: Self) -> Self::Output {
        Flags(self.0 ^ rhs.0)
    }
}

impl Not for Flags {
    type Output = Self;
    fn not(self) -> Self::Output {
        Flags(!self.0)
    }
}

fn main() {
    let a = Flags(0b1100);
    let b = Flags(0b1010);
    println!("a & b = {:?}", a & b); // Flags(0b1000)
    println!("a | b = {:?}", a | b); // Flags(0b1110)
    println!("a ^ b = {:?}", a ^ b); // Flags(0b0110)
    println!("!a    = {:?}", !a);     // Flags(0b0011)
}

位运算综合技巧

获取、设置、清除、翻转特定位

以下是位操作的四大基本操作，是所有位运算技巧的基础：

/// 获取第n位的值（0或1）
fn get_bit(value: u32, n: usize) -> u32 {
    (value >> n) & 1
}

/// 设置第n位为1
fn set_bit(mut value: u32, n: usize) -> u32 {
    value | (1 << n)
}

/// 清除第n位为0
fn clear_bit(mut value: u32, n: usize) -> u32 {
    value & !(1 << n)
}

/// 翻转第n位
fn toggle_bit(mut value: u32, n: usize) -> u32 {
    value ^ (1 << n)
}

fn main() {
    let mut x: u32 = 0b1010_0101;

    println!("原始值: {:08b}", x);
    println!("第2位: {}", get_bit(x, 2));   // 1
    println!("设置第4位: {:08b}", set_bit(x, 4));    // 1011_0101
    println!("清除第0位: {:08b}", clear_bit(x, 0));  // 1010_0100
    println!("翻转第7位: {:08b}", toggle_bit(x, 7));  // 0010_0101
}

位段（Bit Field）

位段是一种将多个小数据打包到一个整数中的技术，常用于协议头、寄存器配置等场景。

/// IP协议头中的标志字段（3位）
#[derive(Debug)]
struct IpFlags {
    reserved: bool,   // 1位
    dont_fragment: bool, // 1位
    more_fragments: bool, // 1位
}

impl IpFlags {
    fn from_u8(value: u8) -> Self {
        IpFlags {
            reserved: (value & 0b100) != 0,
            dont_fragment: (value & 0b010) != 0,
            more_fragments: (value & 0b001) != 0,
        }
    }

    fn to_u8(&self) -> u8 {
        (self.reserved as u8) << 2
            | (self.dont_fragment as u8) << 1
            | (self.more_fragments as u8)
    }
}

fn main() {
    // DF=1, MF=0
    let flags = IpFlags {
        reserved: false,
        dont_fragment: true,
        more_fragments: false,
    };
    let packed = flags.to_u8();
    println!("打包: {:03b} = {}", packed, packed); // 010 = 2

    let unpacked = IpFlags::from_u8(0b110);
    println!("解包: {:?}", unpacked);
    // IpFlags { reserved: true, dont_fragment: true, more_fragments: false }
}

实战题目

191. 位1的个数

191. 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字为 ‘1’ 的个数。

pub fn hamming_weight(n: u32) -> u32 {
    let mut count = 0;
    let mut n = n;
    while n != 0 {
        n &= n - 1; // Brian Kernighan算法
        count += 1;
    }
    count
}

fn main() {
    println!("11(1011)中1的个数: {}", hamming_weight(11)); // 3
    println!("128中1的个数: {}", hamming_weight(128));      // 1
    println!("4294967293中1的个数: {}", hamming_weight(4294967293)); // 31
}

461. 汉明距离

461. 汉明距离

两个整数之间的汉明距离是指这两个数字二进制对应位不同的位置的数目。

pub fn hamming_distance(x: i32, y: i32) -> i32 {
    let xor = x ^ y; // 不同位为1
    let mut count = 0;
    let mut n = xor;
    while n != 0 {
        n &= n - 1;
        count += 1;
    }
    count
}

fn main() {
    println!("汉明距离(1,4): {}", hamming_distance(1, 4)); // 2
    // 1 = 0001, 4 = 0100, xor = 0101, 有2个1
}

更多实战题目

• 136. 只出现一次的数字
• 137. 只出现一次的数字 II
• 201. 数字范围按位与
• 231. 2的幂
• 260. 只出现一次的数字 III 和 剑指 Offer 56 - I. 数组中数字出现的次数 是同一题
• 338. 比特位计数

总结

练习题

1. 统计奇数位：给定一个 u32，统计其二进制中所有奇数位（第1、3、5…位）上 1 的个数。

2. 翻转所有位：不使用 ! 运算符，实现一个函数翻转一个 u32 的所有位。

3. 两数交换：实现一个函数，仅使用异或运算交换两个 i32 变量的值，并分析其局限性。

4. 位图实现：使用 u64 数组实现一个简单的位图（bitmap），支持 set、get、clear 操作，能表示 $[0, 1023]$ 范围内的整数集合。

5. 只出现一次的数字 II（LeetCode 137）：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现一次的元素。提示：考虑每一位的统计。