内容
消去x最后一位的1
x&(x-1)
1
比如: 十进制数10的二进制为1010,9的二进制数为1001,那么(1010)&(1001)=1000，现在10的二进制中最后一位的1已经被消去
用途:
可以用来检测一个数是不是2的幂次。
如果一个数x是2的幂次，那么x>0且x的二进制中只有一个1,所以用x&(x-1)把1消去，应该返回0，如果返回了非0值，证明不是2的幂次
计算一个整数二进制中1的个数
因为1可以不断的通过x&(x-1)这个操作消去，所以当最后的值变成0的时候，也就求出了二进制中1的个数
如果将整数A转换成整数B,需要改变多少个比特位.
思考将整数A转换为B，如果A和B在第i（0<=i<32）个位上相等，则不需要改变这个BIT位，如果在第i位上不相等，则需要改变这个BIT位。所以问题转化为了A和B有多少个BIT位不相同。联想到位运算有一个异或操作，相同为0，相异为1，所以问题转变成了计算A异或B之后这个数中1的个数
其他常用操作:
功能 示例 位运算
去掉最后一位 (101101->10110) x shr 1
在最后加一个0 (101101->1011010) x shl 1
在最后加一个1 (101101->1011011) x shl 1+1
把最后一位变成1 (101100->101101) x or 1
把最后一位变成0 (101101->101100) x or 1-1
最后一位取反 (101101->101100) x xor 1
把右数第k位变成1 (101001->101101,k=3) x or (1 shl (k-1))
把右数第k位变成0 (101101->101001,k=3) x and not (1 shl (k-1))
右数第k位取反 (101001->101101,k=3) x xor (1 shl (k-1))
取末三位 (1101101->101) x and 7
取末k位 (1101101->1101,k=5) x and (1 shl k-1)
取右数第k位 (1101101->1,k=4) x shr (k-1) and 1
把末k位变成1 (101001->101111,k=4) x or (1 shl k-1)
末k位取反 (101001->100110,k=4) x xor (1 shl k-1)
把右边连续的1变成0 (100101111->100100000) x and (x+1)
把右起第一个0变成1 (100101111->100111111) x or (x+1)
把右边连续的0变成1 (11011000->11011111) x or (x-1)
取右边连续的1 (100101111->1111) (x xor (x+1)) shr 1
去掉右起第一个1的左边 (100101000->1000) x and (x xor (x-1))
利用二进制来枚举子集
具体请看博客: 二进制枚举子集详解
异或操作
异或的性质:
x^x=0;
x^0=x;
1
2
用途:
数组中，只有一个数出现一次，剩下都出现两次，找出出现一次的数
因为剩下的都出现了两次，那么异或值肯定为0，所以把所有的数异或起来得到的值就是那个数，可以做一下nyoj-528找球号(三)
其他的用途基本都可以通过这个推出来，想到再写
转载一个博客
位运算，相比普通的代码最大的优点就是其带来的高效性，也因此可以常在底层源码中看见它们的踪影。
本文就位运算常见的操作作一个总结，若您另有关于位运算巧妙的运用可以于底部留言区留言。
首先还是先来回顾下位操作的基础知识。（除非特别说明，否则以下都以2进制为例）
相关基础
1. 与运算
与运算符”&”是双目运算符。只有对应的两个二进位均为1时，结果位才为1，否则为0。例如：
9 & 5 = 00001001
& 00000101
= 00000001
= 1
1
2
3
4
2. 或运算
或运算符”|”是双目运算符。只要对应的两个二进位有一个为1时，结果位就为1。例如：
9 | 5 = 00001001
| 00000101
= 00001101
= 13
1
2
3
4
3. 非运算
非运算符” ~ “为单目运算符。其功能是对参与运算的各二进位求反。例如：
~ 9 = ~ 00001001
= 11110110
= -10
1
2
3
4. 异或运算
异或运算符” ^ “是双目运算符。其功能是对参与运算的二进位相异或，即当两二进位相异时，结果为1，相同就为0。例如：
9 ^ 5 = 00001001
^ 00000101
= 00001100
= 12
1
2
3
4
5. 左移和右移
例1 例2
x 01100011
x << 4 00110000
x >> 4(逻辑右移) 00000110
x >> 4(算术右移) 00000110
左移动就是向左移动k位，丢弃最高的k位，并在右端补k个0，也就是常说的当前值乘以2的k次方。
右移动的原理也是相同的，右移k位就是当前数除以2的k次方。唯一不同的是分为逻辑右移和算术右移。
逻辑右移就是无符号移位，右移几位，就在左端补几个0。
算术右移动是有符号移位，和逻辑右移不同的是，算术右移是在左端补k个最高有效位的值，如此看着有些奇特，但对有符号整数数据的运算非常有用。我们知道有符号的数，首位字节，是用来表示数字的正负（1为负）。负数采用补码形式来存储，比如-26（11100110），算术右移1位之后-13（11110011）。如若不是补最高有效位的值1而是补作0的话，右移之后就变成正数了。
经典应用
1. i+(~i)=-1
i取反再与i相加，相当于把所有二进制位设为1，其十进制结果为-1。
2. 计算n+1与n-1
-~n == n + 1，~n为其取反，负号 ’ - ’ 再对其取反并加1。
~-n == n - 1，思路就是找到最低位的第一个1，对其取反并把该位后的所有位也取反，即01001000变为01000111。
3. 取相反数
思路就是取反并加1，也即~n + 1或者(n ^ -1) + 1。
4. if(x == a) x = b; if(x == b) x = a;
利用^运算符的性质，即得x = a ^ b ^ x。
5. n倍数补全
当n为2的幂时，(x + n - 1) & ~(n - 1)会找到第一个大于x的数，且它正好是n的整数倍。
6. 求二进制中1的个数
/* Version 1 */
int count_1_bits(int n)
{
int count = 0;
while (n)
{
count++;
n = n & (n - 1);
}
return count;
}
/* Version 2 */
int count_1_bits(int n)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
return x;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
关于第二个版本，分析如下：（摘自Matrix67-位运算，并作稍微修改）
以十进制数211为例，其二进制为11010011，
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <— 原数
+---+---+---+---+---+---+---+---+
| 1 0 | 0 1 | 0 0 | 1 0 | <— 第一次运算后
+-------+-------+-------+-------+
| 0 0 1 1 | 0 0 1 0 | <— 第二次运算后
+---------------+---------------+
| 0 0 0 0 0 1 0 1 | <— 第三次运算后，得数为 5
+-------------------------------+
1
2
3
4
5
6
7
8
整个程序是一个分治的思想。第一次我们把每相邻的两位加起来，得到每两位里1的个数，比如前两位10就表示原数的前两位有2个1。第二次我们继续两两相加，10+01=11，00+10=10，得到的结果是00110010，它表示原数前4位有3个1，末4位有2个1。最后一次我们把0011和0010加起来，得到的就是整个二进制中1的个数。
7. 判断二进制中1的奇偶性
x = x ^ (x >> 1);
x = x ^ (x >> 2);
x = x ^ (x >> 4);
x = x ^ (x >> 8);
x = x ^ (x >> 16);
cout << (x & 1) << endl; // 输出 1 为奇数
1
2
3
4
5
6
7
以下分析摘自Matrix67-位运算，并作稍微修改，
以十进制数1314520为例，其二进制为0001 0100 0000 1110 1101 1000。
第一次异或操作的结果如下：
0001 0100 0000 1110 1101 1000
^ 0000 1010 0000 0111 0110 1100
= 0001 1110 0000 1001 1011 0100
1
2
3
得到的结果是一个新的二进制数，其中右起第i位上的数表示原数中第i和i+1位上有奇数个1还是偶数个1。比如，最右边那个0表示原数末两位有偶数个1，右起第3位上的1就表示原数的这个位置和前一个位置中有奇数个1。
对这个数进行第二次异或的结果如下：
0001 1110 0000 1001 1011 0100
^ 0000 0111 1000 0010 0110 1101
= 0001 1001 1000 1011 1101 1001
1
2
3
结果里的每个1表示原数的该位置及其前面三个位置中共有奇数个1，每个0就表示原数对应的四个位置上共偶数个1。
一直做到第五次异或结束后，得到的二进制数的最末位就表示整个32位数里1的奇偶性。
8. 判断奇偶性
/* 判断是否是奇数 */
bool is_odd(int n)
{
return (n & 1 == 1);
}
1
2
3
4
5
9. 不用临时变量交换两个数
/* 此方法对 a 和 b 相等的情况不适用 */
a ^= b;
b ^= a; // 相当于 b = b ^ ( a ^ b );
a ^= b;
1
2
3
4
10. 取绝对值
/* 注意：以下的数字 31 是针对 int 大小为 32 而言 */
int abs(int n)
{
return (n ^ (n >> 31)) - (n >> 31);
}
1
2
3
4
5
其中n >> 31取得n的正负号。
若n为正数，n >> 31的所有位等于0，其值等于0。表达式转化为n ^ 0 - 0，等于n；
若n为负数，n >> 31的所有位等于1，其值等于-1。表达式转化为(n ^ -1) + 1，这很好理解，负数的相反数就是对其补码取反再加1，(n ^ -1) + 1就是在做这样的事。
11. 取两数的较大值
/* 注意：以下的数字 31 是针对 int 大小为 32 而言 */
int max(int a, int b)
{
return (b & ((a - b) >> 31)) | (a & (~(a - b) >> 31));
}
1
2
3
4
5
如果a >= b，(a - b) >> 31为0，否则为-1。
12. 判断符号是否相同
/* 若 x，y 都为 0，输出真；若只有一个为 0，不会报错但运行结果是错的，因为 0 没有正负之分 */
bool is_same_sign(int x, int y)
{
return (x ^ y) >= 0;
}
1
2
3
4
5
13. 判断一个数是不是2的幂
bool is_power_of_two(int n)
{
return (n > 0) ? (n & (n - 1)) == 0 : false;
}
1
2
3
4
如果是2的幂，n - 1就是把n的二进制的最低的那个1取反为0，并把后面的0全部取反为1。
14. 取余2的幂次方
/* 其中 m 为 2 的幂次方，并对 m 取余 */
int mod(int n, int m)
{
return n & (m - 1);
}