C++で整数log2()を実行するにはどうすればよいですか?

https://stackoverflow.com/questions/994593

13-09-2019
|

質問

C++ 標準ライブラリでは、浮動小数点ログメソッドしか見つかりませんでした。ここで、ログを使用してバイナリツリー内のインデックスのレベルを見つけます ( floor(2log(index)) ).

コード (C++):

int targetlevel = int(log(index)/log(2));

一部のエッジ要素 (値 2^n を持つ要素) では、ログが n.0 ではなく n-1.999999999999 を返すのではないかと心配しています。この懸念は正しいでしょうか？常に正しい答えが返されるようにステートメントを変更するにはどうすればよいですか?

解決

あなたは、代わりにこのメソッドを使用することができます：

int targetlevel = 0;
while (index >>= 1) ++targetlevel;

注：これは、インデックスを変更します。あなたは変わらず、それが必要な場合は、別の一時的なint型を作成します。

コーナーケースは、インデックスが0であるとき、あなたはおそらく別にそれをチェックして、例外をスローまたはインデックス== 0の場合、エラーを返すべきである。

他のヒント

あなたは最近、っぽいx86またはx86-64のプラットフォームを使用している（そしておそらくある）場合は、符号なし整数で最上位セットビットの位置を返しますbsr命令を使用します。それは、これはLOG2とまったく同じであることが判明しました（）。ここで、インラインASMを使用してbsrを呼び出す短い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;
}

高速な整数ログが必要なだけの場合₂ 操作、以下の機能 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 の補数に設定された最上位ビットを見つける) がいくつかあります。ここ. 。速度が重要でない限り、これらを使用することはお勧めしません (私自身は読みやすさを好みます) が、それらの存在は知っておくべきです。

底2対数整数

ここで私は、64ビット符号なし整数のために何をすべきかです。これは、最上位ビットのインデックスに相当するベース2対数の底を計算します。それはlog₂64= 6つのステップで常に実行される展開ループを使用していますので、この方法では、多数のためにののsmokingly高速です。

、= {2³²、2¹⁶、2⁸、2⁴、2²、2¹} = {4294967296
本質的に、何それがないと、シーケンスに離れ徐々に小さく正方形を減算{2 ^（2 ^ k）が0≤K≤5}れます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 }

これは返すこと-1（初期-(n == 0)のためにチェックされるものである）、0の無効な入力を与えられた場合に注意してください。あなたはn == 0でそれを呼び出すことを期待することはありません場合は、初期化のためint i = 0;を代用し、関数へのエントリでassert(n != 0);を追加することができます。

ベース-10整数対数

ベース-10整数対数は同様に使用して計算することができる - なぜならlog₁₀2⁶⁴≅19.2659 ...
テストする最大四角形が1016であると
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 }

これは、上記のコメントで提案されています。 gccの組み込みコマンドを使用します：

static inline int log2i(int x) { assert(x > 0); return sizeof(int) * 8 - __builtin_clz(x) - 1; } static void test_log2i(void) { assert_se(log2i(1) == 0); assert_se(log2i(2) == 1); assert_se(log2i(3) == 1); assert_se(log2i(4) == 2); assert_se(log2i(32) == 5); assert_se(log2i(33) == 5); assert_se(log2i(63) == 5); assert_se(log2i(INT_MAX) == sizeof(int)*8-2); }

私はあなたが使用している式に浮動小数点の精度に問題なかったことがありません（と2から1から数字のクイックチェックを³¹ - 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; }

int targetIndex = floor(log(i + 0.5)/log(2.0));

これは、標準または必ずしもポータブルではありませんが、一般的な作業になります。私はそれがどのように効率的に知りません。

十分な精度の浮動小数点数に整数のインデックスに変換します。表現が正確になり、精度を想定すれば十分である。

指数を抽出し、IEEE浮動小数点数の表現を見て、ベース2対数を見つけるために必要な調整を行います。

このconstexprの機能にすることができますが、C ++ 11を使用している場合：

constexpr std::uint32_t log2(std::uint32_t n) { return (n > 1) ? 1 + log2(n >> 1) : 0; }

上記にも同様の回答があります。この答えは

64ビット数値を扱う

丸めの種類と

テスト/サンプルコードが含まれています

機能：

static int floorLog2(int64_t x) { assert(x > 0); return 63 - __builtin_clzl(x); } static int ceilLog2(int64_t x) { if (x == 1) // On my system __builtin_clzl(0) returns 63. 64 would make more sense // and would be more consistent. According to stackoverflow this result // can get even stranger and you should just avoid __builtin_clzl(0). return 0; else return floorLog2(x-1) + 1; }

テストコード:

for (int i = 1; i < 35; i++) std::cout<<"floorLog2("<<i<<") = "<<floorLog2(i) <<", ceilLog2("<<i<<") = "<<ceilLog2(i)<<std::endl;

この関数は、数値の間隔を表すために必要とされるビット数決定：[0..maxvalue

unsigned binary_depth( unsigned maxvalue ) { int depth=0; while ( maxvalue ) maxvalue>>=1, depth++; return depth; }
floor(log2(x))が2のべき乗である場合、
の結果から1を減算することによって、あなたはlog2(x)の正確の表現であるxを取得します。

の X の の Y の の Y-1 の
0 0 -1
の 1 の 1 の 0 の
の 2 の 2 の 1 の
3 2 1
の 4 の 3 の 2 の
5 3 2
6 3 2
7 3 2
の 8 の 4 の 3 の

どのように深いあなたは、あなたのツリーがするプロジェクトのですか？あなたは、整数値にそれを強制的に数値に言うの範囲... +/- 0.00000001を設定することができます。

私は実際にあなたのLOG2（2の最も近いパワーへのポイントのラウンドを浮動ので）2 ^ n個の値を計算する任意の精度を失うべきではありませんので、あなたが1.99999999のように番号を打つだろうかどうか分からない。

私はここにの
を書いた
この機能
// 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 ; }

これは古い記事ですが、私は私の1行のアルゴリズムを共有します：

unsigned uintlog2(unsigned x) { unsigned l; for(l=0; x>1; x>>=1, l++); return l; }

書き換え トッド・リーマンの答えはより一般的です:

#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; }

カンカンと鳴る -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 が定数の場合、結果はコンパイル時に計算されます。

方法浮動小数点数のワーク（粗、仮数* 2 ^指数）が与えられると、2のべき乗である2 ^ 127に、次いで任意の数までは正確にエラーなしで表される。

これは些細ではなくハック溶液を得ない - 整数として浮動小数点数のビットパターンを解釈し、単に指数を見てください。これは、上記のデビッド・ソーンリーのソリューションです。

float f = 1; for (int i = 0; i < 128; i++) { int x = (*(int*)(&f)>>23) - 127; int l = int(log(f) / log(2)); printf("i = %d, log = %d, f = %f quick = %d\n", i, l, f, x); f *= 2; }
唯一の仮数より少ないビットを有するものを表すことができる -
は、は、任意の整数をfloatとして表すことができることは事実ではありません。 32ビットの浮動小数点数では、それは、23ビットの価値があります。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow