如何做一个整数log2（）在C + +？
在C ++标准库中，我只find一个浮点日志方法。 现在我用log来查找二叉树（ floor(2log(index)) ）中索引的级别。
代码（C ++）：
int targetlevel = int(log(index)/log(2));
恐怕对于一些边缘元素（值为2 ^ n的元素）日志将返回n-1.999999999999而不是n.0。 这种恐惧是否正确？ 我怎样才能修改我的陈述，以便它总是会返回正确的答案？
你可以使用这个方法：
int targetlevel = 0; while (index >>= 1) ++targetlevel;
注意：这将修改索引。 如果您不需要更改，请创build另一个临时int。
转angular的情况是当索引是0.你可能应该单独检查它，并抛出一个exception或返回一个错误，如果索引== 0。
如果您使用的是x86或x86-64平台，那么可以使用bsr指令，它将返回无符号整数中最高位的位置。 事实certificate，这和log2（）完全一样。 这是一个简短的C或C ++函数，使用内联ASM调用bsr ：
#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; }
如果你只是想要一个快速整数日志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; }
上面的代码也有一个小的testing工具，所以你可以检查行为：
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作为input值0作为未定义结果的指示，所以这是你应该检查的东西（没有有效的无符号整数将有一个高对数）。
顺便说一句，这里有一些非常快速的攻击（find2的补码数中设置的最高位）。 我不会build议使用它们，除非速度是本质的（我更喜欢自己的可读性），但是您应该意识到它们的存在。
基2整数对数
这是我为64位无符号整数做的。 这将计算基数为2的对数的底数，它等于最高有效位的指数。 这种方法对于大数量来说是非常快速的 ，因为它使用了一个以log264 = 6步执行的展开循环。
实质上，它所做的是逐渐减去序列中的较小的平方{0≤k≤5：2 ^（2 ^ k）} = {2,2,2,2，2,2,4,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 }
请注意，如果给定无效input0（这是初始-(n == 0)正在检查的内容），则返回-1。 如果你不希望用n == 0调用它，你可以用int i = 0;来代替int i = 0; 为初始化和添加assert(n != 0); 在进入function。
基数10整数对数
基10的整数对数可以用类似的方法计算 – 最大的平方testing为10 10，因为log 10 2 4 4 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 }
这已经在上面的评论中提出。 使用gcc builtins：
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); }
我从来没有在你正在使用的公式上的浮点精度的问题（并快速检查从1到2的数字31 – 1没有发现错误），但如果你担心，你可以使用这个函数相反，它返回相同的结果，在我的testing中快了大约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浮点数的表示forms，提取指数，并进行必要的调整以find基本的2日志。
该函数决定了需要多less位来表示数字区间：[0..maxvalue]。
unsigned binary_depth( unsigned maxvalue ) { int depth=0; while ( maxvalue ) maxvalue>>=1, depth++; return depth; }
通过从结果中减去1，得到floor(log2(x)) ，当x是2的幂时，它是log2(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
如果你使用的是C ++ 11，你可以把它作为一个constexpr函数：
constexpr std::uint32_t log2(std::uint32_t n) { return (n > 1) ? 1 + log2(n >> 1) : 0; }
你的树有多深？ 你可以设置一个范围说… +/- 0.00000001的数字强制它为一个整数值。
我实际上并不确定你会得到一个像1.99999999这样的数字，因为在计算2 ^ n值时（因为浮点舍入到2的最近次幂），你的log2不应该失去任何准确性。
这个function我在这里写的
// 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 ; }
这是一个旧post，但我分享我的一行algorithm：
unsigned uintlog2(unsigned x) { unsigned l; for(l=0; x>1; x>>=1, l++); return l; }
上面有类似的答案。 这个答案
- 适用于64位数字
- 让您select舍入types
- 包含testing/示例代码
function：
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; }
testing代码：
for (int i = 1; i < 35; i++) std::cout<<"floorLog2("<<i<<") = "<<floorLog2(i) <<", ceilLog2("<<i<<") = "<<ceilLog2(i)<<std::endl;
