ビット演算子とその応用
一、C言語の六種類のビット演算子:
&ビット単位と
|ビット単位または
^按位异或
~取反
<<左シフト
>>右に移動
1.ビットと演算
ビットと演算子「&」は両目演算子です.
その機能は,演算に関与する2数のそれぞれに対応する2進位相とである.対応する2つのバイナリがいずれも1の場合のみ、結果ビットは1であり、そうでなければ0である.演算に関与する数は符号化方式で現れる.
例えば、9&5書き込み可能な演算式は、00001001(9のバイナリ符号化)&00000101(5のバイナリ符号化)000001(1のバイナリ符号化)可視9&5=1である.
ビットと演算は、通常、特定のビットに対して0をクリアしたり、特定のビットを保持したりするために使用されます.例えば、aの上位8ビットを0にし、下位8ビットを保持し、a&255演算(255のバイナリ数は000000001111111)を行うことができる.
2.ビット単位または演算
ビットまたは演算子「|」は両目演算子です.
その機能は,演算に関与する2数のそれぞれに対応する2進位相または.対応する2つの2進位のうち1つが1であれば,結果ビットは1である.演算に関与する2つの数はいずれも符号化で現れる.
例えば、9|5書き込み可能な演算式は、00001001|00000101
00001101(10進数13)可視9|5=13
3.ビット別または演算
ビット別OR演算子「^」は両目演算子です.
その機能は、演算に関与する2つの数がそれぞれ対応する2進位相が異なる場合、または、2つの対応する2進位相が異なる場合、結果は1である.参加演算数は、まだ符号化されています.
例えば9^5は、00001001^00000101 00001100(10進数12)と書くことができる
4.逆演算を求める
求逆演算子～は単目演算子であり、右結合性を有する.
その機能は,演算に関与する数の各バイナリビットをビット毎に反転させることである.
例えば～9の演算:~(000000000001001)結果:1111111111110110
5.左シフト演算
左シフト演算子「<<」は両目演算子です.左シフトnビットは2を乗じたn次方である.
その機能は「<<」の左の演算数の各バイナリを全部左に数ビットシフトし、「<<」の右の数で移動するビット数を指定し、高位を捨て、低位を0に補う.
1)例:a<<4はaの各バイナリを左に4ビット移動することを指す.a=0000000011(10進3)の場合、左に4桁移動すると0011000(10進48)になります.
2)例:
int i = 1;
i = i << 2;//iの値を左に2桁ずらす
つまり、1の2進法は000...0001(ここでは1の前の0の個数はintの桁数に関係し、32ビットマシン、gccには31個の0がある)、2ビット左にシフトしてから000になる...0100、つまり10進数の4なので、左シフト1ビットは2を乗じたものに相当し、左シフトnビットは2を乗じたn次方である(符号数が完全に適用されない場合があり、左シフトが符号の変化を招く可能性があるため、以下に原因を説明する)
なお、intタイプの左端の符号ビットとシフトがシフト場合である.intはシンボルのある整形数であり,最左端の1ビットはシンボルビット,すなわち0正1負であり,シフト時にオーバーフローが生じることが知られている.
例:
int i = 0x40000000;//16進の4000000、2進の01000000...0000
i = i << 1;
では、iは1ビット左に移動すると0 x 8000000、つまり2進の100000になります...0000は、符号ビットが1にする、他のビットはすべて0であり、intタイプで表すことができる最小値となり、32ビットのintという値は-2174483648であり、オーバーフローする.次にiを1位左に移動するとどうなりますか?C言語では最上位を捨てる処理法を採用し,1を捨てるとiの値が0になる.
左シフトのうち、左シフトのビット数がこの数値タイプの最大ビット数を超えると、コンパイラは左シフトのビット数で型の最大ビット数を除去し、残りの数でシフトします.
int i = 1, j = 0x80000000;//intを32ビットとする
i = i << 33;//33%32=1左シフト1位、iが2になる
j = j << 33;//33%32=1左シフト1位、jは0となり、最上位は破棄される
このプログラムをgccでコンパイルするとき、コンパイラは左シフトビット数>=タイプ長というwarningを与える.実際にi,jが移動するのは1ビット,すなわち33%32後の剰余である.gccではこのルールですが、他のコンパイラが同じかどうかはまだ分かりません.
つまり左シフトは、最高位を捨て、0が最低位を補う
6.右シフト演算
右シフト演算子">>は両目演算子です.右シフトnビットは2で割ったn次方
その機能は「>>」の左の演算数の各2進位をすべて右にいくつかシフトし、「>>」の右の数は移動する桁数を指定することです.
例えば、a=15とし、a>>2は、000001111を00000011(10進3)に右シフトすることを示す.
なお、符号数がある場合は、右シフト時に符号ビットが追従して移動する.正数の場合、最高位補0、負数の場合、シンボルビットは1であり、最高位が補0または補1はコンパイルシステムの規定に依存する.Turbo Cと多くのシステムは補1と規定されている.
右シフト対シンボルビットの処理と左シフトは異なります.
符号付き整数の場合、intタイプなど、右に移動すると、符号ビットは保持されます.たとえば、次のようになります.
int i = 0x80000000;
i = i >> 1;//iの値は0 x 4000000にはなりませんが、0 xc 00000000になります.
つまり、符号数がある場合、符号ビットが右に移動した後、正数であれば0、負数であれば1、
シンボル数の場合、右に移動すると、シンボルビットは同じように移動します.
正数の場合、最高位は0を補い、
負数の場合、符号ビットは1となり、
つまりアセンブリ言語における算術の右シフトである.同様に、移動するビット数がタイプの長さを超えると、残数が取り、残数ビットが移動する.
最上位レベルが0または1を補うかは、コンパイルシステムの規定に依存する.Turbo Cと多くのシステムは補1と規定されている.
負数10100110>>5(文字長が8ビットであると仮定)では11111101が得られる
つまり、Cでは、左シフトは論理/算術左シフト(両者は全く同じ)であり、右シフトは算術右シフトであり、符号ビットを一定に保つ.実際の応用では、場合によっては左/右シフトで高速な乗除演算を行うことができる、これはサイクル効率よりもはるかに高い.x>>1;//x/=2 x<<1に相当する.//x*=2 x>>2に相当する. //x/=4x<<2; //x *= 4x>>3; //x/= 8x<<3;//x*=8このように押す.
符号なし:
もう一例見てください!
二、異或いは操作の妙用
1.特定位置を反転させるには、どのビットを反転させるか∧演算を行う位置を1とすればよい.
2と0相∧は、元の値を保持する.
3.一時変数を使用することなく、2つの値を交換する.
他の変数を導入することなく変数値の交換を実現できる
以下の操作を実行できます.
a = a^b; //(1) b = a^b; //(2) a = a^b; //(3)
異種またはオペレーションは結合法則と交換法則を満たし、任意の整数a^a=0について異種またはオペレーションの性質によって知られている.
証:(第(2)ステップのa)a=a^b=(第(1)ステップのbをbに代入する)a^(a^b)=b;
(第(3)ステップのb)b=a^b=(第(1)ステップのbをbに代入し、(2)ステップのaをaに代入する)a^b^a^b=a^a^b=a^a^b=a^a^b^b=a;
三、ビットと演算
1 . クリアA数では1のビット、Bでは対応するビットが0です.そして両者を＆演算することで、Aクリアの目的を達成することができます.
2 . 1つの数の中の特定のビット数Aのいくつかのビットを取って、数Bのいくつかの位置1を取って、数Aのいくつかのビットと1をビットとすればいいです.
3 . 1ビットを保持するメソッド数Aと数Bは＆演算され、数Bは数Aが保持するビット1にあり、残りのビットはゼロである.
4 .パリティは変数aのパリティを判断する.aと1はビットと演算を行い、結果が1であればaは奇数である.aと1をビットと演算し,結果が0であればaは偶数である.
4、適用例1.int型変数aが奇数であるか偶数a&1=0偶数a&1=1奇数2であるかを判定する.int型変数aのk位をとる
(k=0,1,2,・・sizeof(int)),すなわちa>>k&1.int型変数aのk番目のビットを0、すなわちa=a&~(1<>16-k(sizeof(int)=16とする)6.int型変数aはループ右シフトk回、すなわちa=a>>k|a<<16-k(sizeof(int)=16とする)7.整数の平均値2つの整数x,yに対して、(x+y)/2で平均値を求めると、x+yがINT_より大きくなる可能性があるため、オーバーフローが発生するMAXですが、平均値は緋出っ型ではないことを知っています.ǎ?/DIV>int average(int x,int y)/X,Yの平均値{return(x&y)+((x^y)>>1);8 . 1つの整数が2のべき乗かどうかを判断し、1つの数x>=0に対して、彼が2のべき乗boolean power 2(int x){return((x&(x-1)==0)&(x!=0)}9 tempで2つの整数void swap(int x,int y){x^=y;y^=x;x^=y;
php: $a ='dd'; $b = 'bb'; $a = $a ^ $b; $b = $a ^ $b; $a = $a ^ $b; echo $a,' ', $b; 10絶対値int abs(int x){int y;y=x>>31;return(x^y)-y;//or:(x+y)^y}の計算
11.型取り演算をビット演算に変換(オーバーフローが発生しない場合)a%(2^n)はa&(2^n-1)に等価
12乗算変換ビット演算(オーバーフローが発生しない場合)a*(2^n)はa<>n例:12/8==12>>3 14に等価である.a%2等価a&1(a&log 2(2))a%4等価a&2(a&log 2(4))
..... a%32はa&5に等しい
15 if (x == a) x= b; else x= a; x=a^b^xに等しい.16 xの逆数を(~x+1)と表す
&ビット単位と
|ビット単位または
^按位异或
~取反
<<左シフト
>>右に移動
1.ビットと演算
ビットと演算子「&」は両目演算子です.
その機能は,演算に関与する2数のそれぞれに対応する2進位相とである.対応する2つのバイナリがいずれも1の場合のみ、結果ビットは1であり、そうでなければ0である.演算に関与する数は符号化方式で現れる.
例えば、9&5書き込み可能な演算式は、00001001(9のバイナリ符号化)&00000101(5のバイナリ符号化)000001(1のバイナリ符号化)可視9&5=1である.
ビットと演算は、通常、特定のビットに対して0をクリアしたり、特定のビットを保持したりするために使用されます.例えば、aの上位8ビットを0にし、下位8ビットを保持し、a&255演算(255のバイナリ数は000000001111111)を行うことができる.
main(){
int a=9,b=5,c;
c=a&b;
printf("a=%d
b=%d
c=%d
",a,b,c);
}2.ビット単位または演算
ビットまたは演算子「|」は両目演算子です.
その機能は,演算に関与する2数のそれぞれに対応する2進位相または.対応する2つの2進位のうち1つが1であれば,結果ビットは1である.演算に関与する2つの数はいずれも符号化で現れる.
例えば、9|5書き込み可能な演算式は、00001001|00000101
00001101(10進数13)可視9|5=13
main(){
int a=9,b=5,c;
c=a|b;
printf("a=%d
b=%d
c=%d
",a,b,c);
3.ビット別または演算
ビット別OR演算子「^」は両目演算子です.
その機能は、演算に関与する2つの数がそれぞれ対応する2進位相が異なる場合、または、2つの対応する2進位相が異なる場合、結果は1である.参加演算数は、まだ符号化されています.
例えば9^5は、00001001^00000101 00001100(10進数12)と書くことができる
main(){
int a=9;
a=a^15;
printf("a=%d
",a);
}4.逆演算を求める
求逆演算子～は単目演算子であり、右結合性を有する.
その機能は,演算に関与する数の各バイナリビットをビット毎に反転させることである.
例えば～9の演算:~(000000000001001)結果:1111111111110110
5.左シフト演算
左シフト演算子「<<」は両目演算子です.左シフトnビットは2を乗じたn次方である.
その機能は「<<」の左の演算数の各バイナリを全部左に数ビットシフトし、「<<」の右の数で移動するビット数を指定し、高位を捨て、低位を0に補う.
1)例:a<<4はaの各バイナリを左に4ビット移動することを指す.a=0000000011(10進3)の場合、左に4桁移動すると0011000(10進48)になります.
2)例:
int i = 1;
i = i << 2;//iの値を左に2桁ずらす
つまり、1の2進法は000...0001(ここでは1の前の0の個数はintの桁数に関係し、32ビットマシン、gccには31個の0がある)、2ビット左にシフトしてから000になる...0100、つまり10進数の4なので、左シフト1ビットは2を乗じたものに相当し、左シフトnビットは2を乗じたn次方である(符号数が完全に適用されない場合があり、左シフトが符号の変化を招く可能性があるため、以下に原因を説明する)
なお、intタイプの左端の符号ビットとシフトがシフト場合である.intはシンボルのある整形数であり,最左端の1ビットはシンボルビット,すなわち0正1負であり,シフト時にオーバーフローが生じることが知られている.
例:
int i = 0x40000000;//16進の4000000、2進の01000000...0000
i = i << 1;
では、iは1ビット左に移動すると0 x 8000000、つまり2進の100000になります...0000は、符号ビットが1にする、他のビットはすべて0であり、intタイプで表すことができる最小値となり、32ビットのintという値は-2174483648であり、オーバーフローする.次にiを1位左に移動するとどうなりますか?C言語では最上位を捨てる処理法を採用し,1を捨てるとiの値が0になる.
左シフトのうち、左シフトのビット数がこの数値タイプの最大ビット数を超えると、コンパイラは左シフトのビット数で型の最大ビット数を除去し、残りの数でシフトします.
int i = 1, j = 0x80000000;//intを32ビットとする
i = i << 33;//33%32=1左シフト1位、iが2になる
j = j << 33;//33%32=1左シフト1位、jは0となり、最上位は破棄される
このプログラムをgccでコンパイルするとき、コンパイラは左シフトビット数>=タイプ長というwarningを与える.実際にi,jが移動するのは1ビット,すなわち33%32後の剰余である.gccではこのルールですが、他のコンパイラが同じかどうかはまだ分かりません.
つまり左シフトは、最高位を捨て、0が最低位を補う
6.右シフト演算
右シフト演算子">>は両目演算子です.右シフトnビットは2で割ったn次方
その機能は「>>」の左の演算数の各2進位をすべて右にいくつかシフトし、「>>」の右の数は移動する桁数を指定することです.
例えば、a=15とし、a>>2は、000001111を00000011(10進3)に右シフトすることを示す.
なお、符号数がある場合は、右シフト時に符号ビットが追従して移動する.正数の場合、最高位補0、負数の場合、シンボルビットは1であり、最高位が補0または補1はコンパイルシステムの規定に依存する.Turbo Cと多くのシステムは補1と規定されている.
右シフト対シンボルビットの処理と左シフトは異なります.
符号付き整数の場合、intタイプなど、右に移動すると、符号ビットは保持されます.たとえば、次のようになります.
int i = 0x80000000;
i = i >> 1;//iの値は0 x 4000000にはなりませんが、0 xc 00000000になります.
つまり、符号数がある場合、符号ビットが右に移動した後、正数であれば0、負数であれば1、
シンボル数の場合、右に移動すると、シンボルビットは同じように移動します.
正数の場合、最高位は0を補い、
負数の場合、符号ビットは1となり、
つまりアセンブリ言語における算術の右シフトである.同様に、移動するビット数がタイプの長さを超えると、残数が取り、残数ビットが移動する.
最上位レベルが0または1を補うかは、コンパイルシステムの規定に依存する.Turbo Cと多くのシステムは補1と規定されている.
負数10100110>>5(文字長が8ビットであると仮定)では11111101が得られる
つまり、Cでは、左シフトは論理/算術左シフト(両者は全く同じ)であり、右シフトは算術右シフトであり、符号ビットを一定に保つ.実際の応用では、場合によっては左/右シフトで高速な乗除演算を行うことができる、これはサイクル効率よりもはるかに高い.x>>1;//x/=2 x<<1に相当する.//x*=2 x>>2に相当する. //x/=4x<<2; //x *= 4x>>3; //x/= 8x<<3;//x*=8このように押す.
符号なし:
main(){
unsigned a,b;
printf("input a number: ");
scanf("%d",&a);
b=a>>5;
b=b&15;
printf("a=%d\tb=%d
",a,b);
}もう一例見てください!
main(){
char a='a',b='b';
int p,c,d;
p=a;
p=(p<<8)|b;
d=p&0xff;
c=(p&0xff00)>>8;
printf("a=%d
b=%d
c=%d
d=%d
",a,b,c,d);
}
二、異或いは操作の妙用
1.特定位置を反転させるには、どのビットを反転させるか∧演算を行う位置を1とすればよい.
2と0相∧は、元の値を保持する.
3.一時変数を使用することなく、2つの値を交換する.
他の変数を導入することなく変数値の交換を実現できる
以下の操作を実行できます.
a = a^b; //(1) b = a^b; //(2) a = a^b; //(3)
異種またはオペレーションは結合法則と交換法則を満たし、任意の整数a^a=0について異種またはオペレーションの性質によって知られている.
証:(第(2)ステップのa)a=a^b=(第(1)ステップのbをbに代入する)a^(a^b)=b;
(第(3)ステップのb)b=a^b=(第(1)ステップのbをbに代入し、(2)ステップのaをaに代入する)a^b^a^b=a^a^b=a^a^b=a^a^b^b=a;
三、ビットと演算
1 . クリアA数では1のビット、Bでは対応するビットが0です.そして両者を＆演算することで、Aクリアの目的を達成することができます.
2 . 1つの数の中の特定のビット数Aのいくつかのビットを取って、数Bのいくつかの位置1を取って、数Aのいくつかのビットと1をビットとすればいいです.
3 . 1ビットを保持するメソッド数Aと数Bは＆演算され、数Bは数Aが保持するビット1にあり、残りのビットはゼロである.
4 .パリティは変数aのパリティを判断する.aと1はビットと演算を行い、結果が1であればaは奇数である.aと1をビットと演算し,結果が0であればaは偶数である.
4、適用例1.int型変数aが奇数であるか偶数a&1=0偶数a&1=1奇数2であるかを判定する.int型変数aのk位をとる
(k=0,1,2,・・sizeof(int)),すなわちa>>k&1.int型変数aのk番目のビットを0、すなわちa=a&~(1<
php: $a ='dd'; $b = 'bb'; $a = $a ^ $b; $b = $a ^ $b; $a = $a ^ $b; echo $a,' ', $b; 10絶対値int abs(int x){int y;y=x>>31;return(x^y)-y;//or:(x+y)^y}の計算
11.型取り演算をビット演算に変換(オーバーフローが発生しない場合)a%(2^n)はa&(2^n-1)に等価
12乗算変換ビット演算(オーバーフローが発生しない場合)a*(2^n)はa<
..... a%32はa&5に等しい
15 if (x == a) x= b; else x= a; x=a^b^xに等しい.16 xの逆数を(~x+1)と表す