计算快速日志库2天花板
什么是计算(long int) ceiling(log_2(i))的快速方法，input和输出是64位整数？ 有符号或无符号整数的解决scheme是可以接受的。 我怀疑最好的方法将是一个类似于这里发现的有点扭曲的方法，而不是尝试我自己的，我想使用一些已经testing好的东西。 一般的解决scheme将适用于所有正面的价值。
例如，2,3,4,5,6,7,8的值是1,2,2,3,3,3,3
编辑：到目前为止，最好的路线似乎是使用任何数量的快速存在的bithacks或注册方法计算整数/楼层日志基数2（MSB的位置），然后添加一个如果input不是功率二。 (n&(n-1))幂的快速按位检查。
编辑2：整数对数和前导零方法的一个很好的来源是Henry S. Warren在Hacker's Delight中的5-3和11-4节。 这是我发现的最完整的治疗方法。
这个algorithm已经发布了，但是下面的实现很紧凑，应该优化成无分支代码。
int ceil_log2(unsigned long long x) { static const unsigned long long t[6] = { 0xFFFFFFFF00000000ull, 0x00000000FFFF0000ull, 0x000000000000FF00ull, 0x00000000000000F0ull, 0x000000000000000Cull, 0x0000000000000002ull }; int y = (((x & (x - 1)) == 0) ? 0 : 1); int j = 32; int i; for (i = 0; i < 6; i++) { int k = (((x & t[i]) == 0) ? 0 : j); y += k; x >>= k; j >>= 1; } return y; } #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { printf("%d\n", ceil_log2(atol(argv[1]))); return 0; }
如果你可以限制自己的gcc，有一组内置函数返回前导零位的数目，可以用来做一些你想做的工作：
int __builtin_clz (unsigned int x) int __builtin_clzl (unsigned long) int __builtin_clzll (unsigned long long)
如果你在Windows上编译64位处理器，我认为这应该工作。 _BitScanReverse64是一个内在函数。
#include <intrin.h> __int64 log2ceil( __int64 x ) { unsigned long index; if ( !_BitScanReverse64( &index, x ) ) return -1LL; //dummy return value for x==0 // add 1 if x is NOT a power of 2 (to do the ceil) return index + (x&(x-1)?1:0); }
对于32位，可以仿真_BitScanReverse64，对_BitScanReverse进行1或2次调用。 检查x（（long *）＆x）[1]的高32位，如果需要的话检查低32位，（（long *）＆x）[0]。
#include "stdafx.h" #include "assert.h" int getpos(unsigned __int64 value) { if (!value) { return -1; // no bits set } int pos = 0; if (value & (value - 1ULL)) { pos = 1; } if (value & 0xFFFFFFFF00000000ULL) { pos += 32; value = value >> 32; } if (value & 0x00000000FFFF0000ULL) { pos += 16; value = value >> 16; } if (value & 0x000000000000FF00ULL) { pos += 8; value = value >> 8; } if (value & 0x00000000000000F0ULL) { pos += 4; value = value >> 4; } if (value & 0x000000000000000CULL) { pos += 2; value = value >> 2; } if (value & 0x0000000000000002ULL) { pos += 1; value = value >> 1; } return pos; } int _tmain(int argc, _TCHAR* argv[]) { assert(getpos(0ULL) == -1); // None bits set, return -1. assert(getpos(1ULL) == 0); assert(getpos(2ULL) == 1); assert(getpos(3ULL) == 2); assert(getpos(4ULL) == 2); for (int k = 0; k < 64; ++k) { int pos = getpos(1ULL << k); assert(pos == k); } for (int k = 0; k < 64; ++k) { int pos = getpos( (1ULL << k) - 1); assert(pos == (k < 2 ? k - 1 : k) ); } for (int k = 0; k < 64; ++k) { int pos = getpos( (1ULL << k) | 1); assert(pos == (k < 1 ? k : k + 1) ); } for (int k = 0; k < 64; ++k) { int pos = getpos( (1ULL << k) + 1); assert(pos == k + 1); } return 0; }
真正的最快解决scheme：
一个63个条目的二叉search树。 这些是从0到63的2的幂。一次性生成树的function。 叶子代表权力的日志基础2（基本上，数字1-63）。
为了find答案，您将一个数字input到树中，然后导航到大于该项的叶节点。 如果叶子节点完全相等，则结果是叶子值。 否则，结果是叶子值+ 1。
复杂性固定在O（6）。
使用@egosys提到的gcc内置函数可以构build一些有用的macros。 对于快速粗略的楼层（log2（x））计算，您可以使用：
#define FAST_LOG2(x) (sizeof(unsigned long)*8 - 1 - __builtin_clzl((unsigned long)(x)))
对于类似的ceil（log2（x）），使用：
#define FAST_LOG2_UP(x) (((x) - (1 << FAST_LOG2(x))) ? FAST_LOG2(x) + 1 : FAST_LOG2(x))
后者可以进一步优化使用更多的海湾合作委员会的特点，以避免内部的双重打电话，但我不知道你需要在这里。
下面的代码片段是一种安全且便携的方式，用于在使用支持编译器（Clang）进行编译时使用编译器内在函数来扩展plain-C方法（如@ dgobbi's）。 将其置于方法的顶部将导致该方法在可用时使用内置函数。 当内build不可用时，该方法将返回到标准的C代码。
#ifndef __has_builtin #define __has_builtin(x) 0 #endif #if __has_builtin(__builtin_clzll) //use compiler if possible return ((sizeof(unsigned long long) * 8 - 1) - __builtin_clzll(x)) + (!!(x & (x - 1))); #endif
查找带有整数输出的整数（64位或其他位）的日志库2相当于查找设置的最高有效位。 为什么？ 因为日志库2是多less次，可以将数字除以2来达到1。
find设置的MSB的一种方法是每次向右移位1，直到您有0为止。另一个更有效的方法是通过位掩码进行某种二进制search。
通过检查是否设置了除MSB以外的任何其他位，可以很容易地确定单元部分。
如果有80位或128位浮点数，则转换为该types，然后读取指数位。 这个链接有详细的信息（对于整数高达52位）和其他几种方法：
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogIEEE64Float
另外，请检查ffmpeg源码。 我知道他们有一个非常快的algorithm。 即使它不能直接扩展到更大的尺寸，你可以很容易地做一些事情，如if (x>INT32_MAX) return fastlog2(x>>32)+32; else return fastlog2(x); if (x>INT32_MAX) return fastlog2(x>>32)+32; else return fastlog2(x);
简单的线性search可能是均匀分布整数的一个选项，因为平均需要略less于2个比较（对于任何整数大小）。
/* between 1 and 64 comparisons, ~2 on average */ #define u64_size(c) ( \ 0x8000000000000000 < (c) ? 64 \ : 0x4000000000000000 < (c) ? 63 \ : 0x2000000000000000 < (c) ? 62 \ : 0x1000000000000000 < (c) ? 61 \ ... : 0x0000000000000002 < (c) ? 2 \ : 0x0000000000000001 < (c) ? 1 \ : 0 \ )
下面的代码更简单，只要inputx> = 1，就会工作。inputclog2（0）将得到一个未定义的答案（这是有道理的，因为log（0）是无穷大的…）您可以添加错误检查x == 0）如果你想要：
unsigned int clog2 (unsigned int x) { unsigned int result = 0; --x; while (x > 0) { ++result; x >>= 1; } return result; }
顺便说一下，log2的底层代码是类似的:(再次假设x> = 1）
unsigned int flog2 (unsigned int x) { unsigned int result = 0; while (x > 1) { ++result; x >>= 1; } return result; }
