C语言复习 位运算 & | ^ ~ << >>

重点看1-8 学习运算方法

1. 先把数字写成二进制

我们先规定：

• a = 2
• b = 5

把它们写成二进制（为了直观，这里用 4 位表示；实际机器会用更多位）：

• a = 2 = 0010₂
• b = 5 = 0101₂

2. 按位与：a & b

规则： 对每一位做 AND 运算：
只有 1 & 1 = 1，其余都是 0。

  a = 0010
  b = 0101
a&b = 0000

• 0000₂ = 0₁₀

  a & b 的十进制值：0

3. 按位或：a | b

规则： 对每一位做 OR 运算：
只要有一位是 1，结果就是 1。

  a = 0010
  b = 0101
a|b = 0111

• 0111₂ = 7₁₀

  a | b 的十进制值：7

4. 按位异或：a ^ b

规则： 对每一位做 XOR 运算：
相同为 0，不同为 1（即 1^1=0，0^0=0，1^0=1，0^1=1）。

  a = 0010
  b = 0101
a^b = 0111

• 0111₂ = 7₁₀

a ^ b 的十进制值：7

5. 按位取反：~a

规则： 每一位 0 变 1，1 变 0。

但这里有个关键点：
计算机里的整数通常用补码（two's complement）表示。对于补码来说，有一个非常常用的恒等式：

因为x+~x=-1

例如x=2

0000 0010

+1111 1101

得到补码:1111 1111 为-1
-1 的反码应该是：
-1 的原码：1000 0001
-1 的反码：1111 1110
-1 的补码：1111 1111

~x = -(x + 1)

因此：

• ~2 = -(2 + 1) = -3

  ~a 的十进制值：-3

说明：在 C/C++ 等语言里，int 有固定位宽（如 32 位），但把结果按有符号补码解释时，~2 仍然是 -3。在 Python 里整数是“无限位补码”语义，也同样得到 -3。

6. 左移：a << 2

规则： 左移相当于乘以 2^k（在不溢出的前提下）。
a << 2 表示把 a 的二进制整体左移 2 位，右侧补 0。

a      = 0010
a<<2   = 1000

• 1000₂ = 8₁₀

  a << 2 的十进制值：8

7. 右移：a >> 2

规则： 右移相当于整除 2^k（对非负数等价于向下取整）。
a >> 2 表示把二进制整体右移 2 位。

a      = 0010
a>>2   = 0000

• 0000₂ = 0₁₀

  a >> 2 的十进制值：0

8. 例题 15：最终答案汇总（十进制）

已知 a = 2, b = 5，计算以下式子的十进制值：

• a & b 的十进值是：( 0 )
• a | b 的十进值是：( 7 )
• a ^ b 的十进值是：( 7 )
• ~a 的十进值是：( -3 )
• a << 2 的十进值是：( 8 )
• a >> 2 的十进值是：( 0 )

9. 小结：什么时候用位运算？

• 掩码/权限位：例如 read=1, write=2, exec=4，用 | 组合权限，用 & 检查权限
• 快速乘除 2 的幂：x<<k、x>>k（注意溢出与符号）
• 状态压缩：用一个整数的不同 bit 存多个布尔值
• 算法技巧：如异或找“只出现一次”的数、lowbit（x & -x）等

10. 符号位、溢出、逻辑右移 vs 算术右移

这部分是很多人第一次写位运算时最容易踩坑的地方：同一段代码在不同语言/不同类型（有符号/无符号）下，结果可能不一样。

10.1 符号位与补码

大多数现代语言/CPU 对有符号整数使用补码表示：

• 最高位通常是符号位（1 表示负数，0 表示非负数）
• 负数的补码 = “正数按位取反 + 1”
• 常用恒等式：~x = -(x + 1)（你前面的 ~2 = -3 就来自这里）

为什么会影响位运算？
因为当你对一个负数进行 & | ^ ~ >> 时，实际是在它的补码表示上操作（包含符号位）。

10.2 溢出：位宽固定 vs 无限精度

（1）固定位宽语言：C/C++/Java 等

在 C/C++/Java 里，int、long 等类型是固定位宽的（例如 32 位、64 位），所以：

• ~a 会把该位宽范围内的每一位都翻转
• a << k 可能溢出（高位被挤掉）
• 有符号溢出在不同语言里处理方式不同：
  • Java：溢出按固定位宽截断（模 2^N），行为确定
  • C/C++：某些溢出或移位情况可能是未定义行为（UB）或实现定义，要特别小心

（2）Python：整数是“无限精度”

Python 的 int 是任意精度，不会出现“位宽截断”意义上的溢出，但它仍按补码语义定义 ~ 和右移：

• ~2 == -3
• -1 >> 1 == -1（会一直补 1）

10.3 左移的坑：<< 不是永远等价于乘法

对非负数且不溢出时，x << k 等价于 x * 2^k。但以下情况要谨慎：

• 在固定位宽语言里，左移可能导致高位丢失（溢出）
• 在 C/C++ 中：
  • 左移位数 k 如果 >= 类型位宽，是未定义行为（UB）
  • 对负数做左移，通常也不是你想要的，可能是 UB/实现定义

建议：

• 在 C/C++ 中做位移前先确保类型为无符号（unsigned）并限制移位范围
• 或明确使用更宽的类型（例如 uint64_t）来避免溢出

10.4 右移：逻辑右移 vs 算术右移（最重要的差异）

右移 >> 有两种“补位方式”：

（1）逻辑右移（Logical Right Shift）

• 右移后左侧补 0
• 常用于无符号数
• 直观理解：把二进制当成“纯位串”处理

例子（以 8 位举例）：

10000000 >>> 1  = 01000000

（2）算术右移（Arithmetic Right Shift）

• 右移后左侧补符号位
  • 正数补 0
  • 负数补 1
• 保持符号，常用于有符号数
• 很多语言的 >> 对有符号类型就是算术右移

例子（8 位补码，-128 是 10000000）：

10000000 >> 1  = 11000000   （补 1）

10.5 各语言里 >> 到底是哪一种？

Java / JavaScript

• >>：算术右移
• >>>：逻辑右移（无符号右移） （非常明确）

C / C++

• 对无符号整数：>> 基本等价于逻辑右移（补 0）
• 对有符号负数：>> 是实现定义（多数平台是算术右移，但别依赖它）

想要“逻辑右移”效果：把数转成无符号再右移。

Python

• >>：对负数也是算术右移（补 1）
• Python 没有单独的 >>> 运算符
  如果你想做“逻辑右移”（按固定位宽）可以用掩码模拟：

例如，按 32 位做逻辑右移：

x = -3
logical = (x & 0xFFFFFFFF) >> 1

10.6 一个直观对比：同样的 -3，右移 1 位会怎样？

以 8 位补码举例（仅为演示）：

• -3 的 8 位补码：11111101

算术右移（补 1）

11111101 >> 1 = 11111110   （仍是负数）

逻辑右移（补 0）

11111101 >>> 1 = 01111110  （变成正数位串）

这就是为什么右移一定要明确“你想把它当成有符号数还是纯位串”。