私は暇を見つけてはC言語を学ぼうとしているのですが、他の言語(C#、Javaなど)にも同じ概念(同じ演算子を使うことも多い)が ...
私が疑問に思っているのは、核心的なレベルでは、ビットシフト(<<
, >>
, >>
)は何をするのか、どんな問題を解決するのか、どんな問題が潜んでいるのか、ということです。つまり、初心者のためのビットシフト入門書です。
ビットシフト演算子は、その名の通り、ビットをシフトする演算子です。 ビットをシフトします。 ここでは、さまざまなシフト演算子を簡単に(あるいはそれほどでもない程度に)紹介します。
>>
は、算術的(または符号付き)右シフト演算子です。>>
は、論理的(または符号なし)右シフト演算子です。<<
は左シフト演算子で、論理シフトと算術シフトの両方のニーズに対応しています。これらの演算子はすべて、整数値(int
、long
、場合によってはshort
、byte
またはchar
)に適用できます。 いくつかの言語では、int
より小さいデータ型にシフト演算子を適用すると、オペランドが自動的にint
になります。
なお、<<<
は冗長になるので演算子ではありません。
また、CとC++は右シフト演算子を区別していないことにも注意してください。 これらは>>
演算子のみを提供しており、右シフトの動作は符号付きの型に対して実装で定義されています。 回答の残りの部分はC# / Javaの演算子を使用しています。
(gccやclang/LLVMを含むすべての主流のCおよびC++の実装では、符号付きの型に対する>>
は算術です。 一部のコードはこれを前提としていますが、標準では保証されていません。 しかし、これはundefinedではなく、規格では実装がいずれかの方法で定義することを要求しています。 ただし、負の符号付き数値の左シフトは、未定義の動作です(符号付き整数のオーバーフロー)。 そのため、算術的な右シフトが必要でない限り、通常は符号なしの型でビットシフトを行うのが良いでしょう)。
整数は、メモリ上では一連のビットとして格納されます。 例えば、32ビットのint
として格納された数字6は、次のようになります。
00000000 00000000 00000000 00000110
このビットパターンを1つ左にシフトすると(6 << 1
)、12という数字になります。
00000000 00000000 00000000 00001100
ご覧のように、桁が1つ左に移動し、右の最後の桁は0で埋められています。 また、左にシフトすることは、2の累乗に相当することにも注意してください。 つまり、6 << 1
は6 * 2
に、6 << 3
は6 * 8
に相当します。 優れた最適化コンパイラは、可能な限り乗算をシフトに置き換えます。
これらは循環シフトではないことに注意してください。 この値を1つ左にシフトします(3,758,096,384 << 1
)。
11100000 00000000 00000000 00000000
の結果は3,221,225,472となります。
11000000 00000000 00000000 00000000
端から」ずれてしまった桁は失われます。 折り返しはありません。
論理的右シフトとは、左シフトの逆の意味です。 ビットを左に移動させるのではなく、単純に右に移動させます。 例えば、数字の「12」をシフトする場合。
00000000 00000000 00000000 00001100
を1つ右にシフトすると(12 >>> 1
)、元の6に戻ります。
00000000 00000000 00000000 00000110
このように、右にずらすことは、2の累乗で割ることと同じであることがわかります。
しかし、シフトしても「失われた」ビットを取り戻すことはできません。 例えば、このパターンをシフトすると
00111000 00000000 00000000 00000110
を4つ左にシフトすると(939,524,102 << 4
)、2,147,483,744となります。
10000000 00000000 00000000 01100000
となり、さらに後ろにずらすと((939,524,102 << 4) >>> 4
)134,217,734となります。
00001000 00000000 00000000 00000110
一度ビットを失ってしまうと、元の値に戻すことはできません。
算術右シフトは、論理右シフトとまったく同じですが、ゼロでパディングする代わりに最上位ビットでパディングします。 これは、最上位ビットがsignビット、つまり、正の数と負の数を区別するビットだからです。 最上位のビットでパディングすることで、算術右シフトは符号を保持します。
たとえば、このビットパターンを負の数と解釈すると、次のようになります。
10000000 00000000 00000000 01100000
と解釈すると、-2,147,483,552という数字になります。 これを算術シフトで4つ右にシフトすると(-2,147,483,552 >> 4)、次のようになります。
11111000 00000000 00000000 00000110
つまり、-134,217,722という数字になります。
このように、論理的右シフトではなく、算術的右シフトを使用することで、負の数の符号を維持していることがわかります。 また、ここでも2の累乗での除算を行っていることがわかります。
例えば、1バイトとします。
0110110
左のビットシフトを1回適用すると
1101100
左端の0がバイトからシフトアウトされ、新たに0がバイトの右端に追加されています。
ビットはロールオーバーされず、破棄されます。つまり、1101100 を左シフトした後に右シフトしても、同じ結果は得られません。
左にNだけシフトすることは、2Nを掛けることと同じです。
右にNだけシフトすることは(1の補数を使用している場合)、2Nで除算して0に丸めることと同じです。
ほとんどすべての低レベルのグラフィックス ルーチンはビットシフトを使用しています。
例えば、昔のゲームでは、モード13h(320x200 256色)が使われていました。モード13hでは、ビデオメモリが画素ごとに順次配置されていた。つまり、ピクセルの位置を計算するには、次のような計算をすることになる。
memoryOffset = (row * 320) + column
さて、当時はスピードが重視されていたので、この演算にはビットシフトを使用していました。
しかし、320は2の累乗ではないので、これを回避するためには、足して320になる2の累乗は何かを調べなければなりません。
(row * 320) = (row * 256) + (row * 64)
さて、これを左シフトに変換します。
(row * 320) = (row << 8) + (row << 6)
という最終結果になります。
memoryOffset = ((row << 8) + (row << 6)) + column
これで先ほどと同じオフセットが得られましたが、高価な乗算演算の代わりに2つのビットシフトを使用しています。x86では次のようになります(注:アセンブリを行うのはずっと前のことです(編集者注:いくつかの間違いを修正し、32ビットの例を追加しました))。
mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]
; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov
合計:28サイクル、このタイミングの古いCPUであれば
Vrs
mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6; 2
shl di, 8; 2
add di, ax; 2 (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]
同じ古いCPUで12サイクル。
そう、16のCPUサイクルを削るために、ここまで頑張るのです。
32または64ビットモードでは、どちらのバージョンももっと短く、速くなります。 Intel Skylake(http://agner.org/optimize/ 参照)のような最新のアウトオブオーダー実行CPUは、ハードウェア乗算が非常に高速(低レイテンシー、高スループット)なので、得られるものはずっと小さくなります。 AMD Bulldozer-familyは、特に64ビットの乗算では少し遅くなります。 インテルのCPUやAMD Ryzenでは、2つのシフトはレイテンシーがやや低いが、乗算よりも命令数が多い(スループットが低下する可能性がある)。
imul edi, [row], 320 ; 3 cycle latency from [row] being ready
add edi, [column] ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column], in 4 cycles from [row] being ready.
vs.
mov edi, [row]
shl edi, 6 ; row*64. 1 cycle latency
lea edi, [edi + edi*4] ; row*(64 + 64*4). 1 cycle latency
add edi, [column] ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column], in 3 cycles from [row] being ready.
コンパイラがこれを行ってくれます。gcc、clang、MSVCは、return 320*row + col;`を最適化する際にshift+leaを使用しています]2をご覧ください。
ここで最も興味深いのは、x86にはシフト・アンド・アド命令(LEA
)があり、小さな左シフトと加算を同時に行うことができ、add
命令と同等の性能を発揮します。 ARMはさらに強力で、どの命令のオペランドも無料で左シフトまたは右シフトできます。 そのため、2の累乗であることがわかっているコンパイル時の定数でスケーリングすると、乗算よりもさらに効率的になります。
さて、話を現代に戻すと...もっと便利なのは、ビットシフトを使って2つの8ビットの値を16ビットの整数に格納することです。例えば、C#では
// Byte1: 11110000
// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;
C++では、2つの8ビットメンバを持つ構造体
を使用した場合、コンパイラがこれを行うはずですが、実際には必ずしもそうではありません。