3

ループのない数よりも小さい2の最大の累乗を見つけるにはどうすればよいですか？例：

5 output = 4.
11 output = 8.
100 output = 64.
4

6 に答える 6

12

ints でそれを行う少し面倒な方法は次のとおりです。

// given an int number (which would be the upper value of the range)
number |= number >> 1;
number |= number >> 2;
number |= number >> 4;
number |= number >> 8;
number |= number >> 16;
return (number >> 1) + 1;

アイデアは、01010 のようなものを 01111 に変え、1 回シフトして 00111 を取得し、次に 1 を追加して 01000 の結果を取得することです。

これがどのように機能するかを確認するには、入力が 0 または非ゼロのいずれかであると考えてください。0 の場合、すべてのシフトと論理和の結果が 0 になるため、結果は 0+1 になります (2 の 0 乗は 1、最小の 2 の累乗、入力 0 の答え)。

ゼロ以外の数値の場合、ビットのどこかに、その値の最上位セット ビットがあります。私たちが望む答えは、そのビットの後ろにある重要度の低いビットがすべてないことです。その一点に集中してください。0100 | 0100 | 1 だけ右にシフトする最初のシフトでビットごとの OR を実行すると、最上位のセット ビットが引き続きセットされ、それよりも 1 小さいビットもセットされることが保証されます。0010 = 0110. 次にそれ自体と OR をとりますが、今回は 2 つシフトしています。これにより、MSB と末尾の 3 ビットが確実に得られます。int のビット数の上限に達するまで、これを続けます。完全な 32 ビット値の例の手順を次に示します。

01000000110100111000000011010011

01000000000100000000000010000010 |
00100000000010000000000001000001 = 01100000000110000000000011000011 (num |= num >> 1)

01100000000110000000000011000011 |
00011000000001100000000000110000 = 01111000000111100000000011110011 (num |= num >> 2)

01111000000111100000000011110011 |
00000111100000011110000000001111 = 01111111100111111110000011111111 (num |= num >> 4)

01111111100111111110000011111111 |
00000000011111111001111111100000 = 01111111111111111111111111111111 (num |= num >> 8)

01111111111111111111111111111111 |
00000000000000000111111111111111 = 01111111111111111111111111111111 (num |= num >> 16)

あとは、最終値を 1 ビット右にシフトし、1 を追加して、目的の答えのビットを 1 に設定する最上位キャリーを除いて、すべての 1 を 0 にします。

于 2013-01-25T17:51:37.807 に答える
10

x よりも小さい 2 の最大べき乗が必要であると仮定すると、次の式から得られます。

Ans=pow(2,floor(log(x)/log(2)));
于 2013-01-25T17:52:15.017 に答える
1

n が範囲の最大数の場合 

return int(math.log(n, 2));
于 2013-01-25T18:05:42.777 に答える
0

x86 など、利用可能な場合は、特別な CPU 命令を使用できますBSR。

ループなしで (おそらく、ルックアップ テーブルまたは別の特別な CPU 命令を使用して) 数値をビット元に戻すことができる場合、数値を元に戻し、1 に設定された最下位ビットを見つけ、他のビットをリセットして元に戻すことができます。

unsigned IsolateLeastSignificantOne(unsigned n)
{
  return n & -n;
}

n = BitRevert(IsolateLeastSignificantOne(BitRevert(n)));

ちょっとした裏技やその他の便利な機能については、このドキュメントを参照してください。

于 2013-01-26T04:33:54.067 に答える
0

数値の対数ベースの 2 を取得するか、整数の場合は最上位ビット セットの位置を取得できます (ただし、これにはおそらくループが必要になります)。

しばらく C++ を使っていませんが、C# では次のようになります。

        double val = 129;
        int power = (int)(Math.Log10(val) / Math.Log10(2));

log n (X) = log y (X) / log y (n)というルールを使用

于 2013-01-25T18:01:04.113 に答える
0 
// This only works if i >= 0, and it may overestimate by one power of 2
// if i is slightly less than a large power of 2. Fixing these issues is
// not difficult, so it's left as an exercise.
long largest_power_of_two(long i) {
  int exp;
  frexp(double(i), &exp);
  return long(ldexp(0.5, exp));
}

frexpビットをldexpいじるだけなので、そこには隠れたループさえありません（おそらくマイクロアーキテクチャ層を除く）。

于 2013-01-25T20:18:21.147 に答える