入门：六种位运算、异或性质与补码
基于通用算法概念 · 核于 2026-07
速查
- 六种位运算：与
&（同 1 才 1）、或|（有 1 即 1）、非~（按位取反）、异或^（不同为 1）、左移<<（高位补 0，等价 ×2）、右移>>（正数高位补 0，负数补 1 算术右移，等价 ÷2）——全部按位独立运算，O(1)。 - 异或（XOR）三大性质：自反性
a ^ a = 0（相同抵消）、恒等性a ^ 0 = a（与 0 不变）、交换结合a ^ b = b ^ a、(a^b)^c = a^(b^c)——这三个性质是「找单元素」「不用临时变量交换」「抵消成对元素」的代数根基。 - 移位的乘除含义：
a << k等价a × 2^k，a >> k（正数）等价a / 2^k（向下取整）——所以a << 1= ×2、a >> 1= ÷2，乘除 2 的幂用移位比用乘除快。 - 补码（Two's Complement）：计算机用补码表示负数——
-n的位模式 =~n + 1（按位取反再加 1）。-1在 32 位下是全 1（0xFFFFFFFF），这就是为什么n & (-1) = n、n & (-n)能取出最低位的 1。 - JS 位运算是 32 位有符号：JS 在做位运算前会把操作数转成 32 位有符号整数（
ToInt32），大数（>2³¹）被截断，~、>>的结果可能是负数——这是 JS 位运算最大的坑，大数场景要用BigInt。 - 异或 = 无进位加法：
a ^ b的结果恰好是「不考虑进位时 a+b 的逐位和」（因为 0+0=0、0+1=1、1+0=1、1+1=10 进位本位变 0，与异或真值表完全一致）——这是「不用加减法求和」的原理起点。 - 位运算优先级低于比较：
& | ^ << >>的优先级都低于==<>等比较符（也低于加减）——n & 1 == 0实际是n & (1==0)，必须写(n & 1) === 0，这是最高频的位运算 bug。 - O(1) 且常数极小：所有位运算都是单条 CPU 指令，无分支无访存——但现代编译器常自动把
%2、/2、*2优化成移位，手写不一定更快，可读性更重要。 - 进阶顺序：常用位运算技巧 → 经典应用与位掩码 → 参考。
一、六种位运算：按位独立运算
位运算把整数看成二进制位串，每位独立做逻辑运算。以 8 位为例看 6 种运算（a = 0b1100 = 12，b = 0b1010 = 10）：
| 运算 | 符号 | 规则 | a op b | 结果 |
|---|---|---|---|---|
| 与 AND | & | 同 1 才 1 | 1100 & 1010 | 1000 = 8 |
| 或 OR | | | 有 1 即 1 | 1100 | 1010 | 1110 = 14 |
| 非 NOT | ~ | 按位取反（一元） | ~1100（8 位） | ...0011 = -13 |
| 异或 XOR | ^ | 不同为 1 | 1100 ^ 1010 | 0110 = 6 |
| 左移 | << | 整体左移，低位补 0 | 1100 << 1 | 11000 = 24 |
| 右移 | >> | 整体右移，正数高位补 0 | 1100 >> 1 | 0110 = 6 |
记忆诀窍：与（&）用来「遮罩/清零」（与 0 得 0、与 1 保留），或（|）用来「置位」（与 1 得 1、与 0 保留），异或（^）用来「翻转」（与 1 翻转、与 0 保留）。这三个用途是所有位运算技巧的出发点。
二、异或的自反性：成对抵消的代数根基
异或是位运算里最有「代数味」的操作，它有三大核心性质：
- 自反性：
a ^ a = 0——任何数与自身异或结果为 0（相同位抵消）。 - 恒等性：
a ^ 0 = a——任何数与 0 异或保持不变。 - 交换律 + 结合律：
a ^ b = b ^ a、(a ^ b) ^ c = a ^ (b ^ c)——异或的顺序和分组不影响结果。
由这三条派生出两个高频推论：
一连串异或，成对的数自动抵消：
a ^ b ^ a ^ c ^ b = (a^a) ^ (b^b) ^ c = 0 ^ 0 ^ c = c——这就是「只出现一次的数字」的原理：把数组全异或起来，出现两次的数两两抵消，剩下那个只出现一次的。不用临时变量交换两数：
jsa ^= b; // a = a ^ b b ^= a; // b = b ^ (a ^ b) = a a ^= b; // a = (a ^ b) ^ a = b推导：第二步
b ^ a（此时 a 已是a^b）=b ^ a ^ b = a，第三步同理还原成 b。注意它要求 a、b 是不同变量（同一变量会变 0）。
三、移位的乘除含义：把乘除 2^k 变成移位
左移 a << k 等价于 a × 2^k（高位补 0，低位补 0）；右移 a >> k 对正数等价于 a / 2^k 向下取整（低位丢弃）。
a << 1 == a * 2 a << 2 == a * 4 a << k == a * 2^k
a >> 1 == Math.floor(a / 2) a >> 2 == a / 4（向下取整）- 乘除 2 的幂用移位更快：历史上
* 2比<< 1慢，所以老代码爱用移位；现代编译器自动优化，a * 2和a << 1生成的机器码一样——可读性优先，写* 2更清楚，写<< 1多见于底层/位运算密集的代码。 - 取某位：
(a >> k) & 1——先把第 k 位移到最低位，再与 1 取出。 - 右移对负数：算术右移（Java/C++/JS 的
>>）高位补符号位（负数补 1），所以-8 >> 1 = -4；若要无符号右移（高位补 0）用 JS 的>>>或 Java 的>>>。
四、补码：负数为什么这么表示
计算机用**补码（Two's Complement）**表示负数。对一个 n 位整数，-a 的补码 = (~a + 1)（按位取反再加 1），并丢弃溢出的最高位。
以 4 位为例看 -5 怎么表示（5 = 0101）：
5: 0101 取反 ~5: 1010 +1: 1011 = -5
-5: 1011 取反 ~(-5): 0100 +1: 0101 = 5 （互逆）补码有几个关键推论：
-1是全 1：32 位下-1 = 0xFFFFFFFF（全 1）。所以n & (-1) = n（与全 1 不变）、n | (-1) = -1（或全 1 得全 1）、n ^ (-1) = ~n（异或全 1 = 取反）。n & (-n)取出最低位的 1：这是 lowbit 技巧的原理。因为-n = ~n + 1，取反让最低位的 1 及其以下的 0 全翻转，再 +1 进位回来，恰好只在最低位 1 的位置保留 1，更高位全与原数相反——相与后只剩那一位。- 范围：n 位补码能表示
-2^(n-1)到2^(n-1) - 1（32 位：-2147483648到2147483647）。最小负数-2^(n-1)没有对应的正数，取相反数会溢出（-INT_MIN == INT_MIN）。
五、JS 的位运算是 32 位有符号
JavaScript 的位运算有一个大坑：操作数会先被 ToInt32 转成 32 位有符号整数，结果也是 32 位有符号。这带来两个后果：
- 大数被截断：
(2 ** 31) & 1不是0而是0（对），但(2 ** 32 + 1) | 0是1（被截到 32 位）。任何超过2^31 - 1的数做位运算都会失真。 ~和>>可能产生负数：~5 === -6（32 位取反后最高位变 1）；(1 << 31) === -2147483648（左移到符号位变负数）。
~5 // -6（不是 4294967290）
(1 << 31) // -2147483648（符号位被置 1，变负数）
2 ** 32 | 0 // 0（被截断到 32 位）Python 没有这个问题——Python 整数是任意精度，~5 = -6（补码逻辑一致但无 32 位截断），1 << 100 是个真的大数。所以跨语言搬位运算代码时，JS 的 32 位截断要特别当心，大数场景用 BigInt（但 BigInt 不支持 ~、<<，只支持 &|^）。
下一步
理解了六种位运算、异或性质与补码后，下一步是把它们组合成高频技巧——判断奇偶、不用临时变量交换、n&(n-1) 去最低位 1、lowbit、判断 2 的幂、取设清翻某位，见常用位运算技巧。