位运算

内容

消去x最后一位的1

x&(x-1)

比如: 十进制数10的二进制为1010,9的二进制数为1001,那么(1010)&(1001)=1000,现在10的二进制中最后一位的1已经被消去

用途:

  1. 可以用来检测一个数是不是2的幂次。

    如果一个数x是2的幂次,那么x>0x的二进制中只有一个1,所以用x&(x-1)把1消去,应该返回0,如果返回了非0值,证明不是2的幂次

  2. 计算一个整数二进制中1的个数

    因为1可以不断的通过x&(x-1)这个操作消去,所以当最后的值变成0的时候,也就求出了二进制中1的个数

  3. 如果将整数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;

用途:

  1. 数组中,只有一个数出现一次,剩下都出现两次,找出出现一次的数

    因为剩下的都出现了两次,那么异或值肯定为0,所以把所有的数异或起来得到的值就是那个数,可以做一下nyoj-528找球号(三)

  2. 其他的用途基本都可以通过这个推出来,想到再写

results matching ""

    No results matching ""