位运算骚操作---利用位运算求组合数

一道利用组合求和的例题

这道题乍一看就是把所有的组合给列举出来，然后求和看是否等于目标值，输出需要注意的是优先输出靠前的下标元素，那么这就很巧了朋友们，位运算恰好能优雅的实现这一操作。

位运算如何实现组合的呢？

• 我们先观察一下这道题，它需要的组合数是不确定的，也就是不知道是取几个数的组合，这样显然可以直接深搜，而我们同样也可以通过位运算实现，由于组合数不确定，则总的组合数就是 C n k ( 0 = < k < = n ) C_{n}^{k}(0=<k<=n) Cnk​(0=<k<=n)学过高中数学的显然都知道总和为2的n次方,当然你也可以直接看作n个数里面每个数有取和不取两种选择，总的选择就是这么多。
• 现在我们来聊聊二进制数的基本列举，比如0~7:000、001、010、011、100、101、110、111,我们如果假设有三个数字，1表示取该位置的数，0表示不取，那么这个0~7的二进制序列则就是完全列举了这3个数字的所有组合。
• 好了现在我们知道二进制序列可以直接表示几个数的所有组合，那么现在讨论如何通过位运算来进行取值，我们通过外层循环枚举所有的二进制序列，而内层循环通过(1<<j)&i(表示当前外层循环的序列)来表示j为能不能取，如果能取则表示i序列中的第j+1位为1，具体例子，比如上述提到的011用该公式表示的就是j=0和j=1时能取，这同样也是对应了一个组合，对应取数组中的nums[0]和nums[1]。通过不断这样枚举所有的二进制序列来告诉机器此次该取nums哪个位置的元素，这样就枚举出了nums数组的所有取值组合。

解题代码

可以考虑通过x&(x-1）通过每次对1进行消耗来优化一下效率。

#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
int T;
cin>>n;
int nums[n];
for (int i = 0; i < n; i++)cin>>nums[i];
cin>>T;
//用1左移n，用于方便表示长度为n的数组的二进制序列表，比如1<<3=1000,而长度为3的数组需要从001到111
int max = 1<<n;
int count = 0;
for(int i=1;i<max;i++){
    int x = i;
    int sum = 0;
    //计算所选取组合的sum
    for (int j = 0; j < n; j++){
        //一旦x为0，则1取完
        if(x==0)
            break;
        if(x&(1<<j)){
            sum += nums[j];
            //每次消耗一个1
            x = x&(x-1);
        }
    }//若sum和为目标值T则输出
   if(sum==T){
       int t = i;
       for(int j = 0; j < n; j++){
           if(t==0)
            break;
        if(t&(1<<j)){
            cout<<nums[j]<<" ";
            //每次消耗一个1
            t = t&(t-1);
       } 
   }
    count++;
    cout<<endl;
}
}
cout<<count;
return 0;
}