位运算的应用 - 移位 / 左移 & 右移 / SHL & SHR / << & >>

创建时间:
2014-06-14 17:30
最近更新:
2018-08-11 22:54

乘法 / 除法

x * 2 的 2 进制实现为 x << 1x * 2 ^ k 的 2 进制实现为 x << k
x / 2 的 2 进制实现为 x >> 1x / 2 ^ k 的 2 进制实现为 x >> k

<<

a << b 实际上就是 a 乘以 2 的 b 次方,因为在二进制数后添一个 0 就相当于该数乘以 2。
通常认为 a << 1a * 2 更快,因为前者是更底层一些的操作。因此程序中乘以 2 的操作请尽量用左移一位来代替。
定义常量时可能会用到 shl 运算。你可以方便地用 (1 << 16) - 1 来表示 65535。
很多算法和数据结构要求数据规模必须是 2 的幂,此时可以用 shl 来定义 Max_N 等常量。

>>

和 shl 相似,a >> b 实际上就是 a 除以 2 的 b 次方 (取整)。
程序中经常用 a >> 1 来代替 a / 2,比如二分查找、堆的插入操作等等。
想办法用 shr 代替除法运算可以使程序效率大大提高。
最大公约数的二进制算法用除以 2 操作来代替慢得出奇的 mod 运算,效率可以提高 60%。

计算 小于等于 n 的偶数

n >> 1 << 1

掩码 / 上限 / 最大值

计算掩码

例如 一个 "截取低 6 位的掩码 0×3F",用位运算可以表示为 (1 << 6) -1,该表示中 掩码的位数 直接体现在表达式里,更直观。

n 位的 "最大值 - 1"/"掩码"

  • -1 ^ (-1 << n) //Twitter Snowflake 官方实现中用此算法计算 数据中心序号 的最大值。
  • (1 << n) - 1 //http://github.com/RobThree/IdGen 中用此算法计算 掩码。

2018-06-13 Tony 已测试验明 以上两种算法结果相等。

生产代码备份

public long GetMask(byte bits)
{
    return (1L << bits) - 1;
}