位运算

基本概念

  • 左移 <<
    右边空位补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

标签: none

仅有一条评论

  1. 沙发都是给看不懂的人来坐得

添加新评论