c - msb から始まる最初のゼロ以外のビットを見つける方法

Question

160 ビットの数値を格納する 20 ワード/バイトの配列があります。msb から始まる最初のゼロ以外のビットを見つけるにはどうすればよいですか。ビットの位置を見つける必要があり、それに応じて最初の「1」の位置からいくつかの操作を行う必要があります。

Answer 1

gcc を使用している場合は、まさにそれを行う組み込み関数 (およびその他の多くのこと) があります。

http://gcc.gnu.org/onlinedocs/gcc-4.5.4/gcc/Other-Builtins.html

あなたが探しているのは、おそらく__builtin_clz(unsigned int の場合)、__builtin_clzl(unsigned long の場合)、または__builtin_clzllunsigned long long の場合です。

ドキュメントから：

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

したがって、int (longs? longlongs?) を最も重要なものからゼロではない最初のものを見つけるまで調べてください。次に、適切な を使用して__builtin_clz先行ゼロの数を見つけます。32 (64) からその数値を引いたものが、数値の最上位1ビットの位置です。

もちろん__builtin_clz、他のコンパイラとの互換性を保ちたい場合は、いつでも自分で実装できます (そうすべきです!)。