0

私はビット単位の操作に慣れていません。私はこのシーケンスを持っています:

1 0 0 0 0 : 16
---------------
0 1 1 1 1 : 15
---------------
0 1 1 1 0 : 14
---------------
.
.
.
---------------
0 0 0 1 1 :  3
---------------
0 0 0 1 0 :  2
---------------
0 0 0 0 1 :  1
---------------

「1」が複数あるかどうかを最初に確認したい。その場合は、小数値が大きい方を削除して、残りの大きい方を取得して終了したいと思います。たとえば、15 には 4 つの "1" があり、"8" の "1" の大きい方を削除すると、"0 0 1 1 1 : 7" になり、大きい "1" は "4" になります。これどうやってするの?

4

2 に答える 2

1

これがあなたが望むことをするコードです:

unsigned chk_bits(unsigned int x) {
    unsigned i;
    if (x != 0 && (x & (x-1)) != 0) {
        /* More than one '1' bit */
        for (i = ~(~0U >> 1); (x & i) == 0; i >>= 1)
            ; /* Intentionally left blank */
        return x & ~i;
    }
    return x;
}

符号なしの数値を扱っていると仮定していることに注意してください。符号拡張により、符号付き整数で右シフトが定義されているため、これは通常より安全です。

このifステートメントは、 に複数のビットが設定されているかどうかをチェックしxます。は、最初の '1' の最下位ビットをオフにした場合x & (x-1)と同じ数を取得する既知の方法です(たとえば、 isの場合、is です。したがって、 は次のように言います:xx101100100x & (x-1)101100000if

x がゼロではなく、1 に設定された最初のビット (LSB から MSB の順) をオフにすると、0 以外の値になる場合は...

これは、 に複数のビットが設定されていると言うのと同じxです。

次に、 のすべてのビットをループしx、設定されている最初の最上位ビットで停止します。iは に初期化され1000000000000000000000000000、ループx & iは がゼロ以外に評価されるまでそれを右シフトし続けます。その時点で最初の最上位ビットである が見つかりました1。その時点で、 の補数を取ると、でiこのビットをオフにするマスクが生成されます。これは、 であった唯一のビット( の最上位ビットに対応する)を除いて、すべてのビットが 1 に設定された数値であるためです。したがって、これを AND すると、必要なものが得られます。x~i1xx

コードは移植可能です。特定の表現を前提としておらず、unsigned32 ビットまたは 64 ビットであるという事実に依存していません。

更新:コメントを読んだ後、より詳細な説明を追加しています。

第 1 ステップ - 何をするのかを理解するx & (x-1):

ここでは、次の 2 つの可能性を考慮する必要があります。

  • x1 ( .......0011001)で終わる
  • x.......00110000 ( )で終わる

最初のケースでは、右端のビットが 0 に設定されてx-1いるだけであることが簡単にわかります。x0011001 - 1 = 0011000x & (x-1)x-1

2 番目のケースでは、理解するのが少し難しいかもしれませんが、の右端のビットがx0の場合、1x-1x見つかるまで、最下位ビットから始めて、すべての 0 ビットが 1 ビットに切り替えられます。が 0 に変わります。

これは、これに慣れていない人にとってはトリッキーになる可能性があるため、例を挙げましょう。

1101011000 - 1 = 11101010111

何故ですか?0 で終わる 2 進数の前の数は、右端の位置に 1 つ以上の 1 ビットで埋められた 2 進数であるためです。のよう10101111101111 + 1にインクリメントする場合、次の「空き」位置、つまり次の 0 位置をインクリメントして 1 に変換する必要があり、その位置の右側にあるすべての 1 ビットが 0 に変換されます。 . これは、すべての base-n のカウント方法です。唯一の違いは、base-2 の場合は 0 と 1 しかないことです。

基数 10 のカウントがどのように機能するかを考えてみてください。桁がなくなると、値がラップアラウンドし、左側に新しい桁が追加されます。後は何999ですか?さて、カウントが再びリセットされ、左側に新しい数字が追加され、9 が 0 に戻り、結果は1000. バイナリ演算でも同じことが起こります。

バイナリでカウントするプロセスについて考えてみてください。0 と 1 の 2 ビットしかありません。

  • 0 (10 進数の 0)
  • 1 (10 進数の 1 - 現在、ビットが不足しています。次の数値では、この 1 は 0 に変わり、左側に新しいビットを追加する必要があります)
  • 10 (10 進数 2)
  • 11 (10 進数の 3 - プロセスが再び繰り返されます - ビットがなくなったので、これらの 2 ビットは 0 になり、左側に新しいビットを追加する必要があります)
  • 100 (10 進数 4)
  • 101 (10 進数の 5)
  • 110 (同じプロセスが再び繰り返されます)
  • 111
  • ...

パターンが私が説明したとおりであることがわかりますか?

が0でx終わる2番目のケースを考えていることを思い出してください。したがって、同じままである部分は、0 に変わった 1 の左側の部分だけです。x-1xxx-1xx-1x

したがって、最初の右端の 1 ビットがあった位置まではx & (x-1)同じになります。xこれで、どちらの場合でも、x & (x-1)実際には の右端の 1 ビットが削除されることがわかりxます。

2 番目のステップ: 正確には何~0U >> 1ですか?

文字Uはの略ですunsignedintC では、指定しない限り、整数定数は型になります。U整数定数にaを追加すると、符号なしになります。これを使用したのは、前述したように、右シフトが符号拡張を行うかどうかは実装定義であるためです。単項演算子~は補数演算子であり、数値を取得し、その補数を取ります。0 ビットごとに 1 になり、1 ビットごとに 0 になります。つまり、~0 は 1 で満たされた数値です11111111111...。次に、それを 1 桁右にシフトすると、次のよう01111111....になります。これを表す式は です~0U >> 1。最後に、その補数を取って を取得します。100000....これはコードでは~(~0U >> 1)です。これは、左端のビットを 1 に設定し、その他すべてのビットを 0 に設定して数値を取得する移植可能な方法です。

K&R の第 2 章、より具体的にはセクション 2.9 を参照してください。48 ページからは、ビット単位の演算子が示されています。練習問題 2-9 では、なぜx & (x-1)機能するのかを説明するよう読者に求めます。ご存じないかもしれませんが、K&R は C の生みの親である Kernighan と Ritchie によって書かれた C プログラミング言語について説明した本です。本のタイトルは「The C Programming Language」です。第 2 版を入手することをお勧めします。 . すべての優れた C プログラマーは、この本から C を学びました。

于 2013-11-04T10:53:27.887 に答える
0

「1」が複数あるかどうかを最初に確認したい。

数値の 2 進数表現が 1 の場合、それは 2 x1の形式で表現できる数値です。例えば、

4 00000100 2^2  
32 00010000 2^5

したがって、単一のものを確認するには、このプロパティを確認するだけです。

log 2 ( x ) が整数の場合、その1バイナリ表現は single になります。

log 2 ( x )を計算できます

ログ2 ( x ) = ログy ( x ) / ログy (2)

ここで、yは何でもかまいません。標準のログ関数の場合、 10 またはeです。

ここに解決策があります

double logBase2 = log(num)/log(2);   
if (logBase2 != (int)logBase2) {

    int i = 7;
    for (;i >0 ; i--) {

        if (num & (1 << i)) {

            num &= ~(1 << i);
            break;
        }
    }
}

于 2013-11-04T05:31:54.060 に答える