位运算

任何 int 在内存里都是一串二进制位,例如 11 = 00001011(8 + 2 + 1)。最右是最低位,藏着奇偶的秘密:x & 1 取最低位,是 1 就是奇数——比 x % 2 == 1 更快也更稳,因为负奇数取模在 C 里得 -1,用 % 判断会漏。左移 11 << 1 = 22(乘 2),右移 11 >> 1 = 5(除 2 向下取整,最低位被挤丢)。

x & (x - 1) 把最低位的那个 1 抹成 0(11 = 1011 变 1010 = 10),循环做到 0,做几次就有几个 1——这就是数二进制 1 的个数的写法。x & -x 取出最低位的那个 1(lowbit),树状数组里天天用。

异或口诀「相同为 0,不同为 1」,最神奇的性质是两个相同的数异或为 0。由此两招:a ^= b; b ^= a; a ^= b; 不用临时变量交换两数;数组里其余数都出现两次、只有一个出现一次时,把全部元素异或一遍,成对的互相抵消,剩下的就是那个单的(4^1^2^1^2 = 4),一趟 O(n) 零额外空间。