位运算
内容
消去x最后一位的1
x&(x-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)) |
利用二进制来枚举子集
假设我们现在有5个小球，上面分别标号了0,1,2,3,4代表这些小球的权值,现在要像你求出这些小球的权值可以组成的所有情况。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n=5;//5个小球
for(int i=0; i<(1<<n); i++) //从0～2^5-1个状态
{
for(int j=0; j<n; j++) //遍历二进制的每一位
{
if(i&(1<<j))//判断二进制第j位是否存在
{
printf("%d ",j);//如果存在输出第j个元素
}
}
printf("\n");
}
return 0;
}
异或操作
异或的性质:
x^x=0;
x^0=x;
用途:
数组中，只有一个数出现一次，剩下都出现两次，找出出现一次的数
因为剩下的都出现了两次，那么异或值肯定为0，所以把所有的数异或起来得到的值就是那个数，可以做一下
nyoj-528找球号(三)其他的用途基本都可以通过这个推出来，想到再写