C++ 標準ライブラリでは、浮動小数点ログ メソッドしか見つかりませんでした。ここで、ログを使用して、バイナリ ツリー ( ) のインデックスのレベルを見つけますfloor(2log(index))。
コード (C++):
int targetlevel = int(log(index)/log(2));
残念ながら、一部のエッジ要素 (値が 2^n の要素) では、ログは n.0 ではなく n-1.999999999999 を返します。この恐怖は正しいですか？常に正しい答えを返すようにステートメントを変更するにはどうすればよいですか?
最近の x86 または x86-64 プラットフォームを使用している場合 (そしておそらくそうである場合)、bsr設定された最上位ビットの位置を符号なし整数で返す命令を使用します。これは log2() とまったく同じであることがわかります。bsrインライン ASM を使用して呼び出す短い C または C++ 関数を次に示します。
#include <stdint.h>
static inline uint32_t log2(const uint32_t x) {
uint32_t y;
asm ( "\tbsr %1, %0\n"
: "=r"(y)
: "r" (x)
);
return y;
}
代わりに次の方法を使用できます。
int targetlevel = 0;
while (index >>= 1) ++targetlevel;
注: これにより、インデックスが変更されます。変更しない必要がある場合は、別の一時的な int を作成します。
コーナー ケースは、インデックスが 0 の場合です。インデックス == 0 の場合は、個別にチェックして例外をスローするか、エラーを返す必要があります。
高速な整数 log 2操作だけが必要な場合は、次の関数mylog2()を使用すると、浮動小数点の精度を気にする必要がなくなります。
#include <limits.h>
static unsigned int mylog2 (unsigned int val) {
if (val == 0) return UINT_MAX;
if (val == 1) return 0;
unsigned int ret = 0;
while (val > 1) {
val >>= 1;
ret++;
}
return ret;
}
#include <stdio.h>
int main (void) {
for (unsigned int i = 0; i < 20; i++)
printf ("%u -> %u\n", i, mylog2(i));
putchar ('\n');
for (unsigned int i = 0; i < 10; i++)
printf ("%u -> %u\n", i+UINT_MAX-9, mylog2(i+UINT_MAX-9));
return 0;
}
上記のコードには小さなテスト ハーネスも含まれているため、動作を確認できます。
0 -> 4294967295
1 -> 0
2 -> 1
3 -> 1
4 -> 2
5 -> 2
6 -> 2
7 -> 2
8 -> 3
9 -> 3
10 -> 3
11 -> 3
12 -> 3
13 -> 3
14 -> 3
15 -> 3
16 -> 4
17 -> 4
18 -> 4
19 -> 4
4294967286 -> 31
4294967287 -> 31
4294967288 -> 31
4294967289 -> 31
4294967290 -> 31
4294967291 -> 31
4294967292 -> 31
4294967293 -> 31
4294967294 -> 31
4294967295 -> 31
UINT_MAX未定義の結果を示すものとして 0 の入力値が返されるため、これを確認する必要があります (有効な符号なし整数の対数がこれほど大きくなることはありません)。
ちなみに、これを正確に行うための非常に高速なハックがいくつかあります (2 の補数で設定された最高ビットを見つける)ここから入手できます。速度が本質的なものでない限り、それらを使用することはお勧めしませんが（私自身は読みやすさを好みます）、それらが存在することを認識しておく必要があります。
これは、64 ビットの符号なし整数に対して行うことです。これは、2 を底とする対数の下限を計算します。これは、最上位ビットのインデックスに相当します。この方法は、常に log264 = 6 ステップで実行される展開されたループを使用するため、大きな数に対して非常に高速です。
基本的に、{ 0 ≤ k ≤ 5: 2^(2^k) } = { 2³², 2¹⁶, 2⁸, 2⁴, 2², 2¹ } = { 4294967296, 65536, 256 , 16, 4, 2, 1 } となり、減算された値の指数 k を合計します。
int uint64_log2(uint64_t n)
{
#define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }
int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;
#undef S
}
0 の無効な入力が与えられた場合、これは –1 を返すことに注意してください (これはイニシャル-(n == 0)がチェックしているものです)。で呼び出すことをまったく期待しない場合は、初期化子のn == 0代わりにat entry を関数にint i = 0;追加できます。assert(n != 0);
基数 10 の整数対数は、同様に計算できます — log₁₀2⁶⁴ ≅ 19.2659...
int uint64_log10(uint64_t n)
{
#define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); }
int i = -(n == 0);
S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10);
return i;
#undef S
}
除算は常に定数によるものであるため、優れたコンパイラはここで整数除算演算を乗算命令に最適化することに注意してください。(これは、整数除算命令は、乗算命令と比較して、最新の最速の CPU でも依然として非常に遅いため、重要です。)
C++11 を使用している場合は、これを constexpr 関数にすることができます。
constexpr std::uint32_t log2(std::uint32_t n) noexcept
{
return (n > 1) ? 1 + log2(n >> 1) : 0;
}
あなたが使用している数式の浮動小数点の精度に問題はありませんでした (そして、1 から 2 31 - 1 までの数を簡単にチェックしたところ、エラーは見つかりませんでした)、心配な場合は、この関数を使用できます代わりに、同じ結果を返し、私のテストでは約 66% 高速です。
int HighestBit(int i){
if(i == 0)
return -1;
int bit = 31;
if((i & 0xFFFFFF00) == 0){
i <<= 24;
bit = 7;
}else if((i & 0xFFFF0000) == 0){
i <<= 16;
bit = 15;
}else if((i & 0xFF000000) == 0){
i <<= 8;
bit = 23;
}
if((i & 0xF0000000) == 0){
i <<= 4;
bit -= 4;
}
while((i & 0x80000000) == 0){
i <<= 1;
bit--;
}
return bit;
}
これは標準ではなく、必ずしも移植可能ではありませんが、一般的には機能します。どれだけ効率がいいのかわからない。
整数インデックスを十分な精度の浮動小数点数に変換します。精度が十分であると仮定すると、表現は正確になります。
IEEE 浮動小数点数の表現を検索し、指数を抽出し、基数 2 の対数を見つけるために必要な調整を行います。
この関数は、数値間隔 [0..maxvalue] を表すために必要なビット数を決定します。
unsigned binary_depth( unsigned maxvalue )
{
int depth=0;
while ( maxvalue ) maxvalue>>=1, depth++;
return depth;
}
結果から 1 を引くと、 が 2 のべき乗であることをfloor(log2(x))正確に表すlog2(x)が得られます。x
xyy-1
00-1
110
221
321
432
532
632
732
843
私がここに書いたこの関数
// The 'i' is for int, there is a log2 for double in stdclib
inline unsigned int log2i( unsigned int x )
{
unsigned int log2Val = 0 ;
// Count push off bits to right until 0
// 101 => 10 => 1 => 0
// which means hibit was 3rd bit, its value is 2^3
while( x>>=1 ) log2Val++; // div by 2 until find log2. log_2(63)=5.97, so
// take that as 5, (this is a traditional integer function!)
// eg x=63 (111111), log2Val=5 (last one isn't counted by the while loop)
return log2Val ;
}
ツリーの深さはどのくらいだと思いますか? たとえば... +/- 0.00000001 の範囲を数値に設定して、整数値に強制することができます。
2^n の値を計算するときに log2 の精度が失われないため (浮動小数点は最も近い 2 の累乗に丸められるため)、実際には 1.99999999 のような数値に到達するかどうかはわかりません。
Todd Lehmanの回答をより一般的なものに書き換えます。
#include <climits>
template<typename N>
constexpr N ilog2(N n) {
N i = 0;
for (N k = sizeof(N) * CHAR_BIT; 0 < (k /= 2);) {
if (n >= static_cast<N>(1) << k) { i += k; n >>= k; }
}
return i;
}
Clang で-O3ループを展開します。
0000000100000f50 pushq %rbp
0000000100000f51 movq %rsp, %rbp
0000000100000f54 xorl %eax, %eax
0000000100000f56 cmpl $0xffff, %edi
0000000100000f5c setg %al
0000000100000f5f shll $0x4, %eax
0000000100000f62 movl %eax, %ecx
0000000100000f64 sarl %cl, %edi
0000000100000f66 xorl %edx, %edx
0000000100000f68 cmpl $0xff, %edi
0000000100000f6e setg %dl
0000000100000f71 leal (,%rdx,8), %ecx
0000000100000f78 sarl %cl, %edi
0000000100000f7a leal (%rax,%rdx,8), %eax
0000000100000f7d xorl %edx, %edx
0000000100000f7f cmpl $0xf, %edi
0000000100000f82 setg %dl
0000000100000f85 leal (,%rdx,4), %ecx
0000000100000f8c sarl %cl, %edi
0000000100000f8e leal (%rax,%rdx,4), %eax
0000000100000f91 xorl %edx, %edx
0000000100000f93 cmpl $0x3, %edi
0000000100000f96 setg %dl
0000000100000f99 leal (%rdx,%rdx), %ecx
0000000100000f9c sarl %cl, %edi
0000000100000f9e leal (%rax,%rdx,2), %ecx
0000000100000fa1 xorl %eax, %eax
0000000100000fa3 cmpl $0x1, %edi
0000000100000fa6 setg %al
0000000100000fa9 orl %ecx, %eax
0000000100000fab popq %rbp
nが定数の場合、結果はコンパイル時に計算されます。