位运算

基础 - 原码、反码、补码

众所周知, 计算机程序里最基本就是二进制了, 关于二进制不得不了解的三种码:

• 原码, 首位符号位, 1 表负数, 0 表正数; 正数的反码和补码与原码一致
• 反码, 负数反码, 符号位为 1, 其他 0->1, 1->0
• 补码, 负数补码, 其反码 + 1

补码的原理是取模同余, 推荐阅读 计算机组成原理 - 原码,反码,补码. 整数在计算机中是以补码存在的, 因为这样方便负数的计算

位操作

• &, 有 0 为 0
• |, 有 1 为 1
• ~, 按位取反. 它的十进制数学计算是 加 1 取反
• ^, 相同为 0, 不同为 1
• x >> n, 低位丢弃, 高位补 符号位, 它的十进制数学计算是 x / 2^n
• x << n, 高位丢弃, 低位补 0. 它的十进制数学计算是 x * 2^n

常用技巧

下面的 x 代表一个数字

• 判断奇偶: x & 1 ? 奇数 : 偶数
• 向 0 取整¹: x | 0
• indexOf 结果判断: !~x, 只有 x 为 -1, ~x 才等于 0, 可以这么看 !(不)~(存)x(在)
• 布尔转0/1: ~~x, true -> 1, false -> 0
• 中位数: x >> 1
• 判断是否异号: (x ^ y) < 0 则异号. 相比用乘积来判断的优势是不会有整型溢出.
  注意位运算的优先级低于算术运算, 所以结合的时候记得加个括号.

进阶技巧

• x & x - 1, 消除 x 二进制的最后一个 1 后的值.
  • lc.191 汉明重量;lc.461 汉明距离；lc.231 2的幂;;都可以利用该方法快速解决
• x & -x, 取 x 的最后一个 1 代表的值.
  • 在 React 源码中, getHighestPriorityLane 就是用来获取最高优先级的(React定义1越靠右优先级越高).
• x ^ x === 0; x ^ 0 === x, 且异或操作满足交换律、结合律.

来看一道经典题: 一组数, 只有 2 个数出现了一次，其他都是偶数次，找出这 2 个数.

// test: [1,2,3,4,5,6,5,4,3,2]
function findOnlyOne(arr) {
  let val = 0
  for (const item of arr) {
    val ^= item
  }
  // 此刻 val 为两个只出现一次数的异或结果
  // 根据异或相同为0,不同为1的情况, 两个不同的数异或结果一定至少有一个1, 可以找到最右边的 1
  const rightOne = val & -val

  let a = 0
  for (const item of arr) {
    // rightOne 可以把原数据分为2波, 从而剥离出第一个不同的数
    if ((rightOne & item) === 0) {
      a ^= item
    }
  }
  let b = a ^ val // 利用异或的性质 a ^ b = c, 则 a ^ c = b
  return [a, b]
}

在一些源码中, 常常利用二进制来进行一些常量定义, 使用位运算去进行处理:

const A = 1 << 0; // 0b00000001
const B = 1 << 1; // 0b00000010
const C = 1 << 2; // 0b00000100

const ABC = A | B | C; // 0b00000111 增加属性
const AB = ABC & ~C;   // 0b00000011 删除属性
(AB & B) === B         // true, 意味着 AB 包含 B
(AB & C) === 0         // true，意味着 AB 不包含 C

推荐阅读

• Bit Twiddling Hacks