位运算技巧总结

1. 位运算的性质

1. x对其自身运算
   x & x = x
   x | x = x
   x ^ x = 0

2. x与0运算
   x & 0 = 0
   x | 0 = x
   x ^ 0 = x

3. x与0运算
   x & (0) = x
   x | (0) = ~0
   x ^ (0) = ~x

4. 异或的性质
   x ^ 0 = x x ^ x = 0（常用）
   交换率：x ^ y = y ^ x
   结合律：(x ^ y) ^ z = x ^ (y ^ z)
   自反性：x ^ y ^ y = x（常用）

2. 常用技巧

1. 判断奇偶（x & 1）
2. 判断符号是否相同（x ^ b >= 0）
3. 取出第i位（x & (1 << (i - 1))）
4. i位置1（x | (1 << (i - 1))） 置0（x & ~(1 << (i - 1))） 反转（x ^ (1 << (i - 1))）
5. 取最右侧1（x & (~x + 1) 或 x & -x）
6. 消去最右侧的1（x & (x - 1)）
7. 判断一个数是否为2的幂 （x & (x - 1) == 0?）

3. 例题

• 通过异或运算交换两个数
• 136. 只出现一次的数字（异或性质：x ^ x = 0）
• 222. 完全二叉树的节点个数
• 231. 2 的幂
• 260. 只出现一次的数字 III
• 342. 4的幂