c - 左から1が連続する数を数える

Question

私はこの問題に行き詰まっています: 32 ビット整数があると仮定し、左から連続する 1 ビットの数をカウントする C 関数を記述します。例えば：

leftCount(0xFF000000) = 8
leftCount(0x0FFFFFFF) = 0 (because the number starts with 0)
leftCount(-1) = 32

関数では、! などの論理演算子を使用できます。〜＆^ | + << >>

ループおよび条件構造は使用できません。

ありがとう

Answer 1

を評価することにより、ビットxが値に設定されているかどうかをテストできます。ビットが設定されていない場合はゼロです。yy & (1 << x)

これを使用すると、31 から 0 までループして、各ビットが設定されているかどうかを確認し、設定されていないビットに到達すると停止します。これを自分でコーディングできるはずです。

バイナリ検索を使用すると、これを高速化できます。を評価することで、最初の 16 ビットが設定されているかどうかを確認できます(y & 0xFFFF0000) == 0xFFFF0000。そうであれば、同様の方法で次の 8 ビットをチェックできます。そうでない場合は、最初の 8 ビットを確認できます。この方法を使用して下に再帰すると、より高速なアルゴリズムが得られます。

Answer 2

GCC では、組み込み関数を使用できます。

組み込み関数:int __builtin_clz (unsigned int x)

x最上位ビット位置から始まる、先頭の 0 ビットの数を返します。が 0 の場合x、結果は未定義です。

バイナリ否定を使用して入力を否定する必要があります~x(0 は 1 になり、その逆も同様です)。

---

より学術的な解決策は次のとおりです。

#include <stdio.h>
#include <stdint.h>

int leftCount (unsigned int value) {
    if (~value == 0) {
        return 32; // you said your ints were 32 bits, so the code assumes that
    }
    int result = 0;
    while (value >> 31 == 1) { // test if highest bit is set
        value <<= 1; // shift the input to the left
        ++result; // one more bit was seen
    }
    return result;
}

int main (void) {
    unsigned int value;
    while (scanf ("%i", &value) == 1) {
        printf ("leftCount(0x%x) == %u\n", value, leftCount(value));
    }
    return 0;
}

Answer 3

先行ゼロの数をカウントする高速関数があり、この問題を次のように変換するのは簡単です: 入力を補完します。

int leftCount = input == 0 ? 0 : __builtin_clz(~input);

そこにはアルゴリズムすらありません。

Answer 4

ネタバレ：

#include <limits.h>
#include <stdint.h>
#include <stdio.h>

unsigned naive_leading1bit_count(uint32_t val)
{
unsigned cnt;

for (cnt=0; val & (1u << (sizeof val*CHAR_BIT-1)); val <<=1 ) {
        cnt += 1;
        }
return cnt;
}

int main(void)
{
unsigned res;
uint32_t uuu;

for (uuu = 0xf; uuu; uuu <<=1) {
        res = naive_leading1bit_count( uuu );
        printf("%x: %u\n", uuu, res);
        }

return 0;
}