[C++知识库]c++位运算技巧

选数
??首先先放上一道算法题（c++），一道基础题。解法很多，搜索，枚举都可以。今天以枚举来讲解这道题。不再赘述题干。
??最容易想到的办法，大概就是两重循环枚举吧。外循环控制执行次数，内循环执行寻找k个数，然后，相加并判断是否为素数。内循环的实现可以用递归或者是搜索。思路很简单，但却很容易超时。那么，思路该是怎样的呢？观察数据量，n=20,k<n。暗示性极强呀，复杂度就是O(2^n)呗。那不就是枚举n的所有子集，选取其中为k个数的子集。
??如果，我们将集合中，每个元素出现标记为1，不出现标记为0.那么自然也就是(2ⁿ)种情况呀。也就是原问题的每一个子集，对应一个二进制数.最大值是2ⁿ-1。同样地也对应于一个10进制数(<2ⁿ-1)。这作为我们思路的出发点。
??那么，问题自然就是，当给出一个10进制数(<2ⁿ-1)，当它对应的二进制数中含有k个1时，将这k个1所对应的元素求和，并判断是否为素数即可。思路已经理清。再细化即可得出代码。
（1）枚举0-(2ⁿ-1)（此处可以进一步缩小枚举范围，不缩小也不超时）。
（2）对于10进制数，判断对应的二进制的1的个数。一方面可以自己实现，但是c++提供了接口函数__builtin_popcount()，输入是10进制数，返回的是该数对应的二进制数中1的个数（接口的头文件是cstdio或者iostream）。
（3）找二进制中1所对应的元素。对于n个数中的第i个数而言，如果它出现了(它对应的十进制数记为S)，那么1<<(i-1)&S==1位true。反之为false。
（这一点建议结合代码理解）。接着，求和
（4）素数判断，略过。
AC源代码，如下：

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=25;
long long cnt;
bool check(int n){
	for(int i=2;i*i<n;i++){
		if(n%i==0) return false;
	}
	return true;
}
int main(){
	int n,k,a[maxn];
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int U=1<<n;
	for(int S=0;S<U-1;S++){
		if(__builtin_popcount(S)==k){
			int sum=0;
			for(int i=1;i<=n;i++){
				if((1<<(i-1))&S) sum+=a[i];
			}
			if(check(sum)) cnt++;
		}
	}
	cout<<cnt;
	return 0;
}