位运算
在计算机中整数采用补码存储,即高位1表示负数,0表示正数,补码和原码的转换都是高位不变,其余位取反再加1。
使用补码存储的好处就是可以将减法也同样采用加法的方法进行运算。比如说8-5,也就是(-5)+8,具体怎么做的呢?
1.用s存储两数异或^(不进位加法)的结果,用c存储两数与&运算的结果左移一位(进位)
2.然后将两数分别替换为s和c,进行s和c的加法,这个循环过程一直持续到c为0为止
3.返回num1
我们来看-5和8的加法模拟
1111 1011
1000
1111 0011
1 0000
1110 0011
10 0000
1100 0011
100 0000
1000 0011
1000 0000
0000 0011
0000 0000
最后返回的补码就是正整数3
为了解决c在成为1000 0000时左移越界的问题,我们用long来存储c,但是不改变num2的类型,在num2赋值为c的时候,取低位8位,也就成为了0000 0000,逻辑完全。
class Solution {
public:
int add(int a, int b) {
while(b)
{
int s=a^b;
long c=(long)(a&b)*2;
a=s,b=c;
}
return a;
}
};