Course playlist

位运算完全教程

掌握与(&)、或(|)、非(~)、异或(^)、左移(<<)、右移(>>)的基本使用方法及原理

位运算简介

位运算是对整数在二进制表示下的位进行操作的运算。这些运算直接在二进制位级别上操作，因此执行速度非常快，是底层编程、系统开发和算法优化中的重要工具。

为什么需要位运算？

  • 高效性：位运算是处理器直接支持的最基本操作，速度极快
  • 节省空间：可以用单个整数的不同位存储多个布尔值
  • 算法优化：许多算法问题可以通过位运算巧妙解决
  • 底层开发：操作系统、驱动程序、嵌入式系统开发中广泛应用

位运算主要应用于：权限控制、状态标记、数据压缩、加密算法、图形处理、游戏开发等领域。

学习前提：理解位运算需要掌握二进制表示法。所有位运算都是基于二进制位的操作，每个位只能是0或1。

与运算 (&)

定义：与运算对两个操作数的每一位进行逻辑与操作。只有当两个对应位都为1时，结果位才为1，否则为0。

与运算的真值表

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

与运算的特性

  • 清零特定位：用0与任何位相与，结果都是0
  • 保留特定位：用1与任何位相与，保留原值
  • 判断奇偶性：n & 1 结果为1表示n是奇数，0表示n是偶数
  • 提取最低位：n & -n 可以提取n的最低有效位

与运算示例

例子1：5 & 3 的计算

5 的二进制：0101
3 的二进制：0011
按位与运算：0001
结果：1 (十进制)

例子2：使用与运算判断奇偶性

10 的二进制：1010
1 的二进制：0001
10 & 1 = 0000 = 0 (偶数)

7 的二进制：0111
1 的二进制：0001
7 & 1 = 0001 = 1 (奇数)

应用场景：

  • 权限检查：检查用户是否具有特定权限
  • 掩码操作：提取或清除数据中的特定位
  • 判断整数奇偶性

或运算 (|)

定义：或运算对两个操作数的每一位进行逻辑或操作。只要两个对应位中有一个为1，结果位就为1，否则为0。

或运算的真值表

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

或运算的特性

  • 设置特定位为1：用1与任何位相或，结果都是1
  • 保留特定位：用0与任何位相或，保留原值
  • 组合标志位：将多个标志位合并到一个整数中
  • 向上取整到2的幂：n | (n-1) 可以将n向上取整到最近的2的幂减1

或运算示例

例子1：5 | 3 的计算

5 的二进制：0101
3 的二进制：0011
按位或运算：0111
结果：7 (十进制)

例子2：使用或运算设置权限标志

定义权限：读=1(001)，写=2(010)，执行=4(100)
用户权限：读写 = 读 | 写 = 001 | 010 = 011 = 3
所有权限：读 | 写 | 执行 = 001 | 010 | 100 = 111 = 7
编程技巧：或运算常用于组合多个选项或标志位。在Linux文件权限、Windows API标志位等场景中广泛应用。

非运算 (~)

定义：非运算是单目运算符，对操作数的每一位进行取反操作。0变为1，1变为0。在补码表示中，~n = -(n+1)。

非运算的特性

  • 位取反：每个二进制位取反（0变1，1变0）
  • 补码关系：在补码表示中，~n = -(n+1)
  • 创建掩码：常用于创建位掩码
  • 交换符号：~n + 1 = -n（对于整数）

非运算示例

例子1：~5 的计算（假设8位）

5 的二进制：00000101
按位取反：11111010
这是补码表示，转换为十进制：先减1得11111001，取反得00000110=6，加负号得-6
结果：-6 (十进制，符合 ~n = -(n+1) 规则)

例子2：使用非运算创建掩码

要保留低4位，清除高4位：mask = ~(0xF0) = ~(11110000) = 00001111
数值 0xAB (10101011) & mask = 10101011 & 00001111 = 00001011 = 0x0B

注意事项：

  • 非运算的结果取决于整数的位数（8位、16位、32位、64位）
  • 在不同编程语言中，非运算的行为可能略有不同
  • 非运算经常与与运算结合使用来清除特定位

异或运算 (^)

定义：异或运算对两个操作数的每一位进行逻辑异或操作。当两个对应位不同时，结果位为1，相同时为0。

异或运算的真值表

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

异或运算的特性

  • 交换律：a ^ b = b ^ a
  • 结合律：(a ^ b) ^ c = a ^ (b ^ c)
  • 自反性：a ^ a = 0
  • 与0异或：a ^ 0 = a
  • 交换两个数：a ^= b; b ^= a; a ^= b; 可以不用临时变量交换两个整数

异或运算示例

例子1：5 ^ 3 的计算

5 的二进制：0101
3 的二进制：0011
按位异或：0110
结果：6 (十进制)

例子2：使用异或交换两个数

设 a=5(0101), b=3(0011)
a = a ^ b = 0101 ^ 0011 = 0110 (6)
b = b ^ a = 0011 ^ 0110 = 0101 (5) ← b现在等于原来的a
a = a ^ b = 0110 ^ 0101 = 0011 (3) ← a现在等于原来的b
结果：a=3, b=5，交换完成！

应用场景：

  • 加密算法：简单加密/解密
  • 校验和：数据完整性检查
  • 找不同：在一组成对出现的数字中找出单独出现的数字
  • 图形处理：实现反色效果

移位运算 (<< 和 >>)

定义：移位运算将二进制数的所有位向左或向右移动指定的位数。左移(<<)在右侧补0，右移(>>)的行为取决于具体实现（逻辑右移或算术右移）。

左移运算 (<<)

  • 定义：将所有位向左移动，右侧补0
  • 数学意义：n << m 相当于 n × 2ᵐ
  • 溢出：左移可能导致高位丢失，产生溢出
  • 快速乘法：左移1位相当于乘以2

右移运算 (>>)

  • 逻辑右移：左侧补0，不考虑符号位（无符号数）
  • 算术右移：左侧补符号位（有符号数，保持符号不变）
  • 数学意义：n >> m 相当于 n ÷ 2ᵐ（向零取整）
  • 快速除法：右移1位相当于除以2（向下取整）

移位运算示例

例子1：5 << 2 的计算

5 的二进制：0101
左移2位：010100 （右侧补两个0）
结果：20 (十进制，5 × 4 = 20)

例子2：20 >> 2 的计算

20 的二进制：10100
右移2位：00101 （左侧补两个0）
结果：5 (十进制，20 ÷ 4 = 5)

例子3：-8 >> 2 的计算（算术右移）

-8 的二进制（8位补码）：11111000
算术右移2位：11111110 （左侧补两个符号位1）
结果：-2 (十进制，-8 ÷ 4 = -2)

应用场景：

  • 快速乘除：乘以或除以2的幂次
  • 位字段操作：提取或设置特定位
  • 颜色操作：提取RGB颜色分量
  • 哈希算法：许多哈希函数使用移位运算

位运算实战应用

1. 权限控制系统

使用位运算实现简单的权限控制：

定义权限：读=1(001)，写=2(010)，执行=4(100)
用户权限 = 读 | 写 = 001 | 010 = 011 = 3
检查是否有读权限：用户权限 & 读 = 011 & 001 = 001 ≠ 0 → 有权限
检查是否有执行权限：用户权限 & 执行 = 011 & 100 = 000 = 0 → 无权限
添加执行权限：用户权限 | 执行 = 011 | 100 = 111 = 7
移除写权限：用户权限 & ~写 = 111 & ~010 = 111 & 101 = 101 = 5

2. 判断2的幂

判断一个正整数n是否为2的幂：

2的幂的二进制表示：只有1个1，后面全是0
例如：1(001), 2(010), 4(100), 8(1000), 16(10000)
技巧：n & (n-1) == 0 且 n > 0
验证：8(1000) & 7(0111) = 0000 = 0 → 8是2的幂
验证：6(0110) & 5(0101) = 0100 ≠ 0 → 6不是2的幂

3. 统计二进制中1的个数

使用n & (n-1)技巧：

原理：n & (n-1) 会清除n的最低有效位1
示例：统计13(1101)中1的个数
13(1101) & 12(1100) = 1100 (清除最低位的1)
12(1100) & 11(1011) = 1000 (清除最低位的1)
8(1000) & 7(0111) = 0000 (清除最低位的1)
共执行了3次操作，所以有3个1

位运算测试题

1. 表达式 12 & 5 的结果是多少？

2. 下列哪个表达式可以将整数n的最低有效位1清零？

3. 不使用临时变量，交换a和b的值，正确的位运算方法是什么？

位运算计算器

使用下面的工具进行位运算计算：

结果将显示在这里
题目 对/错/率 难度 记录 通过
姓名 分数 提交时间 操作