什么是计算(long int) ceiling(log_2(i))的快速方法，其中输入和输出是64位整数？有符号或无符号整数的解决方案是可以接受的。我怀疑最好的方法将是一个类似于找到here的方法，但不是尝试我自己，我想使用已经经过充分测试的东西。一般解决方案适用于所有正值。
例如，2,3,4,5,6,7,8的值为1,2,2,3,3,3,3
编辑：到目前为止，最好的路径似乎是使用任意数量的快速现有bithacks或寄存器方法计算整数/楼层日志基数2（MSB的位置），然后如果输入不是幂的话，则添加一个二。对2的幂的快速按位检查是(n&(n-1))。
编辑2：整数对数和前导零方法的一个好来源是Henry S. Warren在Hacker's Delight中的第5-3和11-4节。这是我发现的最完整的治疗方法。
编辑3：这项技术看起来很有希望：https://stackoverflow.com/a/51351885/365478
该算法已经发布，但是下面的实现非常紧凑，应该优化为无分支代码。
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;
}
如果您有80位或128位浮点数，则转换为该类型，然后读取指数位。此链接具有详细信息（对于最多52位的整数）和其他几种方法：
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogIEEE64Float
另外，请检查ffmpeg源。我知道他们有一个非常快的算法。即使它不能直接扩展到更大的尺寸，你也可以轻松地做像if (x>INT32_MAX) return fastlog2(x>>32)+32; else return fastlog2(x);这样的事情
朴素线性搜索可以是均匀分布的整数的选项，因为它平均需要略小于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 \
)
在编写本文时，我将为您提供x86-64的最快方法，如果你有一个快速的底板，适用于参数<2 ^ 63，如果你关心整个范围，我会给你一个通用技术，然后看下面。
我对其他答案的低质量感到惊讶，因为他们告诉你如何以非常昂贵的方式（使用条件和一切！）将地板变成天花板。
如果你可以快速获得对数的底线，例如，使用__builtin_clzll，那么很容易获得这样的地板：
unsigned long long log2Floor(unsigned long long x) {
return 63 - __builtin_clzll(x);
}
unsigned long long log2Ceiling(unsigned long long x) {
return log2Floor(2*x - 1);
}
这是有效的，因为它将结果加1，除非x恰好是2的幂。
请参阅x86-64汇编程序差异at the compiler explorer以获取另一个天花板实现，如下所示：
auto log2CeilingDumb(unsigned long x) {
return log2Floor(x) + (!!(x & (x - 1)));
}
得到：
log2Floor(unsigned long): # @log2Floor(unsigned long)
bsr rax, rdi
ret
log2CeilingDumb(unsigned long): # @log2CeilingDumb(unsigned long)
bsr rax, rdi
lea rcx, [rdi - 1]
and rcx, rdi
cmp rcx, 1
sbb eax, -1
ret
log2Ceiling(unsigned long): # @log2Ceiling(unsigned long)
lea rax, [rdi + rdi]
add rax, -1
bsr rax, rax
ret
对于整个范围，它在之前的答案中：return log2Floor(x - 1) + 1，这显着较慢，因为它使用x86-64四个指令而不是上面的三个。
我已经对64位“最高位”的几个实现进行了基准测试。最“免费分支”的代码实际上并不是最快的。
这是我的highest-bit.c源文件：
int highest_bit_unrolled(unsigned long long n)
{
if (n & 0xFFFFFFFF00000000) {
if (n & 0xFFFF000000000000) {
if (n & 0xFF00000000000000) {
if (n & 0xF000000000000000) {
if (n & 0xC000000000000000)
return (n & 0x8000000000000000) ? 64 : 63;
else
return (n & 0x2000000000000000) ? 62 : 61;
} else {
if (n & 0x0C00000000000000)
return (n & 0x0800000000000000) ? 60 : 59;
else
return (n & 0x0200000000000000) ? 58 : 57;
}
} else {
if (n & 0x00F0000000000000) {
if (n & 0x00C0000000000000)
return (n & 0x0080000000000000) ? 56 : 55;
else
return (n & 0x0020000000000000) ? 54 : 53;
} else {
if (n & 0x000C000000000000)
return (n & 0x0008000000000000) ? 52 : 51;
else
return (n & 0x0002000000000000) ? 50 : 49;
}
}
} else {
if (n & 0x0000FF0000000000) {
if (n & 0x0000F00000000000) {
if (n & 0x0000C00000000000)
return (n & 0x0000800000000000) ? 48 : 47;
else
return (n & 0x0000200000000000) ? 46 : 45;
} else {
if (n & 0x00000C0000000000)
return (n & 0x0000080000000000) ? 44 : 43;
else
return (n & 0x0000020000000000) ? 42 : 41;
}
} else {
if (n & 0x000000F000000000) {
if (n & 0x000000C000000000)
return (n & 0x0000008000000000) ? 40 : 39;
else
return (n & 0x0000002000000000) ? 38 : 37;
} else {
if (n & 0x0000000C00000000)
return (n & 0x0000000800000000) ? 36 : 35;
else
return (n & 0x0000000200000000) ? 34 : 33;
}
}
}
} else {
if (n & 0x00000000FFFF0000) {
if (n & 0x00000000FF000000) {
if (n & 0x00000000F0000000) {
if (n & 0x00000000C0000000)
return (n & 0x0000000080000000) ? 32 : 31;
else
return (n & 0x0000000020000000) ? 30 : 29;
} else {
if (n & 0x000000000C000000)
return (n & 0x0000000008000000) ? 28 : 27;
else
return (n & 0x0000000002000000) ? 26 : 25;
}
} else {
if (n & 0x0000000000F00000) {
if (n & 0x0000000000C00000)
return (n & 0x0000000000800000) ? 24 : 23;
else
return (n & 0x0000000000200000) ? 22 : 21;
} else {
if (n & 0x00000000000C0000)
return (n & 0x0000000000080000) ? 20 : 19;
else
return (n & 0x0000000000020000) ? 18 : 17;
}
}
} else {
if (n & 0x000000000000FF00) {
if (n & 0x000000000000F000) {
if (n & 0x000000000000C000)
return (n & 0x0000000000008000) ? 16 : 15;
else
return (n & 0x0000000000002000) ? 14 : 13;
} else {
if (n & 0x0000000000000C00)
return (n & 0x0000000000000800) ? 12 : 11;
else
return (n & 0x0000000000000200) ? 10 : 9;
}
} else {
if (n & 0x00000000000000F0) {
if (n & 0x00000000000000C0)
return (n & 0x0000000000000080) ? 8 : 7;
else
return (n & 0x0000000000000020) ? 6 : 5;
} else {
if (n & 0x000000000000000C)
return (n & 0x0000000000000008) ? 4 : 3;
else
return (n & 0x0000000000000002) ? 2 : (n ? 1 : 0);
}
}
}
}
}
int highest_bit_bs(unsigned long long n)
{
const unsigned long long mask[] = {
0x000000007FFFFFFF,
0x000000000000FFFF,
0x00000000000000FF,
0x000000000000000F,
0x0000000000000003,
0x0000000000000001
};
int hi = 64;
int lo = 0;
int i = 0;
if (n == 0)
return 0;
for (i = 0; i < sizeof mask / sizeof mask[0]; i++) {
int mi = lo + (hi - lo) / 2;
if ((n >> mi) != 0)
lo = mi;
else if ((n & (mask[i] << lo)) != 0)
hi = mi;
}
return lo + 1;
}
int highest_bit_shift(unsigned long long n)
{
int i = 0;
for (; n; n >>= 1, i++)
; /* empty */
return i;
}
static int count_ones(unsigned long long d)
{
d = ((d & 0xAAAAAAAAAAAAAAAA) >> 1) + (d & 0x5555555555555555);
d = ((d & 0xCCCCCCCCCCCCCCCC) >> 2) + (d & 0x3333333333333333);
d = ((d & 0xF0F0F0F0F0F0F0F0) >> 4) + (d & 0x0F0F0F0F0F0F0F0F);
d = ((d & 0xFF00FF00FF00FF00) >> 8) + (d & 0x00FF00FF00FF00FF);
d = ((d & 0xFFFF0000FFFF0000) >> 16) + (d & 0x0000FFFF0000FFFF);
d = ((d & 0xFFFFFFFF00000000) >> 32) + (d & 0x00000000FFFFFFFF);
return d;
}
int highest_bit_parallel(unsigned long long n)
{
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
return count_ones(n);
}
int highest_bit_so(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;
}
int highest_bit_so2(unsigned long long value)
{
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;
}
这是highest-bit.h：
int highest_bit_unrolled(unsigned long long n);
int highest_bit_bs(unsigned long long n);
int highest_bit_shift(unsigned long long n);
int highest_bit_parallel(unsigned long long n);
int highest_bit_so(unsigned long long n);
int highest_bit_so2(unsigned long long n);
和主程序（抱歉所有的复制和粘贴）：
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include "highest-bit.h"
double timedelta(clock_t start, clock_t end)
{
return (end - start)*1.0/CLOCKS_PER_SEC;
}
int main(int argc, char **argv)
{
int i;
volatile unsigned long long v;
clock_t start, end;
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_unrolled(v);
}
end = clock();
printf("highest_bit_unrolled = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_parallel(v);
}
end = clock();
printf("highest_bit_parallel = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_bs(v);
}
end = clock();
printf("highest_bit_bs = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_shift(v);
}
end = clock();
printf("highest_bit_shift = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_so(v);
}
end = clock();
printf("highest_bit_so = %6.3fs\n", timedelta(start, end));
start = clock();
for (i = 0; i < 10000000; i++) {
for (v = 0x8000000000000000; v; v >>= 1)
highest_bit_so2(v);
}
end = clock();
printf("highest_bit_so2 = %6.3fs\n", timedelta(start, end));
return 0;
}
我尝试了各种新旧英特尔x86机箱。
highest_bit_unrolled（展开的二进制搜索）始终明显快于highest_bit_parallel（无分支位操作）。这比highest_bit_bs（二进制搜索循环）快，而且反过来比highest_bit_shift（天真移位和计数循环）快。
highest_bit_unrolled也比公认的SO答案（highest_bit_so）更快，并且在另一个答案（highest_bit_so2）中给出了一个。
基准测试通过覆盖连续位的一位掩码循环。这是为了试图在展开的二进制搜索中击败分支预测，这是现实的：在现实世界的程序中，输入情况不太可能表现出位位置的位置。
以下是旧Intel(R) Core(TM)2 Duo CPU E4500 @ 2.20GHz的结果：
$ ./highest-bit
highest_bit_unrolled = 6.090s
highest_bit_parallel = 9.260s
highest_bit_bs = 19.910s
highest_bit_shift = 21.130s
highest_bit_so = 8.230s
highest_bit_so2 = 6.960s
在较新的型号Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz：
highest_bit_unrolled = 1.555s
highest_bit_parallel = 3.420s
highest_bit_bs = 6.486s
highest_bit_shift = 9.505s
highest_bit_so = 4.127s
highest_bit_so2 = 1.645s
在较新的硬件上，highest_bit_so2在更新的硬件上更接近highest_bit_unrolled。订单不太一样;现在highest_bit_so真的落后了，并且比highest_bit_parallel慢。
最快的一个，highest_bit_unrolled包含分支最多的代码。每个单独的返回值由一组不同的条件和它自己的专用代码达到。
“避免所有分支”的直觉（由于对分支错误预测的担忧）并不总是正确的。现代（甚至不那么现代）处理器包含相当大的狡猾，以免受到分支的阻碍。
附： highest_bit_unrolled是在December 2011的TXR语言中引入的（错误，自调试以来）。
最近，我开始怀疑一些没有分支的更好，更紧凑的代码是否会更快。
我对结果感到有些惊讶。
可以说，代码应该是针对GNU C的#ifdef-ing并使用一些编译器原语，但就可移植性而言，该版本仍然存在。
下面的代码更简单，只要输入x> = 1就可以工作。输入clog2（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;
}
如果你可以限制自己使用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的高32位，（（long *）＆x）[1]，如果需要，检查低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;
}
使用@egosys提到的gcc builtins，你可以构建一些有用的宏。对于快速粗糙的楼层（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))
后者可以使用更多的gcc特性进一步优化，以避免对内置的双重调用，但我不确定你在这里需要它。
下面的代码片段是一种安全且可移植的方法，用于扩展plain-C方法，例如@ dgobbi，在使用支持编译器（Clang）编译时使用编译器内在函数。将其置于方法的顶部将导致该方法在可用时使用内置函数。当内置不可用时，该方法将回退到标准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
我所知道的最快的方法是使用一个向下舍入的快速log2，结合前后输入值的无条件调整来处理舍入情况，如下面所示的lg_down()。
/* base-2 logarithm, rounding down */
static inline uint64_t lg_down(uint64_t x) {
return 63U - __builtin_clzl(x);
}
/* base-2 logarithm, rounding up */
static inline uint64_t lg_up(uint64_t x) {
return lg_down(x - 1) + 1;
}
基本上向舍入结果添加1对于除了2的精确幂之外的所有值已经是正确的（因为在这种情况下，floor和ceil方法应该返回相同的答案），因此从输入值中减去1来处理就足够了那种情况（它不会改变其他情况的答案）并在结果中添加一个。
这通常比通过明确检查2的精确幂来调整值的方法稍快（例如，添加!!(x & (x - 1))项）。它避免了任何比较和条件操作或分支，更可能只是在内联时，更适合矢量化等。
这依赖于大多数CPU使用clang / icc / gcc内置__builtin_clzl提供的“计数前导位”功能，但其他平台提供了类似的功能（例如，Visual Studio中的BitScanReverse内置）。
不幸的是，这很多人为log(1)返回了错误的答案，因为这会导致__builtin_clzl(0)，这是基于gcc文档的未定义行为。当然，一般的“计数前导零”函数在零处完全定义了行为，但是gcc内置是以这种方式定义的，因为在x86上的BMI ISA扩展之前，它本来会使用本身具有未定义行为的bsr instruction。
如果你知道你有直接使用lzcnt内在的lzcnt指令，你可以解决这个问题。除x86之外的大多数平台从未首先遇到过bsr错误，并且可能还提供了访问“计数前导零”指令的方法（如果有的话）。
真正最快的解决方案：
63个条目的二叉搜索树。这些是从0到63的2的幂。用于创建树的一次性生成函数。叶子代表权力的对数基数2（基本上是数字1-63）。
要查找答案，请将数字输入树中，然后导航到大于项目的叶节点。如果叶节点完全相等，则结果为叶值。否则，结果是叶值+ 1。
复杂性固定为O（6）。
查找具有整数输出的整数（64位或任何其他位）的日志基数2等同于查找设置的最高有效位。为什么？因为日志库2是您可以将数字除以2到达1的次数。
找到所设置的MSB的一种方法是简单地每次向右移位1，直到你有0.另一种更有效的方法是通过位掩码进行某种二进制搜索。
通过检查是否设置除MSB之外的任何其他位，可以容易地计算出ceil部分。