ビット操作
ビット操作
ビット操作は、一連のビットに論理演算を適用して必要な結果を得るプロセスです.小数形式と同様に、足し算、引き算、掛け算、割り算を行います.同様に、いくつかの演算を適用して数値のビットを操作できます.
バイナリ表記では、1 と 0 を使用して数値を表します.
例: 5 => 101
14 => 1110
ある位置のビットが 1 または 0 であるという言い方の 1 つは、ビットが 1 の場合はビットがセットまたはオンであり、0 の場合はビットがセットまたはオフではないと言います.
これらの演算子は、ビットごとの演算子として知られています.
ビット演算子には 6 種類あります.
このブログでは、これらのうち最初の 5 つを取り上げます.これらは、主に使用されるものです.
と ＆
ビットごとの AND &
& 演算を使用して、設定されたビット数を計算できます.
それを理解するには、まず観察を行う必要があります.
数を取りましょう.
例: 42 (110100) の場合、42 から 1 を引くと 41 になり、110011 になります.
これでわかることの 1 つは、42 の最初のセット ビット (右から) の後にあるすべてのビットが 1 になり、それ自体が 0 になったことです.
同様に、すべての数値で 1 だけデクリメントすると、最初にセットされたビット (左から) の後のすべてのビットが 1 になり、それ自体が 0 になります.
例: 10 => 1010 9 => 1001
14 => 1110 13 => 1101
log(n) 時間でビット数を計算するには:
上記のコードでは、n がループ内に入るたびに、セットされたビットが 1 つ失われ、カウントが 1 ずつ増えます.これが、n のセットされたビットの総数になります.
ビットワイズまたは ( | )
ビット単位の OR は、ビット単位の AND と同様に、2 つの等しい長さのビット パターンを操作する二項演算子でもあります.ビット パターンの比較された位置の両方のビットが 0 の場合、結果のビット パターンのビットは 0 になり、それ以外の場合は 1 になります.
XOR ( ^ )
ビット単位の XOR も、2 つの等しい長さのビット パターンを使用します.ビット パターンの比較位置の両方のビットが 0 または 1 の場合、結果のビット パターンのビットは 0 になり、それ以外の場合は 1 になります.
xor のいくつかのプロパティ:
A^A=0
A ^ 0 = A
A ^ ( B ^ C) = ( A ^ B ) ^ C
A^B=B^A
重要なことの 1 つは、多数の数値の xor を使用する場合です.その位置に 1 がある数のカウントが奇数の場合、結果のある位置に 1 があり、それ以外の場合は 0 になると言えます.
上記の観察を使用します.最初の n 個の自然数の xor を計算すると、n%4 で得られる剰余に依存すると言えます.
0 の場合.
次に、答え = n.
1の場合.
答え = 1 です.
2の場合.
答え = n + 1.
3なら.
答え = 0 です.
左シフト (<<)
x 単位 ( 5<
数学的には、数値に x 単位で左シフトを適用すると、2^x が乗算されます.
例: 3<<1 = 2X3 = 6 ( 110 ) [ 3( 11 )]
3<<2 = 4X3 = 12 (1100)
9<<3 = 8X9 = 72 (1001000) [9( 1001 )]
右シフト (>>)
これは左シフトの正反対で、x 単位の数値に適用すると、ビットが x 単位だけ右にシフトされます.
数学的には、x 単位で数値に右シフトを適用すると、2^x で除算されます.
例: 3>>1 = 3/2 = 1
3>>2 = ¾ = 0
これらのビット単位の操作を使用するいくつかの良い方法:
まず第一に、これらを使用して実際の問題を解決できますが、明らかにそれはビットマスクをどのように適用できるかによって異なります.
コードで毎日使用できる短いトリックは次のとおりです.
2 の累乗を計算するには、1<& と << を一緒に使用して、ある位置のビットがオンかオフかを確認できます.
このブログをより良くするために、提案を歓迎します.
ビット操作は、一連のビットに論理演算を適用して必要な結果を得るプロセスです.小数形式と同様に、足し算、引き算、掛け算、割り算を行います.同様に、いくつかの演算を適用して数値のビットを操作できます.
バイナリ表記では、1 と 0 を使用して数値を表します.
例: 5 => 101
14 => 1110
ある位置のビットが 1 または 0 であるという言い方の 1 つは、ビットが 1 の場合はビットがセットまたはオンであり、0 の場合はビットがセットまたはオフではないと言います.
これらの演算子は、ビットごとの演算子として知られています.
ビット演算子には 6 種類あります.
& ( AND )
| ( OR )
^ ( XOR )
<< ( LEFT SHIFT )
>> ( RIGHT SHIFT )
~ ( NOT )
このブログでは、これらのうち最初の 5 つを取り上げます.これらは、主に使用されるものです.
と ＆
ビットごとの AND &
bit a | bit b | a & b (a AND b)
0 0 0
0 1 0
1 0 0
1 1 1
& 演算を使用して、設定されたビット数を計算できます.
それを理解するには、まず観察を行う必要があります.
数を取りましょう.
例: 42 (110100) の場合、42 から 1 を引くと 41 になり、110011 になります.
これでわかることの 1 つは、42 の最初のセット ビット (右から) の後にあるすべてのビットが 1 になり、それ自体が 0 になったことです.
同様に、すべての数値で 1 だけデクリメントすると、最初にセットされたビット (左から) の後のすべてのビットが 1 になり、それ自体が 0 になります.
例: 10 => 1010 9 => 1001
14 => 1110 13 => 1101
log(n) 時間でビット数を計算するには:
int count = 0;
while(n>0){
count++;
n = n&(n-1);
}
上記のコードでは、n がループ内に入るたびに、セットされたビットが 1 つ失われ、カウントが 1 ずつ増えます.これが、n のセットされたビットの総数になります.
ビットワイズまたは ( | )
bit a | bit b | a | b (a OR b)
0 0 0
0 1 1
1 0 1
1 1 1
ビット単位の OR は、ビット単位の AND と同様に、2 つの等しい長さのビット パターンを操作する二項演算子でもあります.ビット パターンの比較された位置の両方のビットが 0 の場合、結果のビット パターンのビットは 0 になり、それ以外の場合は 1 になります.
XOR ( ^ )
ビット単位の XOR も、2 つの等しい長さのビット パターンを使用します.ビット パターンの比較位置の両方のビットが 0 または 1 の場合、結果のビット パターンのビットは 0 になり、それ以外の場合は 1 になります.
xor のいくつかのプロパティ:
A^A=0
A ^ 0 = A
A ^ ( B ^ C) = ( A ^ B ) ^ C
A^B=B^A
重要なことの 1 つは、多数の数値の xor を使用する場合です.その位置に 1 がある数のカウントが奇数の場合、結果のある位置に 1 があり、それ以外の場合は 0 になると言えます.
上記の観察を使用します.最初の n 個の自然数の xor を計算すると、n%4 で得られる剰余に依存すると言えます.
0 の場合.
次に、答え = n.
1の場合.
答え = 1 です.
2の場合.
答え = n + 1.
3なら.
答え = 0 です.
左シフト (<<)
x 単位 ( 5<
数学的には、数値に x 単位で左シフトを適用すると、2^x が乗算されます.
例: 3<<1 = 2X3 = 6 ( 110 ) [ 3( 11 )]
3<<2 = 4X3 = 12 (1100)
9<<3 = 8X9 = 72 (1001000) [9( 1001 )]
右シフト (>>)
これは左シフトの正反対で、x 単位の数値に適用すると、ビットが x 単位だけ右にシフトされます.
数学的には、x 単位で数値に右シフトを適用すると、2^x で除算されます.
例: 3>>1 = 3/2 = 1
3>>2 = ¾ = 0
これらのビット単位の操作を使用するいくつかの良い方法:
まず第一に、これらを使用して実際の問題を解決できますが、明らかにそれはビットマスクをどのように適用できるかによって異なります.
コードで毎日使用できる短いトリックは次のとおりです.
2 の累乗を計算するには、1<
bool on(int n, int position){
int PowerOf2 = 1<<position;
return ((n&PowerOf2)==0)? false : true;
}
このブログをより良くするために、提案を歓迎します.
Reference
この問題について(ビット操作), 我々は、より多くの情報をここで見つけました https://dev.to/shivam164/bit-manipulation-kdlテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol