6

ビットごとのシフト (ビットシフト) 演算子とは何ですか? どのように機能しますか? 、しかし、ビットシフトの概念はまだ理解するのが難しいと思います。

誰かが C でビット シフトするためのより基本的なガイドの方向に私を向けることができますか? 主題全体をカバーする必要があるため、非常に長いものになると思います。

私はC プログラミング言語(別名 K&R) を学んでおり、それが目的なので、演習を行うことができます。基本はわかったのですが、いまだに正しいビットシフト演算ができません。

これが私を困惑させたK＆Rの演習です

練習問題 2-6: 位置 p から始まる n ビットを y の右端の n ビットに設定し、他のビットは変更せずに x を返す関数 setbits(x, p, n, y) を書きなさい。

演習 2-7: 位置 p から始まる n ビットを反転して (つまり、1 を 0 に、またはその逆に) x を返し、他は変更しない関数 invert(x, p, n) を書きなさい。

演習 2-8: n ビット位置だけ右に回転した整数 x の値を返す関数 rightrot(x, n) を書きます

演習 2-9: 2 の補数系では、x &= (x-1) は x の右端の 1 ビットを削除します。理由を説明し、この観察結果を使用して、ビットカウントのより高速なバージョンを記述します。

これらは、k&R (C プログラミング言語) の本からの演習です。これは最高の C の本ですが、ビット シフトを理解するのに苦労しているので、これらの演習に問題があります。

4

8 に答える 8

7

ビットシフトとは、文字どおりの意味に他なりません。特定のシーケンス内のすべてのビットを左または右にシフトすることです。

覚えておかなければならないのは、すべての 10 進数 (6、7、3、2 など) が、コンピューターのメモリ内の一連のビットとして表されるということだけです。したがって、C コードの一部で次のようなものを見つけた場合:

(7 >> 1)

これは、基礎となる 7 の 2 進数表現のビットが 1 桁右にシフトされることを意味します。

あなたが引用したリンクの説明はかなり明確だと思います。おそらく、一連のビットを自分で紙に書き留めて、引用されたリンクのように操作すると役立つでしょう。

あるいは、コンピューターが内部で数値を処理する方法をまだ理解していない可能性もあります。その場合、ビットシフトを学習する前に、それについて読む必要があります。

于 2009-01-14T15:09:54.367 に答える
3

これらの質問に答えるには、シフトするよりも多くのツールがツールキットに必要になります。

数値が2進数でどのように表されるかについて、非常に基本的なことから始める必要があると思います。次に、その数の特定のビット、またはビットのグループを同時に設定およびクリアする方法について検討する必要があります。特定のビットグループが設定されているかどうかを確認するためのテスト方法と、マスキングについて知る必要があります。上記のすべてをビット演算子、またはxor、反転などの演算子で実行できる必要があります。

次に、シフトについて知りたいと思うでしょう。つまり、ビットを特定の数のスペースだけ左右に移動します。「空」のままになっているビットがどうなるかを知りたいと思うでしょう。1または0で埋められていますか？いつ1または0で埋められますか？

グーグルの「ビット演算チュートリアル」は、そもそもいくつかの有望な結果を思いついたようです。しかし、ここにあなたが理解していることを確認するためにあなた自身をテストするためのいくつかの基本があります

// 1234 in hexadecimal. Do you understand this is not 1234 in decimal? Do you understand
// how specifying in hex makes it easier to think about the binary representation?
unsigned short i = 0x1234;
// Flip all the bits in 0x1234
printf("%04x", ~i);

// Test - Is the most significant bit set?
// mask is a binary number with the most significant bit set. Do
// you understand why this is so?
unsigned short mask = 0x8000;
if ((mask & i) == mask)
{
    printf("bit set!");
}
else
{
    printf("bit cleared!");
}

// Set the most significant bit
i = i | mask;
printf("Set the MSB of i, check it out: %i\n", i)

// Set the second most significant bit
// Do you see how by shifting mask right one it becomes the next most significant bit?
i = i | (mask >> 1);

幸運を！

于 2009-01-14T15:58:54.657 に答える
1

紙にビットを書き、一方の端からそれらを消去し、もう一方の端にさらに追加することを考えてください. 小学生と変わらず、10を掛けるときに小数点をずらします。

すべての C 関数はゼロをシフトインします。

そう

x = y << 3;

は、3 ビット左にシフトし、右側の新しいビットはすべてゼロであることを意味します。左側にあった 3 つのビットは、「ビット バケット」に入ります。

x = z >> 2

右側の 2 ビットを失い、左側に 2 つのゼロを追加します。

欠落している機能と、K&R 演習の目的を見つけることができます。世の中に出回っているプロセッサの種類の中には、C やその他の高水準言語よりもはるかに多くのシフト機能があります。

一方の端からシフトされたビットが他方の端にシフトされる回転機能があります。

したがって、この方法で 1 ビット右に回転した数値 0xD は 0xE になります。これは、最下位ビットが 1 であったため、1101 を右にシフトすると、右の 1 が左の 1110 の 1 になります。

場合によっては、ALUのキャリー ビットを回転させます。キャリー ビットに 0 があり、0xD を 1 ビット 0 1101 に回転すると、1 0110 が 0x6 になるとします。0 1011 をもう 1 回回転すると、0xB などが得られます。

なぜあなたが尋ねるキャリービットを回転させるのでしょうか? より大きな数の場合、4 ビット レジスタがあり、8 ビット シフトを実行したいとします。たとえば、各文字が bcde fghi のビットでaあり、 がキャリー ビットで、他の 2 つの 4 つのグループが 4 ビット レジスタであるとします。キャリー e abcd fghi を介して左レジスタをローテーションすることから始め、キャリー i abcd efgh を介して右レジスタをローテーションします。かなりクール; 4 ビット シフト関数で 8 ビット シフトを実行しました。

開始する前にキャリー ビットをクリアした場合 (多くの場合、これに関する命令が存在するか、0+0 を追加するなど、そのビットをクリアすることが保証されている何かをいつでも実行できます)、次のようになります。

私は0bcd efgh

これは、64ビット数で動作する32ビット命令セットで言う場合、Cシフト関数が行うことと同じです。

プロセッサには、多くの場合、0 がシフトインされる C のようなシフトがあります。シフト abcd 左 1 は bcd0 を返し、シフト abcd 右 2 は 00ab を返します。

そして、これは最新のプロセッサを使用する若い人々にいくつかの問題を引き起こします...整数除算はプロセッサでサポートされており、単一のクロックサイクルで動作できるため、そのようなことを考えてください. 除算が行われる前、または除算が数十から数百のクロックであったとき、シフトは単一のクロックであり、代わりにシフトを使用して 2 の累乗または乗算をすべて実行していました。0b00001101 << 2 = 0b00110100 または 0x34. 0xD は 10 進数の 13 で、0x34 は 10 進数の 52 です。52 は 13 の 4 倍です。4 は 2 の 2 乗です。2 だけシフトすることは、4 を掛けることと同じです。

これは双方向に機能します。0x34 右シフト 2 は 0xD ですが、ここに問題があります。負の数になったら、4 0xFC を引いた数を取り、それを 2 で割ります。C 0xFC >> 1 を使用すると 0x7E になりますが、0x7E は +126 10 進数です。-4/2 = 126 はどのようになりますか?

問題は、C がゼロにシフトすることです。一部のプロセッサには、論理シフトとは異なる算術シフトがあることがわかります。算術シフトは最上位ビットを保持するため、0bQWER のような符号付き数値を使用している場合、その数値を算術的に右に 1 ビットシフトすると、0bQQwe が得られます。最上位ビットは次のビットにシフトし、元の場所にとどまります。

再び 0bQQQW にシフトします。ここで、算術左シフトは最下位ビットではなくゼロをシフトするため、左にシフトされた 0bQWER は 0bWER0 です。そして、それは理にかなっています。-4 左シフト 1 は 0xF8 で、-8 で、-4 かける 2 は -8 です。

そのため、一部のプロセッサには算術右シフトのみがあり、左シフトがないことがわかります。asl を指定できるものもありますが、アセンブル時にそれを lsl (論理左シフト) に置き換えます。同じ関数であっても、実際には別のオペコードを持っているものもあります。asl と asr と lsr があり、lsl がないものがあると思います。

紙と鉛筆を使って物事を理解するだけです。例として実数から始めて、次に抽象化します。右に 1 ビット回転させたいとし0x1234ましょう。

0001001000110100  write out the bits
x0001001000110100 shift right one
0000100100011010  because this is a rotate fill in the new bit with the bit that fell off on the prior operation

右に 2 ビットシフトしたい

0000100100011010
xx0000100100011010
1000001001000110

Cで単一ビットの回転を行うにはどうすればよいですか?

unsigned int rotate_right_one ( unsigned int x )
{
  unsigned int y;
  y = x & 1;  // Save the bit that is about to fall off the right
  x >> = 1;  // Logical rotate one bit
  x |= y<<31; // This assumes that unsigned int is 32 bits.
  return(x);
}

さらに回転するには、この関数を複数回呼び出すか、上記のマスクとシフトについて考え、それが複数のビットに対してどのように機能するかを考えます。

また、回転機能が 1 つしかないプロセッサーもあることに注意してください。たとえば、これについて考えてみてください。4 ビットのレジスタがあり、5 ビットをローテーションします。何を得るか？

abcd
bcda  first rotate
cdab  second
dabc  third
abcd  fourth
bcda  fifth

左に 1 回回転すると、どのように見えますか?

abcd
bcda  one bit left.

4 ビット レジスタの 5 つの右は、1 つの左 5-4=1 と同じです。asl のように、一部のプロセッサでは操作をコーディングできますが、アセンブラは回転量として nbits-shift を使用して、その操作を別の回転に置き換えます。

一部の人々にとって、論理ビット操作は理解するのがポインターと同じくらい難しいですが、それは基本的なものであり、それを学んで使用すれば、競合他社や周囲の人々よりもはるかに先を行くでしょう.

以下は、変数のビット数をカウントする例です。

for(count=0, r=1; r; r<<=1) 
    if(r&some_variable) 
        count++;

そのコード行を理解すれば、C と論理ビット演算の両方を学習するための順調な道のりです。

于 2009-01-15T15:13:35.327 に答える
1

例として 2-6 を取り上げ、値 17、4、3、15 を使用しました
。

x = 17 または 10001

p = 4

n = 3

y = 15 または 01111

私の例の数値を使用すると、ここで行う必要があるのは、y (111) から 3 つの ls ビットを取得し、位置 4 から始まる x に挿入することです。これにより、11111 または 31 が得られます。 4 番目の位置に移動し、右端の 3 ビットを除く y のすべてのビットをクリアし、それらを 4 番目の位置に移動して、2 つの値を OR します。

1 つ目: すべて 1 を n 桁左にシフト ~0 << n = 1111111111111000

2番目: 右端の n 個の位置にすべて 1 を配置 ~(~0 << n) = 0000000000000111

3 番目: これらの n 1 ビットを位置 p にシフトし、位置 p から始まる n ビットをゼロに設定します。~(~(~0 << n) << (pn)) = 1111111111110001

4番目: そして、このマスクを x で使用して、位置 p = 10001 の x の n ビットをクリアします。

(私たちが行ったことは最初の数に戻っただけだと誰もが理解していると思いますが、どの位置から開始したいのか、何ビットで作業したいのかをプログラムに伝えるためにこれを行う必要があります. p が 6 で n が 4 の場合は?)

次に、右端の n ビットを除く y のすべてのビットをクリアします。

1 つ目: ~(~0 << n) は、すべて 1 を右端 n の位置に配置します。0000000000000111

2番目: y & ~(~0 << n) y 0000000000000111の右端nビットを選択

3番目: (y & ~(~0 << n)) << (pn) 位置 p 0000000000001110 に y の n ビットを配置 最後に 2 つの結果を OR します

0000000000010001 = 17

0000000000001110 = 7 または =

0000000000011111 = 31

結果は次のようになります。

return x & ~(~(~0 << n) << (pn)) | (y & ~(~0 << n)) << (pn);

これがまったく読みにくい場合は申し訳ありません。私の書式設定能力はいくらか制限されていました。（これは私のせいだと確信しています）これが役立つことを願っています。私はこの特定の演習にかなり長い間行き詰まっていました。正しい答えを投稿するだけでなく、なぜそれが正しい答えなのかについての説明を投稿してください。これは、私が見た多くの答えに欠けていることがわかったものです。

于 2012-01-22T23:12:53.583 に答える
0

サンプルとして、1つの演習を行いましょう。

演習2-6：位置pから始まるnビットをyの右端のnビットに設定してxを返す関数setbits（x、p、n、y）を記述し、他のビットは変更しないでください。

最下位ビットはビット0（位置0）であることに注意してください。

擬似コードは次のとおりです。

  1. xのビットpをp+nに移動し、位置0からnに移動します。それはあなたが右シフトするところです。
  2. ビットnから最上位ビットまでを0に変換するビットマスクを準備します。これにはルックアップ配列を使用できます（たとえば、n = 8の場合は0xFF、7の場合は0x7Fなど）。または、ビット0の設定とループ内での左シフトの組み合わせを使用できます。
  3. xを使用してビットマスクを適用します&。気にしないビットはすべてx0になりました。
  4. ビットマスクを反転します。これで、ハイエンドに1の束があり、ローエンドに0の束があります。yで変更したいビットはすべて、ビットマスクに0があります。
  5. ＆を使用してビットマスクをyに適用します。これで、xのビットに置き換えるyのすべてのビットが0に設定され、変更したくないビットは変更されません。
  6. を使用してxとyを組み合わせて、yに変更するビットを設定します|。これが重要なポイントです。ペンと紙で何が起こっているのかを調べてください。（3）で0に設定されたxのビットは、yの対応するビットに影響を与えません。（3）の影響を受けなかったxのビットは、yの0（ステップ5のために0）と結合し、結果のビットをxの値に設定します。
于 2009-01-14T16:16:19.973 に答える
0

お金（そして時間）があれば、ハッカーのたのしみ（ヘンリー・S・ウォーレン作）のコピーを手に入れてください。それはおそらく周りの最高のビットシフトガイドです。グレイコードなどを介して、単純なシフト（およびその他の操作手法）を実行できます...

于 2009-01-14T16:00:46.900 に答える
0

2 ～ 6 を試して、ビット操作がどのように機能するかを味わってから、それが理にかなっているかどうかを確認してみましょう。

int setbits( int x, int p, int n, int y )
{
    int bitmask = ~0, y_right = 0; 

    /* Ok, first let's get y's rightmost bits.
     * Take our bitmask, shift it left by n bits, leaving the least significant
     * n bits as 0. Then, flip the bitmask so the rightmost n bits become 1, and the
     * leftmost n bits become 0.
     *
     * Then, AND this bitmask with y, to yield y's n rightmost bits.
     */
    bitmask = ~( bitmask << n );
    y_right = bitmask & y;

    /*
     * Ok, now let's use y_right as our bitmask for x.
     * Shift y_right to the left to *begin* at position p.
     */
     y_right <<= p - n;
     x |= y_right;

     return x;
}

注: 上記はテストしていないため、完全に間違っている可能性がありますが、最初は適切なアイデアが得られるはずです。

于 2009-01-14T22:03:18.120 に答える
0

これらの演習のほとんどすべてに、関数 int IsBitSet(int i, int n); で記述できる簡単なソリューションがあることに注意してください。int SetBit(int i, int n); << と >> の組み合わせ。単純な解決策はほぼすべて最悪のケースですが、実装と読み取りがはるかに簡単です。これは、加算の観点から乗算を実装したり、増分の観点から加算を実装したりするようなものです。

于 2009-01-14T17:09:39.600 に答える