0%

前端项目中常用的位操作技巧

前言

大部分例子引用自 Bit Twiddling Hacks

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

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

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

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

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

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

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

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

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

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

原始方法

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

1
2
3
4
5
6
7
8
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 相关

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

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

得到一个索引值

1
2
3
4
5
6
7
8
const getHighest1BitIndex = (num) => {
let c = -1
while (num) {
num >>= 1
c++
}
return c
}

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

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

1
2
3
4
5
6
const hignBit = (num) => {
let index = getHighest1BitIndex(num)
return 1 << index
}
hignBit(14) // 8
hignBit(8) // 8

另一种解法

1
2
3
4
5
6
7
8
9
10
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 形成的数,然后不断右移得到索引值

1
2
3
4
5
6
7
8
9
10
11
12
13
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. 获取某个位置的比特位

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

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

1
2
3
4
5
6
7
8
9
10
11
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 进行异或,即可实现交换比特位的效果

1
2
3
4
5
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

1
2
3
4
5
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
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次

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

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

思路见 leetcode-137. 只出现一次的数字 II

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
  2. Bit Hacks:关于一切位操作的魔法(上)
您的支持将鼓励我继续创作!