-1

ビット単位の演算子 (C)、単項演算子 ~ と !、および符号付き整数変数のみを使用して関数を実装する必要がある演習で問題が発生しています。条件、ループ、または任意の数値を使用することは許可されていません。マイナス (-) を使用することさえ許可されていませんが、これには非常に簡単な回避策があります。

基本的には、最上位ビットからセットされていないビットが見つかるまで、セットされているビットの数を数えます。最初の設定されていないビットを見つけて伝播するのに問題があることを除いて、これはすべて理解したと思いました。私の考えは、(現在) 左端の 1 ビットを反転して右に伝播し、それを分離してから 3 だけ右にシフトすることでした (分離により 1 つ上にシフトされるため)、結果は次の数になるはずです。これを行うことから、右側に 1 ビットを設定します。

これに関する私の最大の障害は、左端のビット (設定されているかどうかに関係なく) を見つけて伝播することです...アイデア、ヒント、手がかりはありますか?

私の理論的アルゴリズムが行うことの例:

1110 0101 1011 1100    // our target
0001 1010 0100 0011    // invert it
0001 1111 1111 1111    // propagate
0001 0000 0000 0000    // magic happens -- isolate the leftmost 1 bit
0000 0100 0000 0000    // shift by >>2
// it's at this point I realize I have no idea what I'm doing anymore
// this looks like 2^10 which is a bit too big...

だから、基本的に私は何も持っていません。誰かが私が何について読むべきかについてのヒントを教えてもらえますか?

4

1 に答える 1

1

各ビットを1つずつテストすることによる、8ビット整数の「ブルートフォース」ソリューション：

int countLeadingBits(int8 x)
{
    int isSetFirst1 = (!!(x & 0x80));               /* 1 if bit pattern is 1xxxxxxx */
    int isSetFirst2 = (!!(x & 0x40)) & isSetFirst1; /* 1 if bit pattern is 11xxxxxx */
    int isSetFirst3 = (!!(x & 0x20)) & isSetFirst2; /* 1 if bit pattern is 111xxxxx */
    int isSetFirst4 = (!!(x & 0x10)) & isSetFirst3; /* etc */
    int isSetFirst5 = (!!(x & 0x08)) & isSetFirst4;
    int isSetFirst6 = (!!(x & 0x04)) & isSetFirst5;
    int isSetFirst7 = (!!(x & 0x02)) & isSetFirst6;
    int isSetFirst8 = (!!(x & 0x01)) & isSetFirst7;

    return isSetFirst1 +
           isSetFirst2 +
           isSetFirst3 +
           isSetFirst4 +
           isSetFirst5 +
           isSetFirst6 +
           isSetFirst7 +
           isSetFirst8;
}

のような 1 ビットを分離x & 0x40し、二重否定を使用してそれを 0 または 1 に変換すると、0 または 1であることがわかっている数値に対してブール演算子のように!!使用できます。すべてのビットをテストしたら、&それらを追加することで、設定されている数を簡単に数えることができます。

これを必要な数のビットに拡張するのはあなたに任せます。

于 2012-09-21T02:05:10.683 に答える