淺顯介紹“二進制枚舉”算法

本文面向初學計算機，對計算機有興趣的讀者，介紹了一種算法，即二進制枚舉。需要簡單的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>

圖片版：

閱讀更多 磅礴力量 的文章

關鍵字: 算法 C語言 二進制