🕍 🤩 💪🏾 Oの2を底とする整数対数（1） ⬆️ 💗 🏕️

多くの場合、任意の整数の2を底とする対数の全体を計算する必要があります。

正面からの決定はループを作ることであり、このループでは、ゼロになるまで常に数値を2で割ります。そのような分割がいくつ発生したか、これが対数の値です。はい、この方法は機能し、生きる権利がありますが、サイクルや複雑な構造なしでどのように実行できるかを示したいと思います。

したがって、次の式を計算します。

y = [l o g_{2} (x)], x - ц е л о е, п о л о ж и т е л ь н о е

$y = [log_2(x)], x - ,$

決定

推論に興味がない人のために、私はすぐに対数を計算するための既製の関数を与えます：

uint32_t getHighBit_32(uint32_t x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x - (x >> 1);
}

uint32_t getBitCount_32(uint32_t x)
{
	x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
	x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
	return (x & 0x0000FFFF) + (x >> 16);
}

uint32_t getLog2_32(uint32_t x)
{
    return getBitCount_32(getHighBit_32(x) - 1);
}

説明

まず、数値xを特定の長さのバイナリ表記に変換してみましょう。

たとえば、長さ= 8ですが、それは問題ではなく、数値の長さは任意です。

ここで、数値からバイナリ表記への変換が何に基づいているかを思い出してください。数を2の累乗の合計として表すこと。次数はビットの位置を決定します。これは1です。例：

45 = 32 + 8 + 4 + 1 = 2^{5} + 2^{3} + 2^{2} + 2^{0}

$45 = 32 + 8 + 4 + 1 = 2^5 + 2^3 + 2^2 + 2^0$ ..。それら。次数5、3、2、0。これは、5、3、2、0番目のビットが1に等しいことを意味します。それらの間の残りのビットはゼロに等しくなります。ビットは右側から始まります。それは明らかになった

45_{10} = 101101_{2}

$45_{10} = 101101_2$

バイナリ表記への変換は指数と密接に関連しており、対数は指数の逆であり、指数に等しいことに注意してください。

2^{y} = x, y = l o g_{2} (x)

$2^y = x, y = log_2(x)$

さらに、2を上げる必要がある指数は、バイナリ表記の1ビットの数です。1ビットの数を見つけると、対数の値の整数部分が2を底とすることがわかります。たとえば、32 = 100000の場合、1ビットは5位なので、対数は5です。

ただし、1ではなく複数ある可能性があるため、対数を見つけるためにどの1ビットを取るかという問題が発生します。答えは、数字の記録の右側から始まる最後の1ビットの数字です。これは、対数の全体を決定する2の累乗であり、残りは対数の一部を構成するためです。

別の例を考えてみましょう-数

45_{10} = 101101_{2}

$45_{10} = 101101_2$ ..。最後の1ビットは5位なので、45の対数の整数部分は5です。実際に

l o g_{2} (45) = 5.4919

$log_2(45)=5.4919$ ..。分数部分を破棄して5を残します

。他の数値でも機能します。

その結果、対数の整数部分は、右から数えて最後の1ビットの数に等しいことがわかりました。質問：最後の1ビットの数を見つける方法は？

このために、G。Warrenの著書「プログラマーのためのアルゴリズムのトリック」で見つけたビット単位の操作に基づく関数があります。

2の累乗に切り捨てます（または数値のバイナリ表記の最後の1ビットを強調表示します）。実際、切り上げることはできますが、対数の値も切り上げられます。
数字のバイナリ表記でシングルビットの数を数える

両方の関数はそこでよく説明されています、そして私はそれらのコードを以前に与えました。

これらの2つの関数を使用して、アルゴリズムを計算するためのアルゴリズムは次のとおりです。

番号の最後の1ビットを選択します。今、その数は100000と書かれています
結果の数から1を引きます。その場合、番号は次のようになります：011111
単位ビット数を数えると、これが対数の整数値になります

例外的な状況

x = 0の場合、対数には例外的な状況があります。理論的には、そのようなアルゴリズムは存在しません（または、制限内では-∞に等しくなります）。ただし、プログラミングでは数学の法則から少し外れているため、関数の入力がゼロの場合でも関数は機能します。この場合、対数の値は32になります（数値が32ビットの場合）。これは、2の最も近い累乗に丸める関数が0を与えるため、ゼロから1を引いて、数値0xFFFFFFFFを取得し、この数値には32単位があるため、対数は32になります。

はい、数学の観点からは、これは正しくありませんが、場合によっては、プログラミングの観点から役立つ場合。

バイナリコードの長さを数える

整数ではなく実数の対数が考慮されることが多いため、このような関数が数学的な対数の計算に使用される可能性はほとんどありません。

ただし、バイナリコードの長さを計算することは、実際にはより一般的なタスクです。

特定の長さのバイナリコードを指定します。これは、たとえば、バイナリツリーのパスである可能性があります。このコードの前に1ビットが書き込まれている場合、整数の対数を取ることにより、補助変数を使用せずにこのコードの長さを計算することができます。

たとえば、コード0001110110を指定します。これは、たとえば32ビットのセルに書き込まれ、このコードの長さを読み取る必要があることがよくあります。これを行うには、コードの前に1ビットを追加します。

10001110110が得られます。これで、このコードの長さを別の場所に個別に保存しなくても、整数の対数によってこのコードの長さを安全に計算できます。

すべてがゼロであるコードの長さを考慮すると、関数は長さ= 32を返しますが、これは正しくない可能性があるため、この状況を予測する必要があります。状況によっては、関数が32を返すと便利な場合もあれば、たとえばゼロを返す場合もあります。

ソース

G.ウォーレン「プログラマーのためのアルゴリズムの秘訣。改訂版。 "、2004

Oの2を底とする整数対数（1）

決定

説明

例外的な状況

バイナリコードの長さを数える

ソース

More articles: