前言

大部分例子引用自 Bit Twiddling Hacks (opens new window)

一些位操作优化的技巧在 js 中不一定能得到体现，本文仅展示一些自己在前端项目中用过且较常用的例子

某些例子比如交换，计算奇偶，计算最值的，使用位操作提升不大，但可读性变差了，本文不做记录

1. 检测两个整数是否异号

本处例子中，0 与正数相当

const isOppositeSign = (x, y) => (x ^ y) < 0
isOppositeSign(1, -2)  // true
isOppositeSign(1, 2)   // false
isOppositeSign(-0, -1) // true

2. 判断一个整数是否为 2 的幂

注意 0 不是 2 的幂，加上 !!num 判断

const isPowerOf2 = (num) => !!num && (num & (num - 1)) === 0
isPowerOf2 (0) // false
isPowerOf2 (1) // true
isPowerOf2 (3) // false

3. 计算无符号整数的比特位中有多少个 1

常用于统计一组开关中状态为开的个数

原始方法

对 num 不断右移，每次判断最后一位是否为1，循环次数为 num 的比特位个数

const countBits = (num) => {
  let res = 0
  for (; num; num >>= 1) {
    res += num & 1;
  }
  return res
}
countBits (4) // 1

Brian Kernighan's way

每次清除一个最低的 1 的比特位，循环次数与 num 的比特位有多少个 1 相关

const countBits = (num) => {
  let c = 0;
  for (; num; c++) {
    num &= num - 1; // 清除最低比特位
  }
  return c
}
countBits (5) // 2

4. 获取最高位 1 所在位置

得到一个索引值

const getHighest1BitIndex = (num) => {
  let c = -1
  while (num) {
    num >>= 1
    c++
  }
  return c
}

同时可以用来计算一个整数以 2 为底的对数，其他拓展应用：

获取某个范围内最大的 2 的幂

const hignBit = (num) => {
  let index = getHighest1BitIndex(num)
  return 1 << index
}
hignBit(14) // 8
hignBit(8) // 8

另一种解法

const hignBit = (num) => {
  let res;
  while (num) {
    res = num
    num = num & (num - 1)
  }
  return res
}
hignBit(14) // 8
hignBit(8) // 8

5. 获取最低位 1 所在位置

利用 n & -n （又称 lowbit 函数）得到最低位 1 形成的数，然后不断右移得到索引值

const lowBit = (num) => {
  return num & -num
}
const getLowest1BitIndex = (num) => {
  let n = lowBit(num)
  // return getHighest1BitIndex(n)
  let c = -1
  while (n) {
    n >>= 1
    c++
  }
  return c
}

树状数组中经常用到 lowbit

6. 获取某个位置的比特位

const getBit = (num, i=0) => {
  // i 从 0 开始
  return (num >> i) & 1
}
getBit(5,1)

7. 判断两个位置的比特位是否一致

const getBit = (num, i = 0) => {
  return (num >> i) & 1
}
const judgeSameBit = (num, i, j) => {
  // const lo = getBit(num, i)
  // const hi = getBit(num, j)
  // return !(lo ^ hi)
  return !(((num >> i) ^ (num >> j)) & 1)
}
judgeSameBit(6, 0, 2) // false
judgeSameBit(6, 1, 2) // true

8. 交换比特位

交换单个比特位

原始序列为 S, 将第 i 个(从右往左数，起始索引为0) 与 第 j 个比特位进行交换

先判断两个位置比特位是否一致，得到一个异或的结果 x

将所有位置置 0，i、j 置为 x : (x << i) | (x << j) ，得到结果 res

最后将原始序列与 res 进行异或，即可实现交换比特位的效果

const swapBit = (num, i, j) => {
  let x = ((num >> i) ^ (num >> j)) & 1;
  return num ^ ((x << i) | (x << j));
}
swapBit(4, 0, 2) //1

交换指定长度的比特位

原始序列为 S, 将第 i 位(从右往左数，起始索引为0)开始，长度为 len 的序列与 第 j 位开始，长度为 len 的序列进行交换

举例，S = 00010111 i=0 j=4 len=3 交换后得到 01110001

const swapIndividualBits = (num, i, j, len) => {
  let x = ((num >> i) ^ (num >> j)) & ((1 << len) - 1);
  return num ^ ((x << i) | (x << j));
}
swapIndividualBits (23,0,4,3) //113 23=>0010111(2) 113=>01110001(2)

常用于移动一组开关的位置

9. 反转比特序列

由于 js 中不能指定一个数字类型的存储大小，这里需要手动指定一共有多少比特位

原始方法

头尾两两交换 O(n)

const swapBit = (num, i, j) => {
  let x = ((num >> i) ^ (num >> j)) & 1;
  return num ^ ((x << i) | (x << j));
}
const reverseBits = (num, n = 8) => {
  let len = n >> 1
  let res = num
  for (let i = 0; i < len; i++) {
    res = swapBit(res, i, n - i - 1)
  }
  return res
}
reverseBits(111) // 246  due to 01101111 => (0)11110110

分治法

仅适用于固定字节，在 js 中不太适用

10. 查找数字

仅一个元素出现一次，其余元素出现2次

var singleNumber = function(nums) {
  return nums.reduce((pre,cur)=>pre^cur)  
};

仅一个元素出现一次，其余元素出现 k 次

思路见 leetcode-137. 只出现一次的数字 II (opens new window)

代码如下：

var singleNumber = function (nums, k=3) {
  if (nums.length === 1) {
    return nums[0]
  }
  let base = 1
  let res = 0
  for (let i = 0; i < 32; i++) {
    let cnk = 0
    for (let j = 0; j < nums.length; j++) {
      cnk += nums[j] & base ? 1 : 0
    }
    if (cnk % 3 !== 0) {
      res |= base
    }
    base <<= 1
  }
  return res
};

恰好有两个元素只出现一次，其余所有元素均出现两次

思路见 leetcode-260. 只出现一次的数字 III (opens new window)

代码如下：

var singleNumber = function (nums) {
  if (nums.length === 2) {
    return nums
  }
  let res = nums.reduce((a, b) => a ^ b)
  // 取最低非0位，两个数在该位上 一个为0 一个为1，  
  // 进行 数组划分 该位为1的一组，该位为0的一组
  let tmp = res & -res
  let res1 = 0;
  let res2 = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] & tmp) {
      res1 ^= nums[i]
    } else {
      res2 ^= nums[i]
    }
  }
  return [res1, res2]
};

---

未完待续...

拓展阅读

1. Bit Twiddling Hacks (opens new window)
2. Bit Hacks：关于一切位操作的魔法（上） (opens new window)