周星星

Appearance

原文首发于语雀《位运算的算法应用》。

基本介绍 ​

作为算法题的一个大类，位运算相关的题目常常出现在各大公司的面试/笔试题中，下面先说说位运算的基本原理。

位运算使得计算机可以直接对每个比特位进行计算，效率会非常的高。

在 JS 中，位运算会将操作数当作 32 位的二进制串进行计算，如果二进制串超过 32 位，则只保留最后的 32 位进行计算，如：

11100110111110100000000000000110000000000001 # 输入的二进制串
            10100000000000000110000000000001 # 实际使用的二进制
11100110111110100000000000000110000000000001 # 输入的二进制串
            10100000000000000110000000000001 # 实际使用的二进制

在 JS 中，位运算有 7 种运算符：

  1. 按位与（a & b）：在 a, b 的位表示中，每一个对应的位都为 1 则返回 1，否则返回 0
# 15 & 9 -> 9
  0000 0000 0000 0000 0000 0000 0000 1111
& 0000 0000 0000 0000 0000 0000 0000 1001
  ---------------------------------------
  0000 0000 0000 0000 0000 0000 0000 1000
# 15 & 9 -> 9
  0000 0000 0000 0000 0000 0000 0000 1111
& 0000 0000 0000 0000 0000 0000 0000 1001
  ---------------------------------------
  0000 0000 0000 0000 0000 0000 0000 1000
# 3&-2 -> 2
  0000 0000 0000 0000 0000 0000 1111 1110
& 0000 0000 0000 0000 0000 0000 0000 0011
  ---------------------------------------
  0000 0000 0000 0000 0000 0000 0000 0010
# 3&-2 -> 2
  0000 0000 0000 0000 0000 0000 1111 1110
& 0000 0000 0000 0000 0000 0000 0000 0011
  ---------------------------------------
  0000 0000 0000 0000 0000 0000 0000 0010

上面这个例子首先要求得-2的补码是多少，然后再去按位与。

譬如现在我们以 3&-2 来看一下计算步骤：

  1. 将2(这里叫原码)转为二进制 ： 0000 0010
  2. 按位取反为 ： 1111 1101
  3. 末位加1得到补码 ： 1111 1110
  1. 按位或（a | b）：在 a, b 的位表示中，每一个对应的位，只要有一个为 1 则返回 1，否则返回 0
# 15 | 9 -> 15
  0000 0000 0000 0000 0000 0000 0000 1111
| 0000 0000 0000 0000 0000 0000 0000 1001
  ---------------------------------------
  0000 0000 0000 0000 0000 0000 0000 1111
# 15 | 9 -> 15
  0000 0000 0000 0000 0000 0000 0000 1111
| 0000 0000 0000 0000 0000 0000 0000 1001
  ---------------------------------------
  0000 0000 0000 0000 0000 0000 0000 1111
  1. 按位异或（a ^ b）：在 a, b 的位表示中，每一个对应的位，两个不相同则返回 1，相同则返回 0
# 15 ^ 9 -> 6
  0000 0000 0000 0000 0000 0000 0000 1111
| 0000 0000 0000 0000 0000 0000 0000 1001
  ---------------------------------------
  0000 0000 0000 0000 0000 0000 0000 0110
# 15 ^ 9 -> 6
  0000 0000 0000 0000 0000 0000 0000 1111
| 0000 0000 0000 0000 0000 0000 0000 1001
  ---------------------------------------
  0000 0000 0000 0000 0000 0000 0000 0110
  1. 按位非（~a）：反转被操作数的位，即将每一位的 0 转为 1，1 转为 0
# ~15 -> -16
~ 0000 0000 0000 0000 0000 0000 0000 1111
  ---------------------------------------
  1111 1111 1111 1111 1111 1111 1111 0000
# ~15 -> -16
~ 0000 0000 0000 0000 0000 0000 0000 1111
  ---------------------------------------
  1111 1111 1111 1111 1111 1111 1111 0000

譬如现在我们以 ~3 来看一下计算步骤：

  1. 将3(这里叫原码)转为二进制 ： 00000011
  2. 按位取反为 ： 11111100
  3. 发现符号位(即最高位)为1(表示负数)，负数的二进制保存方式为其补码形式
  4. 除符号位之外，按位取反 ： 10000011
  5. 末位加1得到补码 ： 10000100
  6. 转换为十进制为 ： -4
  1. 左移（a << b）：将 a 的二进制串向左移动 b 位，右边移入 0
# 9 << 2 -> 36
<<  0000 0000 0000 0000 0000 0000 0000 1001
    ---------------------------------------
    0000 0000 0000 0000 0000 0000 0010 0100
# 9 << 2 -> 36
<<  0000 0000 0000 0000 0000 0000 0000 1001
    ---------------------------------------
    0000 0000 0000 0000 0000 0000 0010 0100
  1. 有符号右移（a >> b）：把 a 的二进制表示向右移动 b 位，向右被移出的位被丢弃，拷贝最左侧的位以填充左侧。这种右移由于保留最左侧的二进制位，因此可以保留数字原本的正负符号

-9的补码是11110111。

  1. 原码是：10001001
  2. 反码是：11110110
  3. 9的正确二进制表示法是：00001001
  4. 补码计算方法：求得原码的反码；反码末位加1。
  5. 当要表示-9时候，先对9的原码取反，变成11110110，即反码，反码基础上加1为11110111，是-9的补码。
# 9 >> 2 -> 2
>>  0000 0000 0000 0000 0000 0000 0000 1001
    ---------------------------------------
    0000 0000 0000 0000 0000 0000 0010 0010
# -9 >> 2 -> -3
>>  1111 1111 1111 1111 1111 1111 1111 0111
    ---------------------------------------
    1111 1111 1111 1111 1111 1111 1111 1101
# 9 >> 2 -> 2
>>  0000 0000 0000 0000 0000 0000 0000 1001
    ---------------------------------------
    0000 0000 0000 0000 0000 0000 0010 0010
# -9 >> 2 -> -3
>>  1111 1111 1111 1111 1111 1111 1111 0111
    ---------------------------------------
    1111 1111 1111 1111 1111 1111 1111 1101
  1. 无符号右移（a >>> b）：把 a 的二进制表示向右移动 b 位，向右被移出的位被丢弃，左边空出的位全部填充为 0。这种右移由于左侧直接补 0，因此生成的数字必然是非负数
# 19 >>> 2 -> 4
>>>  0000 0000 0000 0000 0000 0000 0001 0011
     ---------------------------------------
     0000 0000 0000 0000 0000 0000 0010 0010
# -19 >>> 2 -> 1073741819
>>>  1111 1111 1111 1111 1111 1111 1110 1101
     ---------------------------------------
     0011 1111 1111 1111 1111 1111 1111 0011
# 19 >>> 2 -> 4
>>>  0000 0000 0000 0000 0000 0000 0001 0011
     ---------------------------------------
     0000 0000 0000 0000 0000 0000 0010 0010
# -19 >>> 2 -> 1073741819
>>>  1111 1111 1111 1111 1111 1111 1110 1101
     ---------------------------------------
     0011 1111 1111 1111 1111 1111 1111 0011

常用性质 ​

在使用位运算技巧解的算法题中，有以下这些常用的性质：

  1. a 与自身之间的操作
a & a = a
a | a = a
a ^ a = 0
a & a = a
a | a = a
a ^ a = 0
  1. a 与 0 之间的操作
a & 0 = 0
a | 0 = a
a ^ 0 = a
a & 0 = 0
a | 0 = a
a ^ 0 = a
  1. 按位与、按位或的还原计算
a | ( a & b ) = a
a & ( a | b ) = a
a | ( a & b ) = a
a & ( a | b ) = a
  1. 通过异或完成变量值交换
a ^= b
b ^= a
a ^= b
a ^= b
b ^= a
a ^= b
  1. 判断奇偶（通过 & 1 取出最后一个二进制位以达到模 2 的效果）
# 位运算效率更高
a & 1 === a % 2
# 位运算效率更高
a & 1 === a % 2
  1. 比较两值是否相等（a ^ a === 0）
a ^ b === 0
a ^ b === 0
  1. 将第 i + 1 个二进制位设为 1
a |= 1 << i
a |= 1 << i
  1. 将第 i + 1 个二进制位设为 0
a &= ~(1 << i)
a &= ~(1 << i)
  1. 取出第 i + 1 个二进制位上的数值
a & (1 << i)
a & (1 << i)
  1. 在 a 第 i + 1 个二进制位，插入 b 对应位置的二进制位
a |= 1 << i
a & (b & 1 << i)
a |= 1 << i
a & (b & 1 << i)
  1. 删除二进制序列中最后一个值为 1 的位置
a &= (a - 1)
a &= (a - 1)
  1. 计算 a 的相反数
-a === ~a + 1
-a === ~a + 1
  1. 保留 a 在二进制位中最后一个 1
a &= (-a)
a &= (-a)
  1. 生成二进制位全为 1 的数
~0
~0
  1. 保留 a 二进制序列中最后的 i - 1 位，其余补 0
a & ((1 << i) - 1)
a & ((1 << i) - 1)
  1. 将 a 二进制序列中最后 i - 1 位全部置为 0
a & ~((1 << i) - 1)
a & ~((1 << i) - 1)
  1. 判断 a 的二进制序列最高位是否为 1
a < 0 # 最高位为 1 必然是负数
a < 0 # 最高位为 1 必然是负数
  1. 在二进制序列中，仅保留最高位的 1，其他设为 0，输出该数
a = a | (a >> 1)
a = a | (a >> 2)
a = a | (a >> 4)
a = a | (a >> 8)
a = a | (a >> 16)
return (a + 1) >> 1
a = a | (a >> 1)
a = a | (a >> 2)
a = a | (a >> 4)
a = a | (a >> 8)
a = a | (a >> 16)
return (a + 1) >> 1