位运算详解
1.原文地址
http://www.lgygg.wang/lgyblog/2019/11/11/%e4%bd%8d%e8%bf%90%e7%ae%97/
2.位移符号
>>相当于使当前二进制对应的10进制数除以2.
<<相当于使当前二进制对应的10进制的数乘以2.
例如，a=2,b=9;
a的二进制数是：0010，如果a左移1位，即a>>1，得到0001，即十进制数1。
b的二进制数是：1001，如果b右移1位，即b<<1，得到10010，即18。
所以，如果要求两个数的平均值，可以使用（a+b）>>1,得到0101，即十进制数5，这里你会疑问，(2+9)/2=5.5,这里就是说左移只能对结果是偶数的数值求平均值才能得到正确结果，对应奇数结果的平均值，他会向下取整，所有得到5.5。
3.~求负数
某个正整数的负数可以通过~取反后+1来获得。
假设a=1,求它的负数，即-1的二进制表示。
1的二进制表示是，0001，
-1就是正整数二进制的反码加1，即（~1）+1，（1110）+0001=1111，
这里只是使用4位二进制来表示，当然如果使用8位二进制表示来计算，可以表示为
1的8位二进制表示，00000001，
-1的8位二进制表示，11111111
4.&判断奇偶
&可以用来判断10进制数的奇偶。
例如，判断a=10,b=23是奇数还是偶数。
a的二进制数是00001010
b的二进制数是00010111
只需要和1进行与操作即可，因为一个奇数的二进制表示中1的个数肯定是偶数，而一个偶数的的二进制表示中1的个数肯定是奇数个。为零为偶，否则奇数。
同a&1和b&1来判断a和b是奇数还是偶数。
00001010
&
00000001
结果是，00000000，所有a是偶数。
00010111
&
00000001
结果是，00000001，所有b是奇数。
5.^判断两个数是否相等
只需要对两个数进行异或运算后，如果结果为0则证明相等，否则不相等。
假设a=3,b=4,c=3,判断a==b,a==c是否成立。
a的二进制，0011
b的二进制，0100
c的二进制，0011
0011
^
0100
结果为，0111，结果不为零，所以a!=b
0011
^
0011
结果为，0000，结果为零，所以a==c
6.^交换两个数值
假设现在有两个数值a=4,b=9,交换这两个数,只需要执行
a^=b
b^=a
a^=b
计算过程：
已知a=0100,b=1001
0100
^
1001
结果：a=1101,b=1001
1001
^
1101
结果：b=0100,a=1101
1101
^
0100
结果：a=1001,b=0100
7.位运算实现加减乘除
加法运算
使用位运算实现加法运算主要分为两个部分。
假设需要对a,b两个值进行加法运算，
步骤一，先计算完全不考虑进位进行相加的值，通过异或操作来实现。a = a^b，a即是不考虑进位相加后的值。
步骤二，计算只考虑进位的产生值，通过（a&b）<<1可以得到只考虑进位产生的值，将这个值赋值给b,即b=(（a&b）<<1)。如果计算出来的b值不等于0，就说明发生了进位，就需要重复步骤一和步骤二，直到b的值为0。
例子：假设a=12,b=19,通过位运算来实现a+b。
a的二进制数：00001100
b的二进制数：00010011
先执行异或操作，算出a+b不考虑进位的情况下，得到的值，什么叫不考虑进位的值？通过10进制的计算来说明不考虑进位的计算，或许能让人更容易理解。
还是a=13,b=19，计算a+b，
13
+
19
可以看到，个位上3+9=12，是发生了进位的，正常情况下（也就是考虑进位的情况下），需要向十位进1，得到的结果就是32,但是，在不考虑进位的情况下，得到的结果就是22，很明显，这个22并不是正确的计算结果，我们需要将这个22加上刚才3+9产生的进位值进行相加22+10，才是正确的值。那么回到二进制的计算分析过程，
00001101
^
00010011
结果是a =00011110，这是二进制进行不考虑进位情况下得出的结果。
再计算他们相加的过程有没有发生进位，通过(a&b)<<1
00001101
&
00010011
进行与运算得出的结果是00000001，然后向左移动1位，得到结果是
b=00000010，可以看到这个结果不为0，所以它是发生了进位。
所以需要重复步骤一和步骤二。下面就不再赘述，只是展示重复步骤的过程
第二次
00011110
^
00000010
a=00011100
b=00000100
第三次
00011100
^
00000100
a=00011000
b=00001000
第四次
00011000
^
00001000
a=00010000
b=00010000
第五次
00010000
^
00010000
a=00000000
b=00100000
第六次
00000000
^
00100000
a=00100000
b=00000000
这时候b等于0了，而a=00100000,也就是十进制的32，所以结果是正确的。
C++代码如下:
//方法一：使用循环
int bit_add(int a, int b)
{
int add, carry; //carry代表进位
int i = 1;
do {
add = a ^ b;
carry = (a & b) << 1;
a = add;
b = carry;
cout << "步骤" << i++ << ":" << add << "\n";
} while (carry != 0);
return add;
}
C++
输出结果：
减法运算
实现a – b只要实现a + (-b)即可。所以只要将a和b的相反数调用add函数就行。根据二进制数在机器中表达的规则，得到一个数的相反数，就是这个数的二进制数表达取反加1（补码）的结果。
int bit_subtract(int a, int b)
{
return bit_add(a, bit_add(~b, 1));
}
C++
下面的例子是计算13-19
结果：
乘法运算
用位运算实现乘法运算。a × b的结果可以写成 a?2^0?b_0+a?2^1?b_1+…a?2^i?b_i+…a?2^31?b_31. 其中b_i为0或1表示整数b的二进制表达中第i位的值（从右往左数）。该过程有点类似于求整数的N次方问题。具体实现参照如下代码：
这里只考虑了正整数相乘的结果。
int multi(int a, int b)
{
int res = 0;
while(b != 0)
{
if(b & 1 == 1)
//这里的add是二进制的加法运算函数
res = add(res, a);
a <<= 1;
b >>= 1;
}
return res;
}
C++
假设a=12,b=9,计算a*b。
a的二进制数：00001100
b的二进制数：00001001
第一遍：通过b&1判断最后一位是不是1，很明显b的最后一位是1，所以这个位上是会产生值得，所以
b&1的值为，00000001
res =00001100
a=00011000
b=00000100
第二遍：
b&1的值为，00000000,因为等于零，所以没有产生数值，所以res不变
res =00001100
a=00110000
b=00000010
第三遍：
b&1的值为，00000000,因为等于零，所以没有产生数值，所以res不变
res =00001100
a=01100000
b=00000001
第四遍：
b&1的值为，00000001,
res =01101100
a=11000000
b=00000000
这里b=0,计算结束，所以最好a*b的值为01101100，即十进制数108。
除法运算
用位运算实现除法运算其实就是乘法的逆运算。定义 res 表示除法的结果。首先将a向右移位31位，然后看能不能容下b，如果能，说明a/2^31可以包含一个b，等价于a可以包含一个b?2^31，令res的第31位为1，此时a的值应该为a?b?2^31；如果不能容下b，令res的第31位为0，a的值不变；接下来将a向右移位30位是否能容下b……重复步骤直到a?b?2^i=0。
以上过程只适用于a和b都不是负数的情况下，当a或b为负数时，可以先将a和b转成正数，计算完之后再判断res的真实符号就行。
除法实现到这一步已经可以解决绝大多数情况了。但是我们知道，32位最小整数的绝对值要比最大整数大，所以如果a或b等于最小值，是不能转换成相对应的正数的。这时候需要分情况考虑：
如果a和b都为最小值，直接返回1
如果a不为最小值，而b为最小值，那么a/b = 0，直接返回0
如果a为最小值，而b不为最小值。这时我们对a无能为力，但是我们可以让a增大一点点，计算出一个结果然后再修正一下就可以得到最终的结果。处理过程如下：
<1>计算(a+1)/b，结果记为c
<2>计算c?b
<3>计算(a?c?b)/b，结果记为rest
<4>计算c+rest
代码实现如下：
代码中的INT_MIN在标准头文件limits.h中定义。
#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)
在C/C++语言中，不能够直接使用-2147483648来代替最小负数，因为这不是一个数字，而是一个表达式。表达式的意思是对整数21473648取负，但是2147483648已经溢出了int的上限，所以定义为（-INT_MAX -1）。
C中int类型是32位的，范围是-2147483648到2147483647 。
（1）最轻微的上溢是INT_MAX + 1 :结果是 INT_MIN;
（2）最严重的上溢是INT_MAX + INT_MAX :结果是-2;
（3）最轻微的下溢是INT_MIN - 1:结果是是INT_MAX;
（4）最严重的下溢是INT_MIN + INT_MIN:结果是0
int divide(int a, int b)
{
if(b == 0)
cout<<"Input Error!"<<endl;
else if(a == INT_MIN && b == INT_MIN)
return 1;
else if(b == INT_MIN)
return 0;
else if(a == INT_MIN)
{
int c = div(a+1, b);
return add(c, div(minus1(a, multi(c, b)), b));
}
else
return div(a, b);
}
int div(int a, int b)
{
a = a >= 0? a : add(~a, 1);
b = b >= 0? b : add(~b, 1);
int res = 0;
for(int i=31; i>-1; i=minus1(i, 1))
{
if((a>>i) >= b)
{
res = res | (1<<i);
a = minus1(a, b << i);
}
}
return a >= 0 && b >= 0? add(~res, 1) : res;
}
C++
8.总结
位运算只能对整数进行操作。
9.参考文章
https://blog.csdn.net/sodacoco/article/details/79629208
https://www.jianshu.com/p/5d974bb015cf
https://blog.csdn.net/sodacoco/article/details/79629208
