C言語ビット演算子まとめ

C                ,              ,               ,    c               .

一.C言語ビット演算子の概要
C言語のビット演算子は6種類あり、それぞれ:
>>右シフト演算子
<<左シフト演算子
&ビット単位と演算子
|ビット単位または演算子
^ビット別OR演算子
~ビット単位逆演算子
これらの演算子はいずれも基本データ型のバイナリビットに対して動作し,ここでは整数データ型のビット演算のみについて論じる.
二.各演算子の具体的な使用
>>右シフト演算子:整数のバイナリ形式を全体的に右に移動します.移動後、左に欠けているビットの充填はコンパイラに依存します.算術の右シフトか論理の右シフトかもしれません.
<<左シフト演算子:整数のバイナリ形式全体を左に移動し、移動後右に欠けたビットを0で補完
論理右シフト:シフト中、シンボルビットの左側に新しいビットが移動する可能性があります.シフトした新しいビットは0で埋め込まれ、論理と呼ばれます.
しゅうへんい
算術右シフト:シフト中、シンボルビットの左側に新しいビットが移動する可能性があります.移動する新しいビットはシンボルビットによって決定され、シンボルビットは
1は移入された新しいビットを1で補い,符号ビットを0にすると0で補い,原数の正負を一定に保つようなシフト
方式を算術シフトと呼ぶ.
具体的に論理右シフトか算術右シフトかは、コンパイラ(私が使用しているコンパイラはvs、算術右シフト)に依存します.
注意:論理左シフトと算術左シフトはありません
例:

int a = 10;
int b = 20;
int c = -2;
int d = -25;
printf("%d
",a>>1);
printf("%d
",b<<2);
printf("%d
",c<<2);
printf("%d
",d>>3);
    :
5
40
-8
-4

分析:
10(28個0)1010
右シフト1ビット0(28個0)101=5
ビット演算に接触したばかりの頃、dの変位結果は理解できませんでした.
理由:
-25バイナリは1(26個0)11001
変位後1111(26個0)11の結果はどう見ても-4ではない
実際に計算機のシフト演算では,正数と負数の演算はいずれも補符号を用いた形式で演算される.
正数の符号=正数の符号
負数の補符号=負数の原符号は符号ビットを除いてビット別に逆+1をとる.
負数の原符号=(負数の補符号-1)符号ビットを除いてビット毎に逆
負数の記憶も実際には負数の補符号で記憶されている
だから
-25バイナリは1(26個0)11001
-25プログラムでは1(26個1)00111
変位後1111(26個1)00
さらにバイナリ符号形式1(26個0)00100に-4
 
&2つのオペランドのバイナリをビットと演算子で行い、1&1=1,1&0=0,0&1=0,0&0=0,0&0=0
|2つのオペランドのバイナリをビットまたは演算子ごとに行い、1|1=1,1|0=1,0|1=1,0|0=0
例プログラム:

int a = -1;
int b = 2;
int c = 4;
printf("%d
",b & c );
printf("%d
", b | c );
printf("%d
",a & b );
printf("%d
", a | b );
  :
0
6
2
-1

正数は分析しない
負数か補数か
-1補コード1(29個1)11
2補コード0(29個0)10
ビット単位または演算を1(30個1)1にして負の原数に変換するとちょうど-1になります
ビットと演算を0(29個の0)10で2
^2つのオペランドのバイナリ数をビット別または演算子別に1^1=0,0^1=1,1^0=1とする.0^0=1
~取反演算子はオペランドのバイナリごとに行い、取反1->0,0->1
この2つの演算子も符号化に基づいて演算されます
三.ビット演算子の具体的な応用

           
void printBit(int a)
{
	int i = 31;
	while( i >= 0 )
	{
		printf("%d",a>>i & 1);
		i--;
	}
	printf("
");
}
               
void swap(int *a,int *b)
{
	*a = (*a)^(*b);
	*b = (*a)^(*b);
	*a = (*a)^(*b);
}
  a   n 
int getBit(int a, int n)
{
	return  a>>n & 1;
}
 a   n   0
void setBitZero(int *a,int n)
{
	(*a) = (*a) & ~(1<

四.ビット演算子を運用するACM問題
ボール番号を探す(一)
時間制限:3000 ms|メモリ制限:65535 KB
難易度:3
説明
ある国ではゲームが流行っています.ゲームのルールは、1つのボールに1つの整数番号i(0<=i<=1億1000万)があり、番号は繰り返すことができ、現在はランダムな整数k(0<=k<=1億1000万100)と言い、kのボールがこのボールの中にあるかどうかを判断し(「YES」が存在し、そうでなければ「NO」)、先に答えた者が勝つ.今、このゲームをしたい人がいますが、彼は怠け者です.彼はあなたが彼の勝利を助けることを望んでいる.
入力
1行目には2つの整数m,n(0<=n<=100000,0<=m<=100000)がある.mはこのボールの山にm個のボールがあることを示し、nはこのゲームがn回行われることを示している.次にm+n個の整数を入力し、前のm個はそれぞれこのm個のボールの番号iを表し、後のn個はそれぞれゲーム毎のランダム整数kを表す
しゅつりょく
出力「YES」または「NO」
サンプル入力
6 4
23 34 46 768 343 343
2 4 23 343
サンプル出力
NO
NO
YES
YES
この問題は1つの難題ではありませんて、解法はとても多くて、データ量が比較的に大きいため、解く時間の制限の上でとても多種の方法はタイムアウトすることができて、この問題は私が作ったが、運行時間の上で遅れすぎて、私はc++stlの中のsetの実現を使って、2700+msを使って、メモリも多く使って、以下は1つの比較的に良い方法を貼ります:

#define MAXN 3125010
int vis[MAXN] = {0} ;
int main()
{
	int m , n , x ;
	int i ;
	scanf("%d%d", &m , &n ) ;
	for( i = 0 ; i < m ; ++i )
	{
		scanf("%d", &x ) ;
		vis[ x / 32 ] |= 1 << x % 32 ;
	}
	for( i = 0 ; i < n ; ++i )
	{
		scanf("%d", &x ) ;
		if( vis[ x / 32 ] & ( 1 << x % 32 ) )
			printf("YES
");
		else
			printf("NO
");
	}
	return 0 ;
}

c言語のビット演算子を用いて,配列の1つのメモリ空間に32個の数字が存在するか否かの情報を格納することで,メモリ空間を節約するとともに,数字を検索する際の時間の複雑さをO(1)にする.