5

重複の可能性:
1 または 0 の連続するビット文字列を見つける

整数の連続する 1 を左から数えることはできますか? つまり、先頭ビットから始まる連続したセットビットの総数。

使用のみ:

! ~ & ^ | + << >>

-1= 0xFFFFFFFF32 を返す

0xFFF0F0F012 を返します (FFF = 111111111111)

残念ながらループはありません。

マシンを想定できます：

  1. 整数の 2 の補数、32 ビット表現を使用します。

  2. 右シフトを算術的に実行します。

  3. ワード サイズを超えて整数をシフトすると、予期しない動作が発生します。

私は以下を禁じられています:

  1. if、do、while、for、switch などの制御構造を使用します。

  2. マクロを定義または使用します。

  3. このファイルで追加の関数を定義します。

  4. 任意の関数を呼び出します。

  5. &&、||、-、または ? などの他の操作を使用します。

  6. あらゆる形式の鋳造を使用します。

  7. int 以外のデータ型を使用します。これは、配列、構造体、または共用体を使用できないことを意味します。

私は 1 または 0 の連続したビット文字列の検索を見てきました 。使用できないループを使用しています。どこから始めればよいかさえわかりません。

(はい、これは課題ですが、十分なスキルをお持ちの方に助けを求めているだけです。必要な作業はほぼすべて完了しましたが、これはうまくいきません。)

(学校向けという理由だけで反対票を投じる方: FAQ: 1 特定のプログラミングの問題、チェック 2 ただし、「他の人に ______ を説明してもらいたい」という理由であれば、おそらく問題ありません。)

4

5 に答える 5

2

はい、どうぞ。関数の引数は、符号付きまたは符号なしの場合があります。algは署名に依存しません。

int leftmost_ones(int x)
{
    x = ~x;
    x = x | x >> 1 | x >> 2 | x >> 3 | x >> 4 | x >> 5 | x >> 6 | x >> 7 | 
        x >> 8 | x >> 9 | x >> 10 | x >> 11 | x >> 12 | x >> 13 | x >> 14 | 
        x >> 15 | x >> 16 | x >> 17 | x >> 18 | x >> 19 | x >> 20 | x >> 21 | 
        x >> 22 | x >> 23 | x >> 24 | x >> 25 | x >> 26 | x >> 27 | x >> 28 | 
        x >> 29 | x >> 30 | x >> 31;
    x = ~x;
    return (x & 1) + (x >> 1 & 1) + (x >> 2 & 1) + (x >> 3 & 1) + (x >> 4 & 1) + 
        (x >> 5 & 1) + (x >> 6 & 1) + (x >> 7 & 1) + (x >> 8 & 1) + (x >> 9 & 1) + 
        (x >> 10 & 1) + (x >> 11 & 1) + (x >> 12 & 1) + (x >> 13 & 1) + (x >> 14 & 1) +
        (x >> 15 & 1) + (x >> 16 & 1) + (x >> 17 & 1) + (x >> 18 & 1) + (x >> 19 & 1) +
        (x >> 20 & 1) + (x >> 21 & 1) + (x >> 22 & 1) + (x >> 23 & 1) + (x >> 24 & 1) +
        (x >> 25 & 1) + (x >> 26 & 1) + (x >> 27 & 1) + (x >> 28 & 1) + (x >> 29 & 1) +
        (x >> 30 & 1) + (x >> 31 & 1);
}

いくつかの最適化を備えたバージョン：

int leftmost_ones(int x)
{
    x = ~x;
    x |= x >> 16;
    x |= x >> 8;
    x |= x >> 4;
    x |= x >> 2;
    x |= x >> 1;
    x = ~x;

    return (x & 1) + (x >> 1 & 1) + (x >> 2 & 1) + (x >> 3 & 1) + (x >> 4 & 1) + 
        (x >> 5 & 1) + (x >> 6 & 1) + (x >> 7 & 1) + (x >> 8 & 1) + (x >> 9 & 1) + 
        (x >> 10 & 1) + (x >> 11 & 1) + (x >> 12 & 1) + (x >> 13 & 1) + (x >> 14 & 1) +
        (x >> 15 & 1) + (x >> 16 & 1) + (x >> 17 & 1) + (x >> 18 & 1) + (x >> 19 & 1) +
        (x >> 20 & 1) + (x >> 21 & 1) + (x >> 22 & 1) + (x >> 23 & 1) + (x >> 24 & 1) +
        (x >> 25 & 1) + (x >> 26 & 1) + (x >> 27 & 1) + (x >> 28 & 1) + (x >> 29 & 1) +
        (x >> 30 & 1) + (x >> 31 & 1);
}
于 2012-09-26T16:40:13.230 に答える
1

次のように実行できます。

int result = clz(~x);

つまり、すべてのビットを反転してから、先頭のゼロを数えます。

clzffs先頭のゼロ ビットの数を返します (一般にまたはとも呼ばれますnlz) - 実装の詳細については、こちらを参照してください: http://en.wikipedia.org/wiki/Find_first_set#Algorithms

于 2012-09-26T16:09:24.767 に答える
1

ループは使えますか？

int mask = 0x80000000;
int count = 0;
while (number & mask) {
    count += 1;
    mask >>= 1;
}
于 2012-09-26T15:52:45.243 に答える
1

基本的に典型的なループを展開し、一般的に迷惑をかけることで、それは実行可能だと思います。

これはどうですか: 答えが 1 の場合にのみ 1 になる式はどうでしょうか? 私が提供しています：

const int ok1 = !((number & 0xc0000000) - 0x800000000);

もちろん、 との減算は、誰かがキーボードのキーを!壊したことを回避するためのものです。==

そして、答えが 2 の場合にのみ 1 になる式:

const int ok2 = !((number & 0xe0000000) - 0xc0000000);

これらを形成し続けると、最終的な答えはそれらの合計になります。

const int answer = ok1 + ok2 + ... + ok32;

そういえば、学生時代に変に制限された課題を与えられた記憶がないみたいで、時代が変わったのかな。:)

于 2012-09-26T16:35:54.533 に答える
0 
int count_consecutive_bits(unsigned int x) {
    int res = 0;
    while (x & 0x80000000) { ++res; x <<= 1; }
    return res;
}
于 2012-09-26T15:50:39.947 に答える