C++中巧妙的位运算

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

位运算要多想到与预算和异或运算，并常常将两个数对应位上相同和不同分开处理

一、x&（x-1）消除x二进制中最右边的一个1。

这个比较厉害，比如统计某个

二、与和异或的巧妙结合的思想

与运算可以取出两个二进制数中都有1的部分，异或可以求出两个二进制数中只有一个有1的部分，所以运用位运算的时候可以将两个数用与和异或拆成两部分分别运算，然后在将结果合并。

1、(x&y)+((x^y)>>1）来求x、y的平均数

分析如下：

第一步：x,y对应位均为1，相加后再除以2还是原来的数，如两个00001111相加后除以2仍得00001111。
第二部，对应位有且只有一位为1，用“异或”运算提取出来，然后>>1(右移一位，相当于除以2），即到到第二部分的平均值。
第三部，对应位均为零，因为相加后再除以二还是0，所以不用计算。
三部分汇总之后就是(x&y)+((x^y)>>1)

2、用位运算求两个数的和

一样的思想只不过要用的递归

1 int add(int a,int b)
2 {
3 if(b==0)
4 return a;
5 int sum,carry;
6 sum=a^b;
7 carry=(a&b)<<1;
8 return add(sum,carry);
9 }

3、不使用中间变量，将a、b两个数的值对换

这个只用到异或就可以了

a=a^b;

b=a^b;

a=a^b;