位运算实现四则运算

位运算实现四则运算

最近看到一道算法题,大概内容时不用四则运算实现两个数的相加;看到题目的时候,第一想法就是这道题和二进制有关,JavaScript 中与二进制相关的操作符就是位运算操作符了。下面简单记录下通过位运算实现四则运算符。

加法

首先,先通过一个例子来看下十进制的加法的步骤:

1
16 + 17 = 33
  • 相加各位(个位、十位、百位…)的值,不考虑进位,得到 23
  • 计算进位的值,6 + 7 进 10,得到 10
  • 重复上面两步,将进位值与个位值相加

参考十进制相加的步骤,来看下二进制相加:

$$
16 + 17 = 13
$$

  1. 将两个加数分别转换为二进制
1
2
3
16 => 00001000

17 => 00001001
  1. 同样计算各位的值,不考虑进位,得到 m
1
2
3
4
0000 1000 16
0000 1001 17
------------ ^
0000 0001 1

不考率进位的情况下,可以看出上面的运算结果相当于两个数进行了异或运算(a ^ b

  1. 计算进位的值,得到结果 n

二进制相加时只有在对应位都是 1 的情况下才需要往前进位(左移一位),可以通过与运算符(a & b)来获取需要进位的位置

1
2
3
4
5
6
0000 1000 16
0000 1001 17
------------ &
0000 1000 16
------------ << 1
0001 0000 32
  1. 重复上诉步骤,直到没有进位(m ^ n 是否为 0),此时 m + n 就是最终的计算结果

用代码实现就是:

1
2
3
4
5
6
7
function add(a, b) {
while(a !== 0) { // 没有进位
[a, b] = [(a & b) << 1, a ^ b];
}

return b;
}

减法

减法可以看做是被减数加减数的负数:

1
a - b = a + (-b)

由于计算机内部采用 补码(2 的补码) 的形式表示负数,那么计算公式转换为被减数加上减数的补码

1
a - b = a + (-b) = a + (11111111 - b) + 1

同样,先举个例子来看看具体步骤:

1
7 - 6 = 7 + (-6)
  1. 将被减数、减数分别转换为二进制

    1
    2
    3
    7 => 0000 0111

    6 => 0000 0110
  2. 计算

    1
    2
    3
    4
    1111 1111
    0000 0110
    --------- -
    1111 1001 ~b
    1
    2
    3
    4
    5
    6
    7
    8
    9
    0000 0111
    1111 1001
    --------- + ~b
    1 0000 0000
    --------- 第九位溢出位舍去
    0000 0000
    0000 0001
    --------- + 1
    0000 0001

用代码实现就是:

1
2
3
4
5
6
7
8
9
function sub(a, b) {
b = ~b;

while(a !== 0) {
[a, b] = [(a & b) << 1, a ^ b];
}

return b + 1;
}

乘法

a*b 可以看做 a 个 b 相加

1
2
3
4
5
6
7
8
9
function multiply(a, b) {
let sum = 0;

for (let i = 0; i < b; i++) {
sum += add(sum, a);
}

return sum;
}

除法

a / b 可以转换为 a -b,直到差为非正数为止。

1
2
3
4
5
6
7
8
9
10
11
function divide(a, b) {
let count = 0;

while (a > 0) {
a = sub(a, b);

a >= 0 && count++;
}

return count;
}