数字を表すために必要なビット数x

Question

現在、数値xを表すために必要なビット数を決定するアルゴリズムを作成しようとしています。私の実装はcです。 しかし、いくつかのキャッチがありますが、ビット演算子{〜、&、^、|、+、< <、>>}に制限されています。また、どのようなタイプの制御フロー（if、while、for）も使用できません。 私の最初のアプローチは、左から右へバイナリで数値を調べ、最初の '1'の出現箇所を探します。私はこれにどのように取り組んでいるのかわからない。 私が扱っている番号は、符号なし整数と考えることができます。したがって、00110は3ビットしか必要としない。

これを行うにはもっと簡単で清潔な方法があるのでしょうか？私はそれを逃していますか？ 誰かが何かヒントを与えることができますか？

基本的に、私は、whileループせずにこれを実装しようとしていた。

int result = 0; 
    while (x >>= 1) { 
    result += 1; 
    } 
    return result; 

Answer 1

http://www-graphics.stanford.edu/~seander/bithacks.html#IntegerLog

は、制御フローなしでそれを行う方法を示します。

unsigned int v;   // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here 
register unsigned int shift; 

r =  (v > 0xFFFF) << 4; v >>= r; 
shift = (v > 0xFF ) << 3; v >>= shift; r |= shift; 
shift = (v > 0xF ) << 2; v >>= shift; r |= shift; 
shift = (v > 0x3 ) << 1; v >>= shift; r |= shift; 
             r |= (v >> 1); 
r++; 

Answer 2

まあ、彼は最後のビットカウンタではなく1ビットカウンタが必要だと思います。 このアルゴリズムは32ビット整数を意味するため、結果に必要な修正があります。

unsigned int v;   // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here 
register unsigned int shift; 

r =  (v > 0xFFFF) << 4; v >>= r; 
shift = (v > 0xFF ) << 3; v >>= shift; r |= shift; 
shift = (v > 0xF ) << 2; v >>= shift; r |= shift; 
shift = (v > 0x3 ) << 1; v >>= shift; r |= shift; 
             r |= (v >> 1); 
return 32-r; 

Answer 3

私には解決策があります。 ではなく、が高速です。必要なビット数を計算します。つまり、0xFFFFFFFFは32、0x00000000は0です。 Cコードは実際には最上位ビットまたはゼロを計算することに注意してください。

ここでそれは：

#define ISSET(x,i) ((x & (1 << i)) >> i) 
#define FILL(x) ((x << 5) | (x << 4) | (x << 3) | (x << 2) | (x << 1) | x) 
#define IF(x,y,z) ((FILL(x) & y) | (~FILL(x) & z)) 
#define R(x,i,y,z) (IF(ISSET(x,i),y,z)) 

int log2 (uint32_t x) 
{ 
    return R(x,31,32, 
      R(x,30,31, 
      R(x,29,30, 
      R(x,28,29, 
      R(x,27,28, 
      R(x,26,27, 
      R(x,25,26, 
      R(x,24,25, 
      R(x,23,24, 
      R(x,22,23, 
      R(x,21,22, 
      R(x,20,21, 
      R(x,19,20, 
      R(x,18,19, 
      R(x,17,18, 
      R(x,16,17, 
      R(x,15,16, 
      R(x,14,15, 
      R(x,13,14, 
      R(x,12,13, 
      R(x,11,12, 
      R(x,10,11, 
      R(x, 9,10, 
      R(x, 8, 9, 
      R(x, 7, 8, 
      R(x, 6, 7, 
      R(x, 5, 6, 
      R(x, 4, 5, 
      R(x, 3, 4, 
      R(x, 2, 3, 
      R(x, 1, 2, 
      R(x, 0, 1, 0)))))))))))))))))))))))))))))))); 
} 

注：この場合には6ビットが最も高い戻り値（32）を表現するために十分であるがFILLを延長しなければなりません。

注：一般原則は他の機能にも使用できます。

Answer 4

実際には間違っています。 （6の代わりに）32.63、5の代わりに16..31に4を出力します。これは、底2の対数を取って切り捨てるようなものです。

次のように正解がある：

unsigned int v;   // 32-bit value to find the log2 of 
register unsigned int r; // result of log2(v) will go here 
register unsigned int shift; 

r =  (v > 0xFFFF) << 4; v >>= r; 
shift = (v > 0xFF ) << 3; v >>= shift; r |= shift; 
shift = (v > 0xF ) << 2; v >>= shift; r |= shift; 
shift = (v > 0x3 ) << 1; v >>= shift; r |= shift; 
             r |= (v >> 1); 
r++; 

はR ++に留意されたいです。

Answer 5

てみてください：それは宿題

// http://www.cs.northwestern.edu/~wms128/bits.c 
int check_bits_fit_in_2s_complement(signed int x, unsigned int n) { 
    int mask = x >> 31; 

    return !(((~x & mask) + (x & ~mask))>> (n + ~0)); 
}