C/C++ 里所有位运算（移位 >> <<、& | ^ ~），全部是对【补码】进行操作，不是原码。计算机内存里整数永远以补码形式存放，位运算直接操作内存里的二进制比特（补码）。

想要搞懂"补码为什么是补码"，可以先看《原码、反码、补码：为什么计算机只用"加法"就能做减法》那一篇。

一、左移 <<

向左移动一位，移出去的位舍去，右边补 0。

1
2
int a = 26;
int b = a << 1;        // 52

直观理解：a << n 相当于 a * 2^n（在 不溢出的前提下）。

1.1 负数左移也要算补码

1
2
-26 的原码：10011010
-26 的补码：11100110

-26 << 1：

1
2
补码左移：11100110 → 11001100
（最高位的 1 移出去，最低位补 0）

把 11001100 当补码读回十进制：−52。

左移没有"算术 / 逻辑"之分——不管正负数，移出去的位都丢，右边一律补 0。

二、右移 >>

向右移动一位，但正数和负数的补位规则不一样：

类型 左空出来的位补什么
正数（含 unsigned） 补 0（逻辑右移）
负数（带符号 int） 补 1（算术右移）

2.1 正数右移

1
2
26 >> 1 = 13
13 >> 1 = 6
1
2
26 的二进制：0001 1010
右移一位：   0000 1101 = 13

直观理解：a >> n 相当于 a / 2^n（向下取整）。

2.2 负数右移

1
2
-26 的补码：11100110
右移一位：  11110011   ← 左侧补 1（因为是负数）

把 11110011 当补码读回：(−26) >> 1 = −13（向下取整的除以 2）。

正数 = 逻辑右移；负数 = 算术右移——这是 C/C++ 标准规定。

2.3 unsigned 一律逻辑右移

1
2
unsigned int a = 0xF0000000;
a >> 4;            // 0x0F000000，左侧一定补 0

所以位运算 / 哈希 / 算法竞赛里要用到移位的，统一用 unsigned——避免负数算术右移带来的"奇怪符号位"问题。

三、常用公式

操作 等价于 适用前提
a << n a * 2^n 不溢出
a >> n a / 2^n（向下取整） 正数 / unsigned
1 << k 第 k 位为 1 表示「掩码」
a & (1 << k) 取 a 的第 k 位 判断某一位是 0 还是 1
`a (1 << k)` 把 a 的第 k 位设为 1 不影响其他位
a & ~(1 << k) 把 a 的第 k 位设为 0

四、典型应用

4.1 快速乘 / 除 2 的幂

1
2
3
int a = 100;
int b = a << 3;       // a * 8，比 a * 8 快
int c = a >> 2;       // a / 4（向下取整）

4.2 位掩码（取位 / 设位）

1
2
3
4
5
6
7
8
9
10
11
// 第 k 位：a 是 1 还是 0？
bool bit_k = (a >> k) & 1;

// 把第 k 位设为 1
a |= (1 << k);

// 把第 k 位设为 0
a &= ~(1 << k);

// 把第 k 位取反
a ^= (1 << k);

4.3 取整数二进制长度（竞赛常考）

正整数 x 的二进制位数 = ⌊log2(x)⌋ + 1。可以写：

1
2
3
int bitlen(int x) {
    return 32 - __builtin_clz(x);      // GCC 内建，正数专用
}

__builtin_clz = count leading zeros（前置 0 个数）；32 位机用 __builtin_clz，64 位机用 __builtin_clzll。

五、易错点清单

  1. 左移负数位：a << -1 是 UB（未定义行为）。n 必须 ≥ 0。
  2. a << n 溢出：左移结果超过类型范围直接丢弃高位。C/C++ 不会自动提升，所以大数左移前先 cast 到 long long 或 unsigned long long。
  3. 右移负数补 1：很多人以为右移就是"除以 2"，但对负数来说算术右移会保持负号。这在算法竞赛里是常见 bug——(-3) >> 1 == -2，不是 -1。
  4. unsigned 右移才一定是逻辑右移：带符号类型右移负数走算术规则，行为由实现定义（虽然主流编译器都是补 1，但写代码别依赖）。
  5. 移位优先级低：a + b << 1 实际是 (a + b) << 1，没问题；但 a & b == 0 实际是 a & (b == 0)，写成 == 之前用括号更稳。

六、极简速记

操作 含义
a << n 乘以 $2^n$（左移都补 0）
a >> n 除以 $2^n$（向下取整）；负数算术右移补 1
1 << k 第 k 位的掩码
(a >> k) & 1 取第 k 位
`a \ (1 << k)` 第 k 位设 1
a & ~(1 << k) 第 k 位设 0
a ^ (1 << k) 第 k 位取反

七、小结

  • 位移运算直接操作补码；
  • 左移永远补 0，右移按符号补位：正数 / unsigned 补 0，负数补 1；
  • 想要确定性的"逻辑右移" → 用 unsigned；
  • 移位的本质：左移 = 乘 $2^n$、右移 = 除 $2^n$（向下取整）；
  • 位掩码三件套：a | (1<<k) 设 1、a & ~(1<<k) 设 0、a ^ (1<<k) 取反。