1478

私は暇なときに C を学ぼうとしていますが、他の言語 (C#、Java など) も同じ概念 (および多くの場合、同じ演算子) を持っています...

私が疑問に思っているのは、コア レベルでは、ビット シフト ( <<、>>、>>>) が何をするのか、それがどのような問題を解決するのに役立つのか、曲がり角に潜んでいる問題は何かということです。言い換えれば、ビット シフトのすべての良さを理解するための完全な初心者向けガイドです。

4

11 に答える 11

1814

ビットシフト演算子は、その名前が示すとおり正確に実行します。それらはビットをシフトします。以下は、さまざまなシフト演算子の簡単な (またはそれほど簡単ではない) 紹介です。

オペレーター

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

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

<<<は冗長になるため、演算子ではないことに注意してください。

また、 C と C++ は右シフト演算子を区別しないことに注意してください。それらは>>演算子のみを提供し、右シフト動作は符号付き型に対して定義された実装です。残りの回答では、C# / Java 演算子を使用します。

(GCC および Clang/LLVM を含むすべての主流の C および C++ 実装で>>は、符号付き型は算術演算です。一部のコードはこれを前提としていますが、標準で保証されているものではありません。ただし、 undefinedではありません。標準では、実装で定義する必要があります。ただし、負の符号付き数値の左シフトは未定義の動作です (符号付き整数のオーバーフロー)。したがって、算術右シフトが必要でない限り、符号なしの型でビット シフトを行うことをお勧めします。)

左シフト (<<)

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

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

ビットを失うと、元の値を取り戻すことはできません。

算術右シフト (>>)

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

たとえば、このビット パターンを負の数として解釈すると、次のようになります。

10000000 00000000 00000000 01100000

数値は -2,147,483,552 です。これを算術シフト (-2,147,483,552 >> 4) で右に 4 桁シフトすると、次のようになります。

11111000 00000000 00000000 00000110

または数値 -134,217,722。

したがって、論理右シフトではなく算術右シフトを使用して、負の数の符号を保持していることがわかります。繰り返しになりますが、2 のべき乗による除算を実行していることがわかります。

于 2008-09-26T20:46:39.813 に答える
220

1バイトがあるとしましょう：

0110110

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

1101100

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

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

N だけ左にシフトすることは、2 Nを掛けることと同じです。

N is ( 1 の補数を使用している場合) だけ右にシフトすることは、2 Nで割ってゼロに丸めることと同じです。

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

たとえば、昔はゲームにモード 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

合計: これらのタイミングを持つ古代の 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 サイクル。

はい、CPU サイクルを 16 削減するために、これだけの努力をします。

32 ビット モードまたは 64 ビット モードでは、どちらのバージョンも大幅に短く、高速になります。Intel Skylake ( http://agner.org/optimize/を参照) のような最新のアウトオブオーダー実行 CPUは、非常に高速なハードウェア乗算 (低レイテンシーと高スループット) を備えているため、ゲインははるかに小さくなります。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.

対。

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、および Microsoft Visual C++ が最適化時にどのように shift+lea を使用するreturn 320*row + col;かを確認してください。

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

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

// Byte1: 11110000
// Byte2: 00001111

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

// value = 000011111110000;

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

于 2008-09-26T19:55:11.853 に答える
109

ビットシフトを含むビット単位の演算は、低レベルのハードウェアまたは組み込みプログラミングの基本です。デバイスの仕様や一部のバイナリファイル形式を読むと、バイト、ワード、および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演算子（＆）を使用します。

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

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

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

 i <<= x;  // i *= 2^x;
 i >>= y;  // i /= 2^y;
于 2008-09-26T22:22:03.653 に答える
28

1 つの落とし穴は、以下が実装に依存することです (ANSI 標準によると)。

char x = -1;
x >> 1;

x は 127 (01111111) または -1 (11111111) にすることができます。

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

于 2008-09-26T20:07:48.203 に答える
25

私はヒントとコツだけを書いています。テストや試験で役立つかもしれません。

  1. n = n*2:n = n<<1
  2. n = n/2:n = n>>1
  3. n が 2 のべき乗 (1,2,4,8,...) であるかどうかの確認: check!(n & (n-1))
  4. のx番目のビットを取得していますn:n |= (1 << x)
  5. x が偶数か奇数かのチェック: x&1 == 0(偶数)
  6. xのn番目のビットを切り替えます。x ^ (1<<n)
于 2016-10-11T22:43:54.087 に答える
8

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

例えば：

(long) 4 >> 65

ビットを右に 65 回シフトするとすべてがゼロになると思うかもしれませんが、実際には次のようになります。

(long) 4 >> (65 % 64)

これは、<<、>>、および >>> に当てはまります。他の言語では試していません。

于 2015-08-28T13:16:33.497 に答える
-3

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

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

もちろん、64 ビット バージョンの PHP (Unix) を使用している場合は、63 ビットを超えてシフトすることは避ける必要があります。ただし、たとえば、MySQL は 64 ビットの BIGINT を使用するため、互換性の問題は発生しません。

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

于 2015-10-23T14:28:36.217 に答える