C/C++ACMビット演算バイナリ列挙

ビット演算
バイナリ演算子
1、と(&)
2つの数の各バイナリビットについて1回の演算を行います.2つの数に対応するバイナリビットが同じであれば、結果は1です.そうでなければ、0は次のようになります.

  A = 60(0011 1100) 
  B = 13(0000 1101)
A&B = 12(0000 1100)

2、または(|)
2つの数の各バイナリビットについて1回または演算を行います.2つの数に対応するバイナリビットが同じであれば、結果は0になります.そうでなければ、1は次のようになります.

  A = 60(0011 1100) 
  B = 13(0000 1101)
A|B = 61(0011 1101)

3、非/ビットによる反転(~)
2つの数の各バイナリビットについて1回の取反演算を行い、そのバイナリビットが0であれば1、1となり、0となる.

 A = 60 (0011 1100)
~A = 195(1100 0011)

4、異或演算(^)
2つの数の各バイナリビットについて1回の異和演算を行い、2つの数に対応するバイナリビットが異なる場合、演算結果は1であり、同じ場合は0である.

  A = 60(0011 1100)
  B = 13(0000 1101)
A^B = 49(0011 0001)

以下の性質を有する.

異または半加演算とも呼ばれ、その演算法則は進位を持たないバイナリ加算

に相当する.

1個の数が異なるか、同じ数が2回あると、結果は元の数になります.すなわち(a^b)^b=a

0異または任意の数で、結果はその数、すなわち0^a=a

に等しい.
バイナリシフトオペレータ
1、左に移動(<
例えば、A=5(0101)左に1ビット移動すると、A<<1の結果は1010、10進数の10となる.バイナリでの左シフトは乗二操作であり,c/c++での左シフト演算速度は乗二速度よりも速い.
2、右に移動(>>>)
例えば、A=5(0101)右向きに1ビット移動するとA>>1の結果が0010となり、10進数の2となる.バイナリの左シフトは、2つの除去操作(余剰数を切り捨てる)です.
以上の演算方法に基づいて,次にバイナリ列挙を行うことができる.
バイナリ列挙
nビットのバイナリ数は2 n個あり,1つのn個の要素の集合のサブセット数も2 n個であるため,バイナリの1 0と集合中の要素を結びつけることで組み合わせることができる.
バイナリ列挙では、通常、次の方法が使用されます.

バイナリにとって1はこの要素を表す0はこの要素を取らない

を表す.

および0が存在する位置は、要素の位置

を表す.
5つの要素があるとします.

バイナリ00000は、何も取らない

を表します.

10000代表取a

01000代表取b

11000代表取a,b

だから列挙の範囲は00000から11111、つまり0から1<

したがって、バイナリ列挙被列挙要素には、ランプのスイッチのような2つのケースしかありません.1つのものを取るか取らないか...
関連テーマ:大一冬休み訓練四(バイナリ列挙)2020.01.03
Code
一例として、NEFU OJ Problem 1205:とK-バイナリ列挙のために長さnの配列を与えて、その中からいくつかを選んで、彼らの和をKにすることができるかどうかを求めて、出力:Yes、さもなくば出力No

#include 
using namespace std;

int main()
{
	int n,k,num[20],sum;
	while(cin>>n>>k)
	{
		for(int i=0;i<n;i++)cin>>num[i]; //    
		//↓                 ，       
		for(int i=0;i<1<<n;i++) //    ，   2 n  
		{
			sum=0;
			for(int j=0;j<n;j++)
			{
				if(i&1<<j)sum+=num[j]; //     1   sum 
			}
			if(sum==k) //      k
			{
				printf("Yes
");
				k=-1;
				break;
			}
		}
		if(k!=-1)printf("No
");
	}
	return 0;
}