位运算演示教程

理解位运算的原理与应用

1. 什么是位运算？

位运算是对整数的二进制位进行操作的运算。与普通算术运算不同，位运算直接在二进制级别上操作，效率极高。

为什么学习位运算？
  • ⚡ 运算速度极快，通常比算术运算快 10-100 倍
  • 💾 内存效率高，可以节省存储空间
  • 🔧 在算法、加密、图形处理等领域广泛应用
  • 📊 是理解计算机底层原理的基础

2. 位运算符概览

运算符 名称 符号 描述 示例
AND 按位与 & 两个位都为 1 时结果为 1 5 & 3 = 1
OR 按位或 | 两个位任意一个为 1 时结果为 1 5 | 3 = 7
XOR 按位异或 ^ 两个位不同时结果为 1 5 ^ 3 = 6
NOT 按位取反 ~ 将每个位取反（0→1，1→0） ~5 = -6
LEFT 左移 << 将所有位向左移动 n 位 5 << 1 = 10
RIGHT 右移 >> 将所有位向右移动 n 位 5 >> 1 = 2

3. 按位与 AND (&)

真值表

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

示例：5 & 3 = ?

5:
0
1
0
1
3:
0
1
1
1
&
&
&
&
&
结果:
0
0
0
1
常见用途：
  • 检查特定位是否为 1：if (x & mask) { ... }
  • 清零特定位：x = x & ~mask;
  • 判断奇偶：x & 1 == 0 为偶数
  • 取模 2n：x % 8 等价于 x & 7

4. 按位或 OR (|)

真值表

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

示例：5 | 3 = ?

5:
0
1
0
1
3:
0
1
1
1
|
|
|
|
|
结果:
0
1
1
1
常见用途：
  • 设置特定位为 1：x = x | mask;
  • 合并标志位：flags |= READ | WRITE;
  • 设置权限、状态等组合值

5. 按位异或 XOR (^)

真值表

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

示例：5 ^ 3 = ?

5:
0
1
0
1
3:
0
1
1
1
^
^
^
^
^
结果:
0
0
1
0
重要性质：
  • A ^ 0 = A（与 0 异或保持不变）
  • A ^ A = 0（自己与自己异或得 0）
  • A ^ B ^ A = B（可逆性）
  • A ^ B ^ C = A ^ (B ^ C)（满足交换律和结合律）
常见用途：
  • 交换两个变量：a ^= b; b ^= a; a ^= b;
  • 翻转特定位：x ^= mask;
  • 简单加密：encrypted = data ^ key;
  • 查找只出现一次的数（其他数都出现两次）

6. 按位取反 NOT (~)

5:
0
1
0
1
0
0
0
0
↓ ~
~5:
1
0
1
0
1
1
1
1
⚠️ 注意事项：

~5 在计算机中不是 -6 的原码，而是 -6 的补码！

  • 5 的原码：00000101
  • ~5 的结果：11111010（这是 -6 的补码）
  • 将补码转回原码：取反加1 → 10000110 = -6
常见用途：
  • 取反掩码：~mask 用于清零除指定位外的所有位
  • 求相反数：-x = ~x + 1
  • 查找补集

7. 左移与右移 (<<,>>)

左移 <<

将所有位向左移动，右边补 0

5:
0
0
1
0
1
↓ << 2
结果:
1
0
1
0
0
x << n = x × 2n
5 << 2 = 5 × 4 = 20

右移 >>

将所有位向右移动，左边补符号位（算术右移）或 0（逻辑右移）

20:
1
0
1
0
0
↓ >> 2
结果:
0
1
0
0
0
x >> n = x ÷ 2n（向下取整）
20 >> 2 = 20 ÷ 4 = 5
常见用途：
  • 快速乘除 2 的幂次：x << 3 比 x * 8 快
  • 提取特定位段：(x >> n) & mask
  • 打包数据到更小的类型中

8. 位运算实战案例

1. 判断奇偶

// 传统方法
bool isOdd(int x) {
    return x % 2 != 0;
}

// 位运算方法（更快）
bool isOdd(int x) {
    return x & 1;
}

原理：最低位为 1 则是奇数

2. 交换两数

// 不使用临时变量
void swap(int &a, int &b) {
    a ^= b;
    b ^= a;
    a ^= b;
}

// 验证：
// a = 5, b = 3
// a = 5 ^ 3 = 6
// b = 6 ^ 5 = 3
// a = 6 ^ 3 = 5

3. 找出唯一数

// 数组中只有一个数出现一次
int findUnique(vector<int> nums) {
    int result = 0;
    for (int x : nums) {
        result ^= x;
    }
    return result;
}

原理：x ^ x = 0，成对出现的数抵消

4. 判断2的幂

bool isPowerOfTwo(int x) {
    return x > 0 && (x & (x - 1)) == 0;
}

原理：2的幂次二进制只有1个1

5. 计算汉明距离

int hammingDistance(int a, int b) {
    int xor = a ^ b;
    int count = 0;
    while (xor) {
        count += xor & 1;
        xor >>= 1;
    }
    return count;
}

两个数二进制不同位的个数

6. 权限管理

const int READ = 1;    // 0001
const int WRITE = 2;   // 0010
const int EXECUTE = 4; // 0100

// 设置权限
int permissions = READ | WRITE;

// 检查权限
if (permissions & READ) {
    // 有读权限
}

// 移除权限
permissions &= ~WRITE;

9. 交互式计算演示

选择运算符开始计算

10. 进阶技巧

快速计算 2 的幂次

1 << 0  = 1    // 2^0
1 << 1  = 2    // 2^1
1 << 2  = 4    // 2^2
1 << n  = 2^n  // 2^n

获取最低位的 1

int lowestOne = x & -x;
// 例如：x = 12 (1100)
// x & -x = 4 (0100)

去掉最低位的 1

int removeLowest = x & (x - 1);
// 例如：x = 12 (1100)
// x & (x-1) = 8 (1000)

统计 1 的个数（Brian Kernighan 算法）

int countOnes(int x) {
    int count = 0;
    while (x) {
        x &= (x - 1);
        count++;
    }
    return count;
}

反转二进制位

uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>= 1;
    }
    return result;
}