浅显介绍“二进制枚举”算法

本文面向初学计算机，对计算机有兴趣的读者，介绍了一种算法，即二进制枚举。需要简单的C语言入门水平，也请各位技术大神多多指教。本文从位运算开始，由浅入深介绍了这种算法。

位运算

对于位运算，作为初识编程语言的初学者们，在刚学习它的时候可能会感觉到有些困惑：我用二进制干什么？

二进制世界

我想先向你介绍一下位运算符，方便以下的学习：“~”、“&”、“^”、“|”、“<>”，分别代表按位取反、按位与、按位异或、按位或、左移和右移。

1. 按位取反～：将二进制数的每一位改变。由于二进制只由0，1两个数组成，所以“改变”的意思就是把“0”换成“1”，把“1”换成“0”。比如：二进制数p=10010，则～p=01101。
2. 按位与&：这是双目运算符，也就是说需要两个数来进行运算。这是要把两个数的二进制的每一位来进行与运算。比如这两个数：p=1101，q=1001，那么p&q=1001。
3. 按位异或^：同样是双目运算符，同样是把两个数的每一位来进行比较。在数位上，如果两个数相同，则在结果中该数位为“0”，反之，如果两个数不同，则在结果中该数位为“1”。例如：p=1010，q=1001，则p^q=0011。
4. 按位或|：双目，和按位与&差不多，对每一位来进行或运算。例如：p=1101，q=1001，那么p|q=1101。
5. 左移<
6. 右移>>：双目，和左移类似，只不过需要舍弃，例如10001>>2=100。

这里，先来列举几个基本的应用：比如算2的n次方。在c语言中，要么直接写n个2相乘，要么调用pow函数。如果用了位运算，那么写法就简单很多：1<

还有按位异或，有一些数，在数组中保存着。在数组里，只有一个数仅出现一次，其余的数出现了两次，如何找到这个只出现了一次的数呢？桶排序，是可以的。我们也可以试试按位异或。你想，两个数按位异或，那出现了两次的数经过运算，岂不是相当于没有这个数？这样，经过遍历，把数组里的每一个数都进行按位异或运算，最后的那个结果就是只出现过一次的那个数了。

“0”“1”字符串

二进制枚举就是用来解决可以转化为“0”“1”字符串的问题的。“0”和“1”代表着两种状态：假与真。请你思考一下，一个5位的“0”“1”字符串，有几种写法？答案显然是2^5=32种。

从“00000”到“11111”，一共32个数，我们不去关心它中间是怎么变化的，就让一个变量i去变化，从0到31依次递增，这期间二进制的i一定能覆盖到所有的“0”“1”字符串的情况。这就是二进制枚举的原理，算是一种暴力枚举。

二进制枚举

我们用C++来实现二进制枚举。本文两道例题来自NEFU OJ。先来看一道题：

给出长度为n的数组,求能否从中选出若干个,使他们的和为K.如果可以,输出:Yes,否则输出No

第一行：输入N,K,为数组的长度和需要判断的和(2<=N<=20,1<=K<=10^9)

第二行：N个值，表示数组中元素的值(1<=a[i]<=10^6)

先来分析一下，要实现选出若干个数，可以把它抽象成“0”“1”字符串，“0”代表不选这个数，“1”代表选择这个数。那么我们的i要从0一直自增到2^n-1，来遍历所有的“0”“1”字符串情况。

那么问题来了，我们知道了所有的“0”“1”字符串的情况，如何把这些情况加工成我们需要的信息呢，即，在这道题中，怎么把选出来的数加在一起呢？也就是，怎么检查“0”“1”字符串中“0”“1”的情况呢？（请先思考再看下文）

C++示意图（请先思考）

再引入一个变量j，让它来起检查的作用。我们让j干这么一件事：让它等于1，去跟“0”“1”字符串作按位与运算，如果结果不为0，我们就判断出来了第一位是“1”；让它等于10，去跟“0”“1”字符串作按位与运算，如果结果不为0，我们就判断出来了第二位是“1”；如此循环下去，我们就可以检测出来“0”“1”字符串中“1”的情况了。

j怎么从1变到10呢？我们不难想到用“<

以下为本题的代码：（由于在头条编辑器的预览中缩进全部被取消，我会再附一张图片版）

<code>#include <bits>
using namespace std;

int main()
{
    int n,k,i,j,sum,judge;
    int a[1000];
    while(cin>>n>>k)
    {
        judge=0;
        for(i=0;i        {
            cin>>a[i];
        }
        for(i=0;i        {
            sum=0;
            for(j=0;j            {
                if(i&(1<                {
                    sum=sum+a[j]; 

                }
            }
            if(sum==k)
            {
                judge=1;
                break;
            }
        }
        if(judge==1)
        {
            cout<        }
        else
        {
            cout<        }
    }
    return 0;
}/<bits>/<code>

图片版：

代码的核心，即二进制枚举的部分在这里：

<code>for(i=0;i{
    sum=0;
    for(j=0;j    {
        if(i&(1<        {
            sum=sum+a[j];
        }
    }
    if(sum==k)
    {
        judge=1;
        break;
    }
}/<code>

图片版：

再来看一个题：商店里有n朵花,四糸乃有w元钱。n朵花各不相同，四糸乃要买这n朵花其中的其中的若干朵。由于四糸乃很喜欢4这个数字，所以她希望她买的花的朵数是4的倍数，并且买完花后剩下的钱（可以为0）也是4的倍数。此外，因为已经来到花店了，所以四糸乃不能一朵花也不买。因为花店接下来还要做生意，四糸乃也不能将这n朵花全部买走。那么四糸乃一共有多少种买花方案呢？

测试数据共三行。

第一行是一个整数n表示有n朵花。（2<=n<=22）

第二行有n个整数，分别表示这n朵花的价格a[i]。（1<=a[i]<=1e7）

第三行是一个整数w代表四糸乃开始时持有的钱数（1<=w<=1e8）

分析一下，我们依然可以创建一个n位的“0”“1”字符串，只是这回增加了许多限制。

代码如下：

<code>#include <bits>
using namespace std;

int a[100],n,w;
int main()
{
    int i,j,flowersum=0,num=0,spend=0; 

    cin>>n;
    for(i=0;i    {
        cin>>a[i];
    }
    cin>>w;
    for(i=0;i    {
        flowersum=0;
        spend=0;
        for(j=0;j        {
            if(i&(1<            {
                flowersum++;
                spend=spend+a[j];
                if(spend>w)
                {
                    break;
                }
            }
        }
        if((w-spend)>=0&&(w-spend)%4==0&&flowersum%4==0&&flowersum!=n&&flowersum>0)
        {
            num++;
        }
    }
    cout<    return 0;
}/<bits>/<code>

图片版：

总结

两道题之后，我们可以总结出二进制枚举的套路：一个大循环，遍历所有的字符串；里面一个小循环，检查所有的“0”“1”情况。代码如下：

<code>for(i=0;i{
    //初始化
    for(j=0;j    {
        if(i&(1<        {
            //检测到“1”之后的动作
        }
    }
    
}/<code>

图片版：

閱讀更多 磅礴力量 的文章

關鍵字: 电脑 编程语言 算法