昨天在leetcode做题的时候做到了371,原题是这样的:
371. Sum of Two Integers Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -. Example:
Given a = 1 and b = 2, return 3.
因为之前完全没有在实际练习中使用过位运算,所以刚看到这道题目的时候我的第一反应是
1.用乘除代替加减,但是一想,觉得恐怕不行,因为乘除本质上也是加减法,不可能跳过加减法做运算。
2.然后又想到或许可以转成二进制再用逻辑运算计算?但是问题是转成二进制不难,但是转回来还是得用加减法呀!看来这种方法也不行。
3.于是想到位运算,但是由于对位运算很不熟悉,于是上网搜了一下,得到如下表格:
含义 |
Pascal语言 | C语言 | Java |
---|---|---|---|
按位与 | a and b | a & b | a & b |
按位或 | a or b | a | b | a | b |
按位异或 | a xor b | a ^ b | a ^ b |
按位取反 | not a | ~a | ~a |
左移 | a shl b | a << b | a << b |
带符号右移 | a shr b | a >> b | a >> b |
无符号右移 | a>>> b |
好吧,其实一看都是一些布尔运算,也不难理解,接下来就是运算问题了。
举个例子试试看怎么算吧,比如3 + 1,该怎么算呢?由于位运算都是基于二进制的也就是3 + 1 = (011) + (001),如果列竖式计算的话就是
0 1 1 + 0 0 1 ----------- 0 1 0 + 0 1 0 ----------- 1 0 0
看懂了吗?其实就是模拟进位:
1.首先最低位相加是要进一的
2.然后在做第二位的运算
3.以此类推,一直到没有进位为止。
那么必须弄清楚什么时候需要进位,很明显,当同一位上的数字都是1的时候需要进位,进位以后下一位变成1,也就是3 & 1中等于1的地方是需要进位的,然后左一一位,使下一位变成1, 然后下一位需要加的数字就是 3 ^ 1。
C++代码实现如下:
int getSum(int a, int b) {
while(a != ) {
int tmp = (a & b) << ;
b = a ^ b;
a = tmp;
}
return b;
}