0

私のニーズ:

非負の unsigned long a については、

入力 a = 5; Ans は 3 である必要があります

入力 a = 12; Ans は 4 である必要があります

入力 a = 1; Ans は 1 でなければなりません

入力 a=0 Ans は 0 でなければなりません

つまり、左から最も重要な 1 つの位置を見つけます。

私が試したこと：

int count = 0;

if( a!=0 )
 do{
   count++;
 }while( a >>= 1 );

問題 while ループとシフトのために時間がかかります。

提案された方法 4 バイトがどのようにメモリに格納されているかがわかっている場合 (char* を使用)、最上位の 1 を含むバイトを取り出します。したがって、最悪の場合、答えを見つけるには最大 8 回のシフトで十分です。

4

2 に答える 2

1

そうしないでください。探しているビットが最上位バイトに含まれていない場合 (つまり、数値が より小さい場合2 ^ (3 * CHAR_BIT))、メソッドは機能しません。片っ端から始めてみませんか？

unsigned find_msb(unsigned long long n)
{
    int bits_max = sizeof(n) * CHAR_BIT - 1;
    int i;
    for (i = bits_max; i >= 0; i--) {
        if ((n >> i) & 1) return i + 1;
    }
    return 0;
}
于 2013-02-23T17:13:14.163 に答える
1

あなたは効率を心配する方法があると思います。最悪の場合は O(n) であり、率直に言って、これ以上良くなることはありません。遅いプロセッサの組み込みシステムであっても、H2CO3 のアルゴリズムを試して高速化する必要はありません。

それを機能させてから、効率について心配してください。

于 2013-02-23T19:50:43.087 に答える