位运算

基本概念

• 左移 <<
  右边空位补0，其值相当于x2。
• 右移 >>
  如果为正数左边空位补0，如果为负数则可能补0或补1（取决于所使用的计算机系统）。
• 按位与 &
  两个都为1则为1
• 按位或 |
  其中一个为1则为1
• 按位异或 ^
  “半加”，不同的为1，相同的为0
• 取反 ~
  ~1 = 0, ~0 = 1 涉及补码的算法：

  1. 正数的补码与原码相同
  2. 负数的补码是对其原码逐位取反，但符号位（第一位）除外；然后整个数加1。

常用算法

判断奇偶性

lambda x : x & 1

取二进制数的第k位

lambda x, k : x >> k & 1

二进制数k位清0

lambda x : x & ~ (1 << k)

二进制数k位置1

lambda x : x | (1 << k)

求平均值

lambda x, y : (x & y) + ((x ^ y) >> 1)

判断是否为2的幂

lambda x : ((x & (x-1)) == 0) && (x != 0)

交换两整数

a, b = 3, 4
a = a ^ b
b = b ^ a
a = a ^ b
print(a, b) #4 3