一名前端的基础位运算修养
 2021-01-28 17:34:05    3.1k Words  14 Mins

一名前端的基础修养系列 —- 位运算

1. 进制转换

img_20210126_191525.jpg

img_20210126_190700.jpg

js 自带的进制转换api： toString()

2. 十进制数的原码、反码、补码

进为什么会有原码、反码、补码？

是为了解决用二进制表示复数，将人习惯使用的符号转换为机器可以处理的形式。

那么，什么事原码、反码、补码？

2. 十进制数的原码、反码、补码

进为什么会有原码、反码、补码？

是为了解决用二进制表示复数，将人习惯使用的符号转换为机器可以处理的形式。

那么，什么事原码、反码、补码？

2.1 概念

2.1.1 原码

原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是 8 位二进制:

1
2
3
4
十进制 -> 原码

1  -> 0000 0001
-1 -> 1000 0001

正负数的原码有区别，那 0 呢？

1
2
3
4
十进制 -> 原码

+0 -> 0000 0000
-0 -> 1000 0000

2.1.2 反码

  1. 正数的反码与其原码相同
  2. 负数除了符号位，其他位置均取反
1
2
3
4
5
6
7
8
9
十进制 -> 原码 -> 反码

1  -> 0000 0001 -> 0000 0001
-1 -> 1000 0001 -> 1111 1110

0?

+0 -> 0000 0000 -> 0000 0000
-0 -> 1000 0000 -> 1111 1111

2.1.3 补码

  1. 正数的补码就是其本身
  2. 负数的补码是其反码 + 1
1
2
3
4
5
6
7
8
9
十进制 -> 原码 -> 反码 -> 补码

1  -> 0000 0001 -> 0000 0001 -> 0000 0001
-1 -> 1000 0001 -> 1111 1110 -> 1111 1111

0?

+0 -> 0000 0000 -> 0000 0000 -> 0000 0000
-0 -> 1000 0000 -> 1111 1111 -> 0000 0000

补码没有正0与负0之分

2.2 练习

已知一个数字的补码是 11101101 求其十进制数?

1
2
3
4
5
6
解：

补码: 1110 1101    (首位是符号位，是 1，说明是负数)
反码: 1110 1100    (补码 -1 是反码)
原码: 1001 0011    (反码除了符号位均取反，是原码)
十进制: -19

3. 位运算符

表达式 符号 解释
a & b & 位与运算，两者皆1则为1
a | b | 位或运算，有一个1则为1
a ^ b ^ 异或运算，不同则为1，否则为0
~a ~ 取反运算，0变成1，1变成0
a << b << 左移，将 a 左移 b 位（b<32），右边用 0 填充
a >> b >> 有符号右移，将 a 右移 b 位（b<32），右边超出的位丢弃，左边部分按照符号位补齐（正数补0，负数补1）
a >>> b >>> 无符号右移，将 a 右移 b 位（b<32），右边超出的丢弃，左边补0

做一下练习：

JavaScript 将数字存储为 64 位浮点数，但所有按位运算都以 32 位二进制数执行。

在执行位运算之前，JavaScript 将数字转换为 32 位有符号整数。

执行按位操作后，结果将转换回 64 位 JavaScript 数。

以下操作，为了简化表示，不补齐 32 位。

1
2
3
4
5
6
7
十进制：14 & 19
运算：
      0000 1110
      0001 0011
      ---------  &
      0000 0010
结果： 2
1
2
3
4
5
6
7
十进制：14 | 19
运算：
      0000 1110
      0001 0011
      ---------  |
      0001 1111
结果： 31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
十进制：14 ^ 19
运算：
      0000 1110
      0001 0011
      ---------  ^
      0001 1101
结果： 29

负数？

十进制：-14 ^ 19
运算：
      1000 1110 (原码)
			---------
      1111 0001 (反码)
      ---------  
      1111 0010 (补码)
      0001 0011
      ---------  ^
      1110 0001 (补码)
      ---------
      1110 0000 (反码)
      ---------
      1001 1111 (原码)
结果： -31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
十进制：~ 14
运算：
      0000 1110
      ---------  ~
      1111 0001 (补码)
      ---------
      1111 0000 (反码)
      ---------
      1000 1111 (原码)
结果： -15

负数？

十进制：~ -14
运算：
      1000 1110 (原码)
			---------
      1111 0001 (反码)
      ---------  
      1111 0010 (补码)
      ---------  ~
      0000 1101 (原码)
结果： 13

这里有一个规律：

~a = -(a + 1)

why ? (因为补码和反码转换的时候，+1 或则会 -1 造成的)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
十进制：14 << 3
运算：
      0000 0000 0000 1110
      ------------------- << 3
      0000 0000 0111 0000
结果： 112 (相当于 14 * 2 * 2 * 2)

负数的移动？

十进制：-14 << 3
运算：
      1000 0000 0000 1110 (原码)
      -------------------
      1111 1111 1111 0001 (反码)
      -------------------
      1111 1111 1111 0010 (补码)
      ------------------- << 3
      1111 1111 1001 0000 (补码)
      -------------------
      1111 1111 1000 1111 (反码)
      -------------------
      1000 0000 0111 0000 (原码)
结果： -112
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
十进制：14 >> 3
运算：
      0000 0000 0000 1110
      ------------------- >> 3
      0000 0000 0000 0001
结果： 1 (相当于 14 除了 3 次 2，每次抛弃小数点后的)

负数的移动？

十进制：-14 >> 3
运算：
      1000 0000 0000 1110 (原码)
      -------------------
      1111 1111 1111 0001 (反码)
      -------------------
      1111 1111 1111 0010 (补码)
      ------------------- >> 3
      1111 1111 1111 1110 (补码)
      -------------------
      1111 1111 1111 1101 (反码)
      -------------------
		  1000 0000 0000 0010 (原码)
      
结果： -2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
十进制：14 >>> 3
运算：
      0000 0000 0000 1110
      ------------------- >> 3
      0000 0000 0000 0001
结果： 1 (正数和有符号右移 >> 没有区别)

负数的移动？

十进制：-14 >> 3
运算：
      10000000 00000000 00000000 00001110 (原码)
      ---------------------------------------
      11111111 11111111 11111111 11110001 (反码)
      ---------------------------------------
      11111111 11111111 11111111 11110010 (补码)
      --------------------------------------- >> 3
      00011111 11111111 11111111 11111110 (原码)
      
结果： 536870910

因为这里设计到二进制最左边，所以以全貌 32 位来展示。

4. 实际应用

4.1 颜色 RGB 和 十六进制 的互相转换

我们注意到，rgb 的每一位数的范围都是 0 ～ 255。相当于 0 ～ 2^8 - 1，转换成二进制，刚好可以用8位表示完整。00000000 ～ 11111111，用 16 进制就是 00 ～ ff。

4.1.1 RGB -> 16进制

给定一个用 RGB 格式表示的颜色 rgb(213, 87, 70)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
首先，拆分一下，拿出来三个数字

213
87
70

然后，转化成二进制

213 -> 00000000 00000000 00000000 11010101
87  -> 00000000 00000000 00000000 01010111
70  -> 00000000 00000000 00000000 01000110

我们如果想把这三个数变成一个数，直接转换为 16 进制。需要怎么操作呢？（位移）

213 -> 00000000 00000000 00000000 11010101
87  -> 00000000 00000000 00000000 01010111
70  -> 00000000 00000000 00000000 01000110

213(?) -> 00000000 11010101 00000000 00000000
87(?)  -> 00000000 00000000 01010111 00000000
70(?)  -> 00000000 00000000 00000000 01000110

然后呢？这咋还是三个数，说好的一个呢？别急 （位或运算）

213(?) -> 00000000 11010101 00000000 00000000
87(?)  -> 00000000 00000000 01010111 00000000
70(?)  -> 00000000 00000000 00000000 01000110
					----------------------------------- |
??        00000000 11010101 01010111 01000110
                         d5       57       46
                         							#d55746

把上面的过程转化成代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
const rgbColor = 'rgb(213, 87, 70)';

function rgbToHex(str) {
  const res = str.match(/^rgb\((\d{1,3}),\s?(\d{1,3}),\s?(\d{1,3})\)$/);

  if(!res) return 'invalid';

  const [ , red, green, blue] = res;

  return '#' + (red << 16 | green << 8 | blue).toString(16);
}

console.log(rgbToHex(rgbColor));  // #d55746

反过来就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
拿到一个 16 进制颜色： #d55746；

先转换成 2 进制
#d55746 -> 00000000 11010101 01010111 01000110

接下来怎么分解成三个数呢？

我们一个一个取，先取得 red

#d55746 -> 00000000 11010101 01010111 01000110
           ----------------------------------- >> 16
           00000000 00000000 00000000 11010101
           														    0xd5 -> 213
           
挪动之后就只剩下了我们想要的值，下一个

#d55746 -> 00000000 11010101 01010111 01000110
           ----------------------------------- >> 8
           00000000 00000000 11010101 01010111
           
这下犯了难，不是我们想要的，那咋办呢，只想要后面部分的。（与运算）
           00000000 00000000 11010101 01010111
           00000000 00000000 00000000 11111111
           ----------------------------------- &
           00000000 00000000 00000000 01010111
                                          0x57 -> 87
           
同理，拿到最后一个
           00000000 11010101 01010111 01000110
           00000000 00000000 00000000 11111111
           ----------------------------------- &
           00000000 00000000 00000000 01000110
                                          0x46 -> 70

同代码表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const hexColor = '#254';

function hexToRgb(str) {
  const res = str.match(/^#([0-9a-f]{3}|[0-9a-f]{6})$/);

  if(!res) return 'invalid';
  
  let hex = res[1];

  if(String(hex).length == 3) {
    hex = String(hex).split('').map(char => `${char}${char}`).join('');
  }

  hex = Number('0x' + hex)

  return `rgb(${hex >> 16 & 0xff}, ${hex >> 8 & 0xff}, ${hex & 0xff})`;
}

console.log(hexToRgb(hexColor));  // rgb(34, 85, 68)

4.2 存储

一个用户对应多个标签的问题。比如有100个标签，每个用户都可能有其中的任意个。这个用户和标签的对应关系怎么存储？假如往数据库里存？

逗号分隔？不优雅！（虽然我们很多代码都是这样做的！）

这种情况，按位存储是比较理想的方案，怎么做呢？

1
2
3
const tagList = ['a', 'b', 'c', 'd', 'e'];

const userTags = ['b', 'e'];

我们先假设给每个标签一个标记值

1
2
3
4
5
6
7
8
9
10
11
12
a ->  1 -> 00000001
b ->  2 -> 00000010
c ->  4 -> 00000100
d ->  8 -> 00001000
e -> 16 -> 00010000

怎么存储呢？看起来没个标签对应一个二进制位，1 代表有这个标签，0 代表没有，所以我们吧他们集合起来不就可以了

b ->  2 -> 00000010
e -> 16 -> 00010000
           -------- |
           00010010 -> 18 = 16 + 2

转化成代码，

1
2
3
4
5
6
7
8
9
10
const tagList = ['aa', 'bb', 'cc', 'dd', 'ee', 'ff', 'gg', 'hh', 'ii', 'jj', 'kk'];


const inputTags = ['bb', 'ii', 'kk'];

const saveTags = tags => tags.reduce((total, item) => total | (1 << tagList.indexOf(item)), 0);

const encodeRes = saveTags(inputTags);

console.log(encodeRes);   // 1282

现在存起来了，那取出来怎么再对应回去呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const tagList = ['aa', 'bb', 'cc', 'dd', 'ee', 'ff', 'gg', 'hh', 'ii', 'jj', 'kk'];


const inputTags = ['bb', 'ii', 'kk'];

const saveTags = tags => tags.reduce((total, item) => total | (1 << tagList.indexOf(item)), 0);

const encodeRes = saveTags(inputTags);

console.log(encodeRes);   // 1282 

const getTags = num => {
  let index = 0, res = [];
  while(num && index < tagList.length) {
    if(num & 1) {
      res.push(tagList[index]);
    }

    num = num >> 1;
    index++;
  }

  return res;
}

const decodeRes = getTags(encodeRes);

console.log(decodeRes);   // [ 'bb', 'ii', 'kk' ]

用上面的例子，做个演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
a ->  1 -> 00000001
b ->  2 -> 00000010
c ->  4 -> 00000100
d ->  8 -> 00001000
e -> 16 -> 00010000

我们有 18，

18 -> 0001 0010
      
index = 0    0001 0010      &1 = 0   (说明没有 a)    []
             --------- >> 1
index = 1    0000 1001      &1 = 1   (说明有 b)     [b]
             --------- >> 1
index = 2    0000 0100      &1 = 0   (说明没有 c)   [b]
             --------- >> 1
index = 3    0000 0010      &1 = 0   (说明没有 d)   [b]
             --------- >> 1
index = 4    0000 0001      &1 = 1   (说明有 e)     [b, e]
             --------- >> 1
             0000 0000
                 (end)

5. 奇技淫巧

找了几个 leetcode 上的算法题

5.1 给定一个（正）整数，判断它是否是 2 的幂次方。

解题思路？

一直除 2 看是否可以等于 1？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function isFun(num) {
  let res = false;
  while(num > 0) {
    if(num % 1 !== 0) break;

    if(num === 1) {
      res = true;
      break;
    }

    num /= 2;
  }

  return res;
}

console.log(isFun(128)); // true
console.log(isFun(134)); // false

可以实现功能，但是bigger不高啊！试一试用位运算来实现。我们可以先看看这些数都有哪些特点。

1 2 4 8 16 32 …
1 10 100 1000 10000 100000 …

用二进制表示，只有第一位是1其余全是0。所以我们可以用这个特征来进行判断。

1
2
3
4
5
6
function isFun(num) {
  return /^1(0)*$/.test(num.toString(2))
}

console.log(isFun(128)); // true
console.log(isFun(134)); // false

有没有更好的办法？更优雅？

1
2
3
4
5
6
function isFun(num) {
  return !(num & num - 1);
}

console.log(isFun(128)); // true
console.log(isFun(134)); // false

原理？

1
2
3
4
5
6
7
8
9
128       -> 1000 0000
(128 - 1) -> 0111 1111
             --------- &
						 0000 0000 -> 0
						 
134       -> 1000 0110
(134 - 1) -> 1000 0101
             --------- &
             1000 0100 -> 132

5.2 进阶！判断一个正整数是否是 4 的幂次方

首先，满足是 4 的幂次方的数，一定也是 2 的幂次方数。如 上一题的表格所示。除此之外，他们也有自己的特征

1
2
3
4
1  -> 00000001
4  -> 00000100
16 -> 00010000
64 -> 01000000

可以看到，他的 1 是间隔出现的，从后往前数，都在奇数位置。

所以根据这个特征，可以在满足是 2 进制数的基础上，做一次判断，就可以达到我们想要的效果。但是怎么做呢？

可以扩展一下我们上面的正则方法，因为规律是 1 后面有 0 个或者偶数个0，

1
2
3
4
5
6
7
function isFun(num) {
  const res = num.toString(2)
  return /^1(00)*$/.test(res)
}

console.log(isFun(64)); // true
console.log(isFun(128)); // false

同样不够优雅，用位运算的方法是这样写

1
2
3
4
5
6
7
8
function isFun(num) {
  if(num & num - 1) return false;

  return (num & 0x55555555) === num;
}

console.log(isFun(64));  // true
console.log(isFun(128)); // false

0x55555555 是个什么玩意？？（黑人问号脸）

1
0x55555555 -> 01010101 01010101 01010101 01010101

转换成二进制，是一个 0 和 1 间隔的，奇数为是 1 的串。为什么是这么个玩意呢？

1
2
3
4
5
6
7
8
9
10
0x55555555 -> 01010101 01010101 01010101 01010101
256        -> 00000000 00000000 00000001 00000000
              ----------------------------------- &
              00000000 00000000 00000001 00000000 -> 256
              
0x55555555 -> 01010101 01010101 01010101 01010101
128        -> 00000000 00000000 00000000 10000000
              ----------------------------------- &
              00000000 00000000 00000000 00000000 -> 0

那，有没有什么其他的方法呢？

1
2
3
4
5
6
7
function isFun(num) {
  return /^1(0)*$/.test(num.toString(4))
}

console.log(isFun(256)); // true
console.log(isFun(128)); // false
console.log(isFun(134)); // false

我们把这个数转化成 4 进制

1
2
3
4
5
十进制 -> 四进制

256 -> 0001 0000
128 -> 0000 2000
137 -> 0000 2021

也是，满足 4 的幂次方数的，转化成 4 进制，同样是 1 开头，后面全是 0 （或者没有 0）。

所以扩展一下，一个 x 的幂次方，转化成 x 进制。都是 1 开头后面全是 0 （或者没有 0）。

扩展一下方法

1
2
3
4
5
6
7
8
9
10
11
12
/*
* params
* num 要验证的数
* a 要满足的幂次方
*/
function isFun(num, a) {
  return /^1(0)*$/.test(num.toString(a))
}

console.log(isFun(128, 2));  // true
console.log(isFun(81, 9));   // true
console.log(isFun(169, 13)); // true
 Comments