末尾のゼロの数

Question

私は、数値のバイナリ表現における末尾のゼロの数を返す関数trailing_zeroes（int n）を書いています。

例：4バイナリでは100あるので、この場合の機能は2を返します。

unsigned trailing_zeroes(int n) { 
    unsigned bits; 

    bits = 0; 
    while (n >= 0 && !(n & 01)) { 
     ++bits; 
     if (n != 0) 
      n >>= 1; 
     else 
      break; 
    } 
    return bits; 
} 

if文の理由は、場合n 0に等しいため、ループがあるでしょうです。

私はそれがこのように書かれたかなり醜いこのコードだと思います。そこには良い方法がありますか？

多くの人がwhile/for時々の内側に、そのステートメントを使用すると、「非公式」ことができることを私に言ったので、私は、while内break声明を避けたいです。私はこのような機能を書き換えると思ったが、私はそれはそれを行うための最善の方法だとは思わない：

unsigned bits; 
if (n == 0) 
    return bits = 1; 

bits = 0; 
while (!(n & 01)) { 
    ++bits; 
    n >>= 1; 
} 

Answer 1

あなたの機能が正しくありません：それはまだ0のための無限ループを持っています。テストは次のようになります。あなたはこのアプローチに負の数を扱うことができません

while (n > 0 && !(n & 1)) 

注意、したがって、あなたの関数は、おそらくunsigned数の引数を取る必要があり、またはあなたがunsignedに引数を変換することができます。

unsigned trailing_zeroes(int n) { 
    unsigned bits = 0, x = n; 

    if (x) { 
     while ((x & 1) == 0) { 
      ++bits; 
      x >>= 1; 
     } 
    } 
    return bits; 
} 

上記の機能は非常にシンプルで理解しやすいです：

あなたの関数は特殊なケース0とは、単純なループを使用する必要があります。結果が小さい場合は非常に高速です。 0に返される値は、0は実際にはunsignedタイプの値のビットと同じくらい多くの末尾のゼロがあるため、疑問のある関数のように0です。

一定のステップ数で、より効率的なアプローチがあります：私たちはいくつかのコンパイラが持つ

while (!(x & 0x0000FFFF)) { bits += 16; x >>= 16; } 

への第一歩を変更することにより、任意の大きなintサイズを扱うことができる

unsigned trailing_zeroes(int n) { 
    unsigned bits = 0, x = n; 

    if (x) { 
     /* assuming `x` has 32 bits: lets count the low order 0 bits in batches */ 
     /* mask the 16 low order bits, add 16 and shift them out if they are all 0 */ 
     if (!(x & 0x0000FFFF)) { bits += 16; x >>= 16; } 
     /* mask the 8 low order bits, add 8 and shift them out if they are all 0 */ 
     if (!(x & 0x000000FF)) { bits += 8; x >>= 8; } 
     /* mask the 4 low order bits, add 4 and shift them out if they are all 0 */ 
     if (!(x & 0x0000000F)) { bits += 4; x >>= 4; } 
     /* mask the 2 low order bits, add 2 and shift them out if they are all 0 */ 
     if (!(x & 0x00000003)) { bits += 2; x >>= 2; } 
     /* mask the low order bit and add 1 if it is 0 */ 
     bits += (x & 1)^1; 
    } 
    return bits; 
} 

注組み込み関数__builtin_ctz()を使用して、非常に効率的なアセンブリコードを使用して末尾のゼロ数を数えます。これはC標準関数ではありませんが、移植性の低下を犠牲にして、利用可能であれば使用することをお勧めします。コンパイラのドキュメントを確認してください。ここ

GCC docuemntationから抽象的である：

組み込み関数

：int __builtin_ctz (unsigned int x)

最下位ビット位置から、xに0ビットの末尾の番号を返します。 xが0の場合、結果は不定です。

Answer 2

すでに述べたように、それは、ハードウェアを使用することとして、そこにこれを行うことができます組み込みがあり、かつ、それは非常に速いかもしれません。しかし、doc for GCCは、入力が0の場合、結果は未定義であると言います。これは拡張であるため、コンパイラでは使用できない可能性があります。

それ以外の場合は誰でも「操作」または「ビットカウント」と言う場合は、"Hacker's Delight"のコピーを入手する必要があります。私は両方のエディションを買ったので、とても良い本。これに専用の4ページ（第1版）、 'ntz'（末尾のゼロの数）があります。すでに 'nlz'（先行ゼロの数）または 'popcnt'関数がある場合は、直接ntzを得ることができます。そうでなければ、本はseveral implementationsを提供し、あるものはpopcntを使用し、もう1つはループを使用し、もう1つはバイナリ検索を使用します。例えば

、

int ntz3(unsigned x) { 
    int n; 

    if (x == 0) return(32); 
    n = 1; 
    if ((x & 0x0000FFFF) == 0) {n = n +16; x = x >>16;} 
    if ((x & 0x000000FF) == 0) {n = n + 8; x = x >> 8;} 
    if ((x & 0x0000000F) == 0) {n = n + 4; x = x >> 4;} 
    if ((x & 0x00000003) == 0) {n = n + 2; x = x >> 2;} 
    return n - (x & 1); 
}