通过位运算求两个数的和(求解leetcode:371. Sum of Two Integers)

昨天在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;
}
上一篇:c语言小技巧:C语言学习笔记之位运算求余


下一篇:cakephp 如何在一个模型里调用另一个模型