MENU

从位运算看二进制枚举

April 23, 2020 • Read: 609 • 算法

位运算符

在C语言中,数据是以二进制存在的,比如2的二进制表示就是10,3的二进制表示就是11……

既然有二进制,那么肯定也有类似于十进制一样的运算方法了。C语言中提供了六种运算符:

运算符&|^~<<>>
说明按位与按位或按位异或取反左移右移

解释:

  1. 按位与(&):在二进制的位上,只有两个值都为1,按位与的结果才为1,否则为0,例如 1&1=1(001 & 001),2&1=0(010 & 001)
  2. 按位或(|):在二进制的位上,两个值中任意一个为1,按位与的结果就是1,全为0时结果为0,例如1|1=1(001 | 001 = 001),2|1=3(010 | 001 = 011),0|0=0(000 | 000=000)
  3. 按位异或(^):在二进制位上的值不同时,值为1,否则为0,例如 1^1=0(001 ^ 001= 000),2^1=3(010 ^ 001= 011)
  4. 取反(~):单目运算符,右结合性,即:将每一位上的数字取反,~1=-2 (-010),~0=-1(-001)
  5. 左移(<<):将二进制位上的每一位都向左移动,例如:1<<2=4(001 => 100),左移n位的结果相当于乘以2的n次方,其中(1<<n)可以生成第n位的零,比如1<<15=1000000000000000,后有15个零
  6. 右移(>>): 将二进制位上的每一位都向右移动,例如:4>>2=1(100 => 001),右移n位的结果相当于除以2的n次方

二进制枚举

情景1:

我这里有4个不同的水果,n块钱,每个水果的价格分别为:k1,k2,k3,k4,问:请问我的钱最多能同时买那几个水果?

对于这个情景,因为水果只有4个,所以数据量很小,所以使用暴力枚举法就能过,用两个for循环?不不不,我们使用二进制枚举

首先,1<<4 = 10000(二进制表示),所以1<<4-1=1111(二进制表示)=15(十进制表示),如果从0开始数,则有16个数。我们来看看这16个数:

00 = 0000
01 = 0001
02 = 0010
03 = 0011
04 = 0100
05 = 0101
06 = 0110
07 = 0111
08 = 1000
09 = 1001
10 = 1010
11 = 1011
12 = 1100
13 = 1101
14 = 1110
15 = 1111

我对上面的数据进行了填0处理,以便看的更清晰

我们仔细看看这16个数,你是不是看出一点名堂?如果把每一位上的0或1表示为买或者不买,那么上述的16个数的二进制结果,就表示了这4个水果的所有购买方式!

那么,我们应当如何检索上面的每种可能呢?

前面我们又说到,1<<n可以生成n个0位的数,最前面的为1,例如(1<<4=10000),再利用按位与(&)运算符,就能知道这一位表示的是0还是1

例如,我想知道 2 所代表的二进制位上哪些位为0,哪些位为1,就可以有

for (int j=0;j<n;i++)
{
    if (2&(1<<j))
    {
        printf("%d",j);
    }
}

运行结果为:1,也就是说,只有1号位上为1,其余位置都为0. (2=》0010)

利用这个原理,就可以快速对结果进行遍历了

模板如下:

for(int i=0;i<(1<<n);i++)
{
    for (int j=0;j<n;j++)
    {
        if (i&(1<<j))
        {
            ……
        }
    }
}

例题:

林大oj-和为K

Last Modified: April 26, 2020
Archives Tip
QR Code for this page
Tipping QR Code