位运算实战

位运算符

运算符	名称	运算规则	记忆口诀
`&`	按位与	两个二进制位都为1时结果为1，否则为0	全1出1，有0出0
`\|`	按位或	两个二进制位都为0时结果为0，否则为1	有1出1，全0出0
`^`	按位异或	两个二进制位相同时结果为0，不同时结果为1	相同为0，不同为1
`~`	按位取反	单目运算符，0变1，1变0（包含符号位）	全部翻转
`<<`	左移	高位丢弃，低位补0	乘 $2^{n}$ 2n
`>>`	右移	低位丢弃，高位补符号位（算术右移）	除 $2^{n}$ 2n（向下取整）

规则与运算

按位与（&）：清零与截取

核心性质：

x & 1：取x的最低位（判断奇偶）
x & (~0 << n)：将低n位清零（右侧低位左侧高位）
与0运算：x & 0 = 0

按位或（|）：置1操作

核心性质：

x | (1 << n)：将第n位设为1
或0不改变：x | 0 = x

按位异或（^）：不进位加法与交换

核心性质（高频考点）：

x ^ x = 0（自身异或得0）
x ^ 0 = x（与0异或不变）
x ^ y ^ x = y（自反性）
异或满足交换律和结合律

交换算法

    // 临时变量交换
    int temp = a;
    a = b;
    b = temp;

    // 异或交换（三步异或，只适用整数）
    a = a ^ b;  // 第一步：a = a ^ b
    b = a ^ b;  // 第二步：b = (a ^ b) ^ b = a
    a = a ^ b;  // 第三步：a = (a ^ b) ^ a = b

    // 加减法交换（可能有溢出风险）
    a = a + b;  // 第一步：a = a + b
    b = a - b;  // 第二步：b = (a+b) - b = a
    a = a - b;  // 第三步：a = (a+b) - a = b

左移（<<）与右移（>>）：乘除2的幂

左移规则：

x << n = $x \times 2^{n}$
高位丢弃，低位补0
可能改变符号位（溢出）

右移规则（重点！）：

正数右移：高位补0（逻辑右移）
负数右移：高位补1（算术右移，保持符号位）
x >> n = $⌊ x \div 2^{n} ⌋$ （向下取整）

常用公式及用法

恒等式

操作	结果	应用场景
`x & x`	x	—
`x \| x`	x	—
`x ^ x`	0	判断相等、去重
`x & 0`	0	清零
`x \| 0`	x	—
`x ^ 0`	x	—
`x & 1`	x的最低位	判断奇偶
`x << n`	$x \times 2^{n}$	快速乘
`x >> n`	$⌊ x \div 2^{n} ⌋$	快速除

判断奇偶

if (a & 1) {
    // a是奇数
} else {
    // a是偶数
}

判断相等

if ((a ^ b) == 0) {
    // a == b
}

运算符优先级

从高到低：

~（取反）—— 同!、++等单目运算符
<<、>>（移位）—— 比加减法低
&（与）
^（异或）
|（或）
&=, ^=, |=, <<=, >>=（复合赋值）

常见陷阱

陷阱	错误写法	正确写法
优先级混淆	`x & 3 == 1`	`(x & 3) == 1`
负数的右移	误以为负数右移补0	负数右移补1（算术右移）
对有符号数左移溢出	`int << 31`可能变成负数	注意范围
取反符号位	以为`~`不影响符号位	`~`对所有位取反，包括符号位