5

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

私の解決策の試みは次のとおりです。

#include <stdio.h>

unsigned setbits(unsigned, int, int, unsigned);

int main(void)
{
    printf("%u\n", setbits(256, 4, 2, 255));
    return 0;
}

unsigned setbits(unsigned x, int p, int n, unsigned y)
{
    return (x >> (p + 1 - n)) | (1 << (n & y));
}

おそらく間違っていますが、ここで正しい道を進んでいますか？そうでない場合、私は何を間違っていますか? なぜこれが完全に理解できないのかはわかりませんが、これを考え出すのに約 1 時間費やしました。

ありがとう。

4

3 に答える 3

5

アルゴリズムは次のとおりです。

  1. n が 0 の場合、x を返します。
  2. 1 を取り、それを n 回左シフトしてから 1 を引きます。これを と呼びますmask。
  3. 左シフト マスク p 回これを呼び出しますmask2。
  4. Andx は mask2 の逆です。Andマスク付きの y と左シフト p 回。
  5. Orこれら 2 つの操作の結果を返し、その値を返します。
于 2010-01-16T03:33:24.950 に答える
2

答えは、セクション 2.9 の getbits の例を少し修正したアプリケーションだと思います。

次のように分解しましょう。

Let bitstring x be 1 0 1 1 0 0
Let bitstring y be 1 0 1 1 1 1

positions -------->5 4 3 2 1 0

設定p = 4 and n =3により、 x からのビット文字列が得られ0 1 1ます。4 で始まり 2 で終わり、3 つの要素にまたがります。

やりたいことは0 1 1、1 1 1(ビット文字列 y の最後の 3 つの要素) に置き換えることです。

しばらく左シフト/右シフトを忘れて、次のように問題を視覚化しましょう。

ビット文字列 y から最後の 3 桁を取得する必要があります。1 1 1

ビット文字列 x1 1 1の位置の直下に配置します。4 3 and 2

0 1 1残りのビットは1 1 1そのままに置き換えます...

では、もう少し詳しく見ていきましょう...

私の最初の声明は次のとおりです。

We need to grab the last three digits from bitstring y which is 1 1 1

ビット文字列からビットを分離する方法は、最初にすべて 0 のビット文字列から始めることです。で終わり0 0 0 0 0 0ます。

0 には、別の数値でビットごとに '&' するとすべて 0 になり、別の数値でビットごとに '|' するとその別の数値が返されるという驚くべき特性があります。

0 自体はここでは役に立ちません...しかし、'|' y の最後の 3 桁が「0」の場合、最終的には 1 1 1 になります。y の他のビットは、ここではあまり関係ないので、これらの数値をゼロにしながら、最後の 3 桁はそのままです。本質的に、番号が必要0 0 0 1 1 1です。

それでは、必要な一連の変換を見てみましょう。

Start with  ->  0 0 0 0 0 0
apply ~0    ->  1 1 1 1 1 1
lshift by 3 ->  1 1 1 0 0 0 
apply ~     ->  0 0 0 1 1 1
& with y    ->  0 0 0 1 1 1 & 1 0 1 1 1 1 -> 0 0 0 1 1 1

そして、このようにして、目的を設定するために使用される最後の 3 桁が得られます...

私の2番目の声明は次のとおりです。

ビット文字列 x の位置 4 3 と 2 のすぐ下に 1 1 1 を配置します。

これを行うためのヒントは、セクション 2.9 の getbits の例から見つけることができます。位置 4、3、および 2 についてわかっていることは、値から見つけることができますp = 4 and n =3。p は位置、n はビットセットの長さです。右端p+1-nのビットからのビットセットのオフセットが得られます。この特定の例ではp+1-n = 4 +1-3 = 2。

したがって、文字列 を 2 だけ左シフトすると、 になり0 0 0 1 1 1ます0 1 1 1 0 0。この文字列を x の下に置くと、x の1 1 1位置と一致することがわかり4 3 and 2ます。

私は最終的にどこかに到達していると思います..私がした最後の声明は..

残りのビットはそのままにして、0 1 1 を 1 1 1 に置き換えます...

文字列を見直してみましょう:

x           ->   1 0 1 1 0 0
isolated y  ->   0 1 1 1 0 0

これら 2 つの値に対してビット単位の or を実行すると、この場合に必要なものが得られます。

1 1 1 1 0 0

1 1 1しかし、もし の代わりにがあったとしたら、これは失敗するでしょう1 0 1...だから、「銀の弾丸」にたどり着くためにもう少し掘り下げる必要があるとしたら...

上記の 2 つの文字列をもう一度見てみましょう...

x -> bit by bit...1(stays) 0(changes) 1(changes) 1(changes) 0(stays) 0(stays)

1 x x x 0 0したがって、理想的には、x が 1 に置き換えられる bitstring が必要です。ここに私たちを助ける直感の飛躍があります..

Bitwise complement of isolated y -> 1 0 0 0 1 1
& this with x gives us           -> 1 0 0 0 0 0
| this with isolated y           -> 1 1 1 1 0 0 (TADA!)

この長い投稿が、このようなビットマスキングの問題を合理化し、解決するのに役立つことを願っています...

ありがとう

于 2012-02-07T11:03:50.970 に答える
0

~0 << i最下位iビットが に設定され0、残りのビットが に設定された数値が得られることに注意してください1。同様に、~(~0 << i)最下位iビットが に設定され1、残りが に設定された数値が得られます0。

さて、あなたの問題を解決するには：

  1. nまず、 position で始まるビットを除くすべてのビットがpのビットに設定された数値が必要ですx。このためには、 position で始まるビット1を除くすべての場所で構成されるマスクが必要です。 np
    1. このマスクには、位置 のビットから始まる最上位 (最上位) ビットが設定されていますp+1。
    2. このマスクには、最下位p+1-nビットも設定されています。
  2. 上記のマスクを取得したら&、このマスクを使用xすると、ステップ 1 で必要な番号が得られます。
  3. ここで、設定されたビットの最下位nビットyが左にシフトされた数値が必要ですp+1-n。
    1. 最下位nビットのみが設定されたマスクを簡単に作成でき、&それを使用しての最下位ビットyを抽出できます。yn
    2. p+1-n次に、この数値をビット単位でシフトできます。
  4. 最後に、ステップ 2 と 3.2 の結果を bitwise-or ( |) して数値を取得します。

泥のように透明？:-)

(上記の方法は、数値のサイズに依存しない必要があります。これは重要だと思います。)

編集：あなたの努力を見てください：ビットn & yでは何もしません。nたとえば、nが 8 の場合、 の最後の 8 ビットが必要ですがy、(バイナリの 8 は 1000 です)n & yの 4 番目のビットだけが選択されます。yだからあなたはそれが正しくないことを知っています。同様に、時間を右シフトすると、最上位ビットがゼロに設定され、残りのビットが の最上位ビットで構成されるx p+1-n数値が得られます。これもあなたが望むものではありません。p+1-nx

于 2010-01-16T05:39:13.763 に答える