位运算奇技淫巧

位运算特性

x & x = x
x | x = x
x ^ x = 0

x & 0 = 0
x | 0 = x
x ^ 0 = x
x & y | x = x
x & (y | x) = x

常用等价语句

x ^ y == 0  // x == y
~x          // x != -1
x << 1 | 1  // x * 2 + 1
x ^ 1       // (x + 1) % 2
x & 1       // x % 2
~(x & 1)    // x % 2 == 0

// 从末尾低位开始算起，末尾为第1位
x |= 1 << i;     // 将第i+1位 置1
x &= ~(1 << i);  // 将第i+1位 置0

x & (1 << i);  // 取出第i+1位（即抛弃高位，低位 置0）
x & (-x);      // 取出最低的非零位（即抛弃高位，低位 置0）
x&(x - 1);     // 如果末尾为1，则置其为0

x & ~((1 << i) - 1);  // 将最后i位 置0
x & ((1 << i) - 1);   // 取出最后i位

“脱裤子放屁”的等价表达式

-x = ~x + 1 = ~(x - 1)
~x = -x - 1
-(~x) = x + 1
~(-x) = x - 1
x + y = x - (~y) - 1 = (x ^ y) + 2 * (x & y) = (x | y) + (x & y) = 2 * (x | y) - (x ^ y)
x - y = x + ~y + 1 = (x ^ y) - 2 * (~x & y) = (x & ~y) - (~x & y) = 2 * (x & ~y) - (x ^ y)
x ^ y = (x | y) - (x & y)
x & ~y = (x | y) - y = x - (x & y)
~(x - y) = y - x - 1 = ~x + y
x 恒等于 y = (x & y) - (x | y) - 1 = (x & y) + ~(x | y)
x | y = (x & ~y) + y
x & y = (~x | y) - ~x

其他

// 统计一个 int 的二进制中有多少个 1
__builtin_popcount(x);