Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

位运算系列-不使用四则运算符的加法

题目描述

写一个函数,求两个整数之和,要求在函数体内不得使用+、-、×、÷ 四则运算符号。

样例
输入:num1 = 1 , num2 = 2

输出:3

思路

经验知识1:位运算的特点之一是在二进制表示下不进位,参与位运算的各个bit之间是独立无关的。

经验知识2: XOR又称作无进位加法

经验知识3: 计算机便是通过XOR,与操作,移位操作来实现加法的,具体的做法可以见下面的代码。

相信如果你有上面三块知识储备,想出该题目的解法是没有问题的。

这里多说一句,为什么别人可以想出正确的解法,而我们不可以。原因有两个:

第一,别人知道某块知识,而我们不知道。

第二,(需要使用到的知识我们是知道的)别人能够通过发散思维,或者启发式思考调取需要用到的知识储备,而我们却不行。

针对以上两点,我们的解法是:

第一,学习更多的知识、经验、技巧,有更多的知识储备。

第二,不仅仅要学习知识、经验、技巧,还要去尝试着去做深度、广度的思考。深度的话,我们多问几个为什么,去剖析本质,找到他们的第一性原理。广度的话,我们要去做类比,要去做关联,了解两块知识的区别与联系。

第三,去做更多的刻意练习:多刷题,多解题,多推理证明,保证自己思维的严密性。

代码

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
public:
int add(int num1, int num2){
while (num2) {
/*
经过XOR操作后,1/0,0/1,0/0都已经符合预期了,只是1/1? 本来应该成为10,却变成了0?
我们怎样才能找回丢失的进位呢? 只有&操作才能将两个1变为1,也许是我们好的选择?
实际上,这就是计算机执行加法的底层原理。
*/
int sum = num1 ^ num2;
int carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
//用计算出来的结果重新赋值,有点辗转相除法的感觉。
}
return num1;
}

int sub(int num1, int num2) {
//a - b = a + (-b)
return add(num1, add(~num2, 1)))
}


int mul(int a, int b) {
//最笨的方法是for循环--b次; 有没有更好的办法呢?
//都转为正数先
int a1 = a >= 0 ? a : add(~a, 1);
int b1 = b >= 0 ? b : add(~b, 1);
int sum = 0;
//整个过程跟手动乘法类似
while (b1) {
if (b1 & 0x01) {
sum = add(sum, a1);
}
a1 <<= 1;
b1 >>= 1;
}

//异号,相反数
if (a ^ b < 0) {
sum = add(-sum, 1);
}

return sum;
}

int div(int a, int b, int& reminder) {
int r = 0;
//都转为正数先
int a1 = a >= 0 ? a : add(~a, 1);
int b1 = b >= 0 ? b : add(~b, 1);
for (int i = 31; i >= 0; i--) {
if ((a1 >> i) >= b1) { // a >= (b << i)
r = add(r, 1 << i);
a1 = sub(a1, b1 << i);
}
}

//异号,相反数
if (a ^ b < 0) {
r = add(~r, 1);
}

reminder = a1;
return r;
}
};


你的支持是我坚持的最大动力!