ビットシフト（ビットシフト）演算子とは何ですか？

https://stackoverflow.com/questions/141525

02-07-2019
|

質問

暇なときにCを学習しようとしましたが、他の言語（C＃、Javaなど）も同じ概念（そして多くの場合同じ演算子）を持っています...

私が不思議に思っているのは、コアレベルで、ビットシフト（<<、>>、>>>）が何をするのか、どのような問題を解決できるのか、曲がり角に何が潜んでいるのか、ということです。言い換えれば、ビットシフトのすべての長所についての絶対的な初心者向けガイドです。

解決

ビットシフト演算子は、その名前が示すとおりに機能します。ビットをシフトします。さまざまなシフト演算子の簡単な（またはそれほど簡単ではない）紹介を次に示します。

演算子

>>は算術（または符号付き）右シフト演算子です。
>>>は、論理（または符号なし）右シフト演算子です。
<<は左シフト演算子であり、論理シフトと算術シフトの両方のニーズを満たします。

これらの演算子はすべて整数値（int、long、場合によってはshortおよびbyteまたはchar）に適用できます。一部の言語では、シフト演算子を<<<より小さいデータ型に適用すると、オペランドのサイズが自動的に6 << 1に変更されます。

6 * 2は冗長ではないため、演算子ではないことに注意してください。また、CとC ++は右シフト演算子を区別しないことに注意してください。これらは6 << 3演算子のみを提供し、右シフト動作は符号付き型に対して定義された実装です。

左シフト（<！> lt; <！> lt;）

整数は、一連のビットとしてメモリに保存されます。たとえば、32ビットの6 * 8として保存される数値6は次のようになります。

00000000 00000000 00000000 00000110

このビットパターンを1つ左の位置（3,758,096,384 << 1）にシフトすると、数値12になります：

00000000 00000000 00000000 00001100

ご覧のとおり、数字は左に1桁シフトしており、右の最後の数字はゼロで埋められています。また、左にシフトすることは2の累乗で乗算することと同等であることに注意してください。したがって、12 >>> 1は939,524,102 << 4と同等であり、(939,524,102 << 4) >>> 4は<=>と同等です。適切な最適化コンパイラは、可能な場合、乗算をシフトに置き換えます。

非円形シフト

これらは循環シフトではないことに注意してください。この値を1つ左にシフト（<=>）：

11100000 00000000 00000000 00000000

結果は3,221,225,472になります：

11000000 00000000 00000000 00000000

シフトされる数字<！> quot; off the end <！> quot;失われます。ラップアラウンドしません。

論理的右シフト（<！> gt; <！> gt; <！> gt;）

論理的な右シフトは、左シフトの逆です。ビットを左に移動するのではなく、単に右に移動します。たとえば、数値12をシフトします：

00111000 00000000 00000000 00000110

右に1ポジション（<=>）すると、元の6が返されます：

10000000 00000000 00000000 01100000

したがって、右へのシフトは2の累乗による除算と同等であることがわかります。

失われたビットはなくなりました

ただし、シフトは<！> quot; lost <！> quot;を回収できません。ビット。たとえば、このパターンをシフトした場合：

00001000 00000000 00000000 00000110

左4桁（<=>）に2,147,483,744が得られます：

11111000 00000000 00000000 00000110

そして次にシフト（<=>）すると、134,217,734が得られます：

<*>

ビットが失われると、元の値に戻すことはできません。

算術右シフト（<！> gt; <！> gt;）

算術右シフトは論理右シフトとまったく同じです。ただし、ゼロでパディングする代わりに、最上位ビットでパディングします。これは、最上位ビットが sign ビット、つまり正数と負数を区別するビットだからです。最上位ビットでパディングすることにより、算術右シフトは符号を保持します。

たとえば、このビットパターンを負の数として解釈する場合：

<*>

番号は-2,147,483,552です。これを算術シフト（-2,147,483,552 <！> gt; <！> gt; 4）で右4桁にシフトすると、次のようになります。

<*>

または番号-134,217,722。

つまり、論理的な右シフトではなく、算術右シフトを使用して、負の数の符号を保持していることがわかります。もう一度、2の累乗による除算を実行していることがわかります。

他のヒント

単一のバイトがあるとしましょう：

単一の左ビットシフトを適用すると、次のようになります：

左端のゼロがバイトからシフトアウトされ、バイトの右端に新しいゼロが追加されました。

ビットはロールオーバーしません。それらは破棄されます。つまり、1101100を左にシフトしてから右にシフトすると、同じ結果は得られません。

Nを左にシフトすることは、2 ^Nを乗算することと同等です。

Nだけ右にシフトする（ 1の補数を使用している場合） 2 ^Nで除算してゼロに丸めることと同等です。

ビットシフトは、2のべき乗で作業している場合、非常に高速な乗算および除算に使用できます。ほとんどすべての低レベルグラフィックルーチンはビットシフトを使用します。

たとえば、昔、ゲームにはモード13h（320x200 256色）を使用していました。モード13hでは、ビデオメモリはピクセルごとに順番にレイアウトされました。これはピクセルの位置を計算することを意味し、次の数学を使用します：

memoryOffset = (row * 320) + column

今、その日と年齢に戻ると、速度が重要であったため、ビットシフトを使用してこの操作を行いました。

ただし、320は2の累乗ではないため、これを回避するには、加算された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

合計：これらのタイミングがあった古代のCPUで28サイクル。

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のような最新のアウトオブオーダー実行CPU（ http://agner.org/optimize/ を参照）非常に高速なハードウェア乗算（低レイテンシーおよび高スループット）があるため、ゲインははるかに小さくなります。 AMD Bulldozerファミリは、特に64ビット乗算の場合、少し遅くなります。 Intel 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を使用します。

ここで注意すべき最も興味深いことは、 x86としてhift-and-add命令（LEA）。これは、パフォーマンスのasおよびadd命令を使用して、小さな左シフトと加算を同時に実行できます。 ARMはさらに強力です。任意の命令の1つのオペランドを自由に左または右にシフトできます。したがって、2のべき乗であることが知られているコンパイル時定数によるスケーリングは、乗算よりもさらに効率的になります。

OK、現代に戻って...今より便利なのは、ビットシフトを使用して2つの8ビット値を16ビット整数に格納することです。たとえば、C＃の場合：

// Byte1: 11110000
// Byte2: 00001111

Int16 value = ((byte)(Byte1 >> 8) | Byte2));

// value = 000011111110000;

C ++では、2つの8ビットメンバーでstructを使用した場合、コンパイラがこれを行う必要がありますが、実際には常にそうとは限りません。

ビットシフトを含むビット単位の操作は、低レベルのハードウェアまたは組み込みプログラミングの基本です。デバイスの仕様またはいくつかのバイナリファイル形式を読むと、バイト、ワード、およびdwordが、バイト単位で整列されていないビットフィールドに分割され、さまざまな値が含まれています。読み取り/書き込みのためにこれらのビットフィールドにアクセスするのが最も一般的な使用法です。

グラフィックプログラミングの簡単な実際の例は、16ビットピクセルが次のように表されることです。

  bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1  | 0 |
      |       Blue        |         Green         |       Red          |

緑色の値を取得するには、次のようにします。

 #define GREEN_MASK  0x7E0
 #define GREEN_OFFSET  5

 // Read green
 uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

説明

オフセット5で始まり10（つまり6ビット長）で終わる緑の値のみを取得するには、16ビットピクセル全体に適用される（ビット）マスクを使用する必要があります。、興味のあるビットのみを生成します。

#define GREEN_MASK  0x7E0

適切なマスクは0x7E0で、バイナリでは0000011111100000（10進数では2016）です。

uint16_t green = (pixel & GREEN_MASK) ...;

マスクを適用するには、AND演算子（<！> amp;）を使用します。

uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

マスクを適用すると、MSBが11番目のビットにあるため、実際には11ビットの数字である16ビットの数字になります。緑は実際には6ビット長なので、右シフト（11-6 = 5）を使用して縮小する必要があるため、オフセットとして5を使用します（#define GREEN_OFFSET 5）。

また、2の累乗による高速乗算および除算にビットシフトを使用することも一般的です。

 i <<= x;  // i *= 2^x;
 i >>= y;  // i /= 2^y;

ビットマスキング<！> amp;シフト

ビットシフトは、低レベルのグラフィックプログラミングでよく使用されます。たとえば、32ビットワードでエンコードされた特定のピクセルカラー値。

 Pixel-Color Value in Hex:    B9B9B900
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

理解を深めるために、どのセクションがラベル付けされた同じバイナリ値がどの色部分を表すか

                                 Red     Green     Blue       Alpha
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

たとえば、このピクセル色の緑の値を取得したいとしましょう。この値は、マスキングとシフトによって簡単に取得できます。

マスク：

                  Red      Green      Blue      Alpha
 color :        10111001  10111001  10111001  00000000
 green_mask  :  00000000  11111111  00000000  00000000

 masked_color = color & green_mask

 masked_color:  00000000  10111001  00000000  00000000

論理&演算子は、マスクが1の値のみが保持されるようにします。最後に行う必要があるのは、これらのビットをすべて16桁右にシフトして正しい整数値を取得することです（論理的右シフト）。

 green_value = masked_color >>> 16

Et voil <！>＃225 ;、ピクセルの色の緑の量を表す整数があります：

 Pixels-Green Value in Hex:     000000B9
 Pixels-Green Value in Binary:  00000000 00000000 00000000 10111001 
 Pixels-Green Value in Decimal: 185

これは、jpg、png、...などの画像形式のエンコードまたはデコードによく使用されます。

1つの落とし穴は、次のものが実装に依存することです（ANSI標準に準拠）：

char x = -1;
x >> 1;

xは、127（01111111）または-1（11111111）になります。

実際には、通常後者です。

ヒントやコツだけを書いていますが、テストや試験で役立つ場合があります。

n = n*2：n = n<<1
n = n/2：n = n>>1
nが2の累乗（1,2,4,8、...）であるかどうかを確認：!(n & (n-1))
nの x ^thビットの取得：n |= (1 << x)
xが偶数か奇数かを確認する：x&1 == 0（even）
xの n ^thビットを切り替える：x ^ (1<<n)

Java実装では、シフトするビット数はソースのサイズによってmod'dされることに注意してください。

例：

(long) 4 >> 65

equals 2.ビットを右に65回シフトすると、すべてがゼロになると予想されるかもしれませんが、実際には次と同等です：

(long) 4 >> (65 % 64)

これは、<！> lt; <！> lt;、<！> gt; <！> gt ;、および<！> gt; <！> gt; <！> gt;に当てはまります。他の言語で試したことはありません。

Pythonでの便利なビット操作/操作。 Pythonで@Ravi Prakashの回答を実装しました。

# basic bit operations
# int to bin
print(bin(10))

# bin to int
print(int('1010',2))

# multiplying x with 2 .... x**2== x << 1
print(200<<1)

# dividing x with 2 .... x /2 == x >> 1
print(200>>1)

# modulo x with 2 .... x%2 == x&1
if 20&1==0:
    print("20 is a even number")

# check if n is power of 2 : check !(n & (n-1))
print(not(33 &(33-1)))

# getting xth bit of n : (n>>x)&1
print((10>>2)&1) # bin of 10==1010 and 2nd bit is 0

# toggle nth bit of x : x^(1<<n)
# take bin(10)==1010 and toggling 2nd bit in bin(10) we get 1110 === bin(14)
print(10^(1<<2))

Windowsプラットフォームでは32ビットバージョンのPHPしか使用できないことに注意してください。

次に、たとえば<！> lt; <！> lt;をシフトします。または<！> gt; <！> gt; 31ビット以上、結果は予期できません。通常、ゼロではなく元の数値が返されますが、これは非常に厄介なバグになる可能性があります。

もちろん、64ビットバージョンのPHP（unix）を使用する場合は、63ビット以上のシフトは避けてください。ただし、たとえば、MySQLは64ビットBIGINTを使用するため、互換性の問題はありません。

更新：PHP7 Windowsから、PHPビルドは最終的に完全な64ビット整数を使用できるようになりました。整数のサイズはプラットフォームに依存しますが、約20億の最大値が通常の値です（32ビットの符号付き）。通常、64ビットプラットフォームの最大値は約9E18です。ただし、PHP 7より前のWindowsでは常に32ビットでした。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow