blocks|key|1494077|text|查找具有整数输出的整数(64位或任何其他位)的以2为底的对数等同于查找设置的最高有效位。为什么？因为以2为底的对数是你可以用2除以2得到1的次数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1494078|找到已设置的MSB的一种方法是每次向右移位1，直到得到0。另一种更有效的方法是通过位掩码进行某种二进制搜索。|1494079|通过检查是否设置了除MSB之外的任何其他位，很容易计算出ceil部分。|1494080|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

Finding the log base 2 of an integer (64-bit or any other bit) with integer output is equivalent to finding the most significant bit that is set. Why? Because log base 2 is how many times you can divide the number by 2 to reach 1. 

One way to find the MSB that's set is to simply bitshift to the right by 1 each time until you have 0. Another more efficient way is to do some kind of binary search via bitmasks.

The ceil part is easily worked out by checking if any other bits are set other than the MSB.

blocks|key|2464625|text|如果您可以将自己限制为gcc，那么有一组内置函数可以返回前导零位的数量，并且可以用来做一些工作来做您想做的事情：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2464626|int+__builtin_clz+(unsigned+int+x)
int+__builtin_clzl+(unsigned+long)
int+__builtin_clzll+(unsigned+long+long)|code-block|syntax|javascript|2464627|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

If you can limit yourself to gcc, there are a set of builtin functions which return the number of leading zero bits and can be used to do what you want with a little work:

<pre><code>int __builtin_clz (unsigned int x)
int __builtin_clzl (unsigned long)
int __builtin_clzll (unsigned long long)
</code></pre>

blocks|key|3872807|text|如果您有80位或128位浮点数可用，则转换为该类型，然后读出指数位。此链接包含详细信息(最多52位整数)和其他几种方法：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3872808|http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogIEEE64Float|offset|length|3872809|另外，检查ffmpeg源代码。我知道他们有一个非常快的算法。即使它不能直接扩展到更大的尺寸，您也可以轻松地执行if+(x>INT32_MAX)+return+fastlog2(x>>32)%2B32;+else+return+fastlog2(x);之类的操作|style|CODE|3872810|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|21|0|0|1J|1W|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@$D|S|E|T|1|U]]|A|$]]|$1|F|3|G|5|6|7|V|8|@$D|W|E|X|H|I]]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]]|K|$L|$5|M|N|O|A|$P|C]]]]

If you have 80-bit or 128-bit floats available, cast to that type and then read off the exponent bits. This link has details (for integers up to 52 bits) and several other methods:

<a href="http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogIEEE64Float" rel="nofollow noreferrer">http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogIEEE64Float</a>

Also, check the ffmpeg source. I know they have a very fast algorithm. Even if it's not directly extensible to larger sizes, you can easily do something like <code>if (x&gt;INT32_MAX) return fastlog2(x&gt;&gt;32)+32; else return fastlog2(x);</code>

blocks|key|3872855|text|如果你是在Windows的64位处理器上编译，我认为这应该可以工作。_BitScanReverse64是一个内在函数。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3872856|#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+%2B+(x&(x-1)?1:0);
}|code-block|syntax|javascript|3872857|对于32位，您可以通过1到2次调用_BitScanReverse来模拟_BitScanReverse64。检查x的高32位，((long*)&x)1，如果需要，然后检查低32位，((long*)&x)。|3872858|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

If you're compiling for 64-bit processors on Windows, I think this should work. _BitScanReverse64 is an intrinsic function.

<pre><code>#include &lt;intrin.h&gt;
__int64 log2ceil( __int64 x )
{
 unsigned long index;
 if ( !_BitScanReverse64( &amp;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&amp;(x-1)?1:0);
}
</code></pre>

For 32-bit, you can emulate _BitScanReverse64, with 1 or 2 calls to _BitScanReverse.
Check the upper 32-bits of x, ((long*)&amp;x)[1], then the lower 32-bits if needed, ((long*)&amp;x)[0].

blocks|key|751078|text|真正最快的解决方案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|751079|包含63个条目的二进制搜索树。这些是从0到63的2的幂。创建树的一次性生成函数。叶子表示幂的以2为底的对数(基本上是数字1-63)。|751080|要找到答案，您需要向树中输入一个数字，并导航到大于该项目的叶节点。如果叶节点完全相等，则result为叶值。否则，结果为叶值%2B+1。|751081|复杂度固定在O(6)。|751082|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

The true fastest solution:

A binary search tree of 63 entries. These are the powers of 2 from 0 to 63. One-time generation function to create the tree. The leafs represent the log base 2 of the powers (basically, the numbers 1-63).

To find the answer, you feed a number into the tree, and navigate to the leaf node greater than the item. If the leaf node is exactly equal, result is the leaf value. Otherwise, result is the leaf value + 1.

Complexity is fixed at O(6).

blocks|key|2464821|text|#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+%2B=+32;
++++++value+=+value+>>+32;
++++}
++++if+(value+&+0x00000000FFFF0000ULL)
++++{
++++++pos+%2B=+16;
++++++value+=+value+>>+16;
++++}
++++if+(value+&+0x000000000000FF00ULL)
++++{
++++++pos+%2B=+8;
++++++value+=+value+>>+8;
++++}
++++if+(value+&+0x00000000000000F0ULL)
++++{
++++++pos+%2B=+4;
++++++value+=+value+>>+4;
++++}
++++if+(value+&+0x000000000000000CULL)
++++{
++++++pos+%2B=+2;
++++++value+=+value+>>+2;
++++}
++++if+(value+&+0x0000000000000002ULL)
++++{
++++++pos+%2B=+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;+%2B%2Bk)
++++{
++++++++int+pos+=+getpos(1ULL+<<+k);
++++++++assert(pos+==+k);
++++}
++++for+(int+k+=+0;+k+<+64;+%2B%2Bk)
++++{
++++++++int+pos+=+getpos(+(1ULL+<<+k)+-+1);
++++++++assert(pos+==+(k+<+2+?+k+-+1+:+k)+);
++++}
++++for+(int+k+=+0;+k+<+64;+%2B%2Bk)
++++{
++++++++int+pos+=+getpos(+(1ULL+<<+k)+%7C+1);
++++++++assert(pos+==+(k+<+1+?+k+:+k+%2B+1)+);
++++}
++++for+(int+k+=+0;+k+<+64;+%2B%2Bk)
++++{
++++++++int+pos+=+getpos(+(1ULL+<<+k)+%2B+1);
++++++++assert(pos+==+k+%2B+1);
++++}
++++return+0;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|2464822|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>#include "stdafx.h"
#include "assert.h"

int getpos(unsigned __int64 value)
{
 if (!value)
 {
 return -1; // no bits set
 }
 int pos = 0;
 if (value &amp; (value - 1ULL))
 {
 pos = 1;
 }
 if (value &amp; 0xFFFFFFFF00000000ULL)
 {
 pos += 32;
 value = value &gt;&gt; 32;
 }
 if (value &amp; 0x00000000FFFF0000ULL)
 {
 pos += 16;
 value = value &gt;&gt; 16;
 }
 if (value &amp; 0x000000000000FF00ULL)
 {
 pos += 8;
 value = value &gt;&gt; 8;
 }
 if (value &amp; 0x00000000000000F0ULL)
 {
 pos += 4;
 value = value &gt;&gt; 4;
 }
 if (value &amp; 0x000000000000000CULL)
 {
 pos += 2;
 value = value &gt;&gt; 2;
 }
 if (value &amp; 0x0000000000000002ULL)
 {
 pos += 1;
 value = value &gt;&gt; 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 &lt; 64; ++k)
 {
 int pos = getpos(1ULL &lt;&lt; k);
 assert(pos == k);
 }
 for (int k = 0; k &lt; 64; ++k)
 {
 int pos = getpos( (1ULL &lt;&lt; k) - 1);
 assert(pos == (k &lt; 2 ? k - 1 : k) );
 }
 for (int k = 0; k &lt; 64; ++k)
 {
 int pos = getpos( (1ULL &lt;&lt; k) | 1);
 assert(pos == (k &lt; 1 ? k : k + 1) );
 }
 for (int k = 0; k &lt; 64; ++k)
 {
 int pos = getpos( (1ULL &lt;&lt; k) + 1);
 assert(pos == k + 1);
 }
 return 0;
}
</code></pre>

blocks|key|3872982|text|使用@egosys提到的gcc内置，您可以构建一些有用的宏。对于快速而粗略的地板(log2(X))计算，您可以使用：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3872983|#define+FAST_LOG2(x)+(sizeof(unsigned+long)*8+-+1+-+__builtin_clzl((unsigned+long)(x)))|code-block|syntax|javascript|3872984|对于类似的ceil(log2(x))，使用：|3872985|#define+FAST_LOG2_UP(x)+(((x)+-+(1+<<+FAST_LOG2(x)))+?+FAST_LOG2(x)+%2B+1+:+FAST_LOG2(x))|3872986|后者可以使用更多的gcc特性来进一步优化，以避免对内置函数的双重调用，但我不确定这里是否需要它。|3872987|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|S|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

Using the gcc builtins mentioned by @egosys you can build some useful macros.
For a quick and rough floor(log2(x)) calculation you can use:

<pre><code>#define FAST_LOG2(x) (sizeof(unsigned long)*8 - 1 - __builtin_clzl((unsigned long)(x)))
</code></pre>

For a similar ceil(log2(x)), use:

<pre><code>#define FAST_LOG2_UP(x) (((x) - (1 &lt;&lt; FAST_LOG2(x))) ? FAST_LOG2(x) + 1 : FAST_LOG2(x))
</code></pre>

The latter can be further optimized using more gcc peculiarities to avoid the double call to the builtin, but I'm not sure you need it here.

blocks|key|1497199|text|这个算法已经发布了，但是下面的实现非常紧凑，应该会优化成无分支的代码。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1497200|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%2B%2B)+{
++++int+k+=+(((x+&+t[i])+==+0)+?+0+:+j);
++++y+%2B=+k;
++++x+>>=+k;
++++j+>>=+1;
++}

++return+y;
}


#include+<stdio.h>
#include+<stdlib.h>

int+main(int+argc,+char+*argv[])
{
++printf("%25d\n",+ceil_log2(atol(argv[1])));

++return+0;
}|code-block|syntax|javascript|1497201|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

This algorithm has already been posted, but the following implementation is very compact and should optimize into branch-free code.

<pre><code>int ceil_log2(unsigned long long x)
{
 static const unsigned long long t[6] = {
 0xFFFFFFFF00000000ull,
 0x00000000FFFF0000ull,
 0x000000000000FF00ull,
 0x00000000000000F0ull,
 0x000000000000000Cull,
 0x0000000000000002ull
 };

 int y = (((x &amp; (x - 1)) == 0) ? 0 : 1);
 int j = 32;
 int i;

 for (i = 0; i &lt; 6; i++) {
 int k = (((x &amp; t[i]) == 0) ? 0 : j);
 y += k;
 x &gt;&gt;= k;
 j &gt;&gt;= 1;
 }

 return y;
}


#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

int main(int argc, char *argv[])
{
 printf("%d\n", ceil_log2(atol(argv[1])));

 return 0;
}
</code></pre>

blocks|key|748843|text|下面的代码片段是一种安全且可移植的方法，用于扩展plain-C方法，例如@dgobbi的方法，以便在使用支持编译器(Clang)进行编译时使用编译器内部函数。将其放在方法的顶部将导致该方法在内置可用时使用它。当内置代码不可用时，该方法将回退到标准C代码。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|748844|#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))+%2B+(!!(x+&+(x+-+1)));
#endif|code-block|syntax|javascript|748845|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

The following code snippet is a safe and portable way to extend plain-C methods, such as @dgobbi's, to use compiler intrinsics when compiled using supporting compilers (Clang). Placing this at the top of the method will cause the method to use the builtin when it is available. When the builtin is unavailable the method will fall back to the standard C code.

<pre><code>#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 &amp; (x - 1)));
#endif
</code></pre>

blocks|key|2464982|text|下面的代码更简单，只要输入xlog1就可以工作。输入clog2(0)将得到一个未定义的答案(这是有意义的，因为>=+(0)是无穷大的…)如果需要，您可以为(x+==+0)添加错误检查：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2464983|unsigned+int+clog2+(unsigned+int+x)
{
++++unsigned+int+result+=+0;
++++--x;
++++while+(x+>+0)+{
++++++++%2B%2Bresult;
++++++++x+>>=+1;
++++}

++++return+result;
}|code-block|syntax|javascript|2464984|顺便说一句，log2的地板代码类似于：(同样，假设x+>=为1)|2464985|unsigned+int+flog2+(unsigned+int+x)
{
++++unsigned+int+result+=+0;
++++while+(x+>+1)+{
++++++++%2B%2Bresult;
++++++++x+>>=+1;
++++}

++++return+result;
}|2464986|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

The code below is simpler and will work as long as the input x >= 1. input clog2(0) will get an undefined answer (which makes sense because log(0) is infinity...) You can add error checking for (x == 0) if you want:

<pre><code>unsigned int clog2 (unsigned int x)
{
 unsigned int result = 0;
 --x;
 while (x &gt; 0) {
 ++result;
 x &gt;&gt;= 1;
 }

 return result;
}
</code></pre>

By the way, the code for the floor of log2 is similar: (Again, assuming x >= 1)

<pre><code>unsigned int flog2 (unsigned int x)
{
 unsigned int result = 0;
 while (x &gt; 1) {
 ++result;
 x &gt;&gt;= 1;
 }

 return result;
}
</code></pre>

blocks|key|748870|text|对于均匀分布的整数，朴素线性搜索可能是一种选择，因为它平均需要的比较略少于2次(对于任何整数大小)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|748871|/*+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++\
)|code-block|syntax|javascript|748872|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

The naive linear search may be an option for evenly distributed integers, since it needs slightly less than 2 comparisons on average (for any integer size).

<pre><code>/* between 1 and 64 comparisons, ~2 on average */
#define u64_size(c) ( \
 0x8000000000000000 &lt; (c) ? 64 \
 : 0x4000000000000000 &lt; (c) ? 63 \
 : 0x2000000000000000 &lt; (c) ? 62 \
 : 0x1000000000000000 &lt; (c) ? 61 \
...
 : 0x0000000000000002 &lt; (c) ? 2 \
 : 0x0000000000000001 &lt; (c) ? 1 \
 : 0 \
)
</code></pre>

blocks|key|2465107|text|据我所知，最快的方法是使用快速的log2向下舍入，结合对输入值前后的无条件调整来处理向上舍入的情况，如下面的lg_down()所示。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2465108|/*+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)+%2B+1;
}|code-block|syntax|javascript|2465109|基本上，对于除2的精确幂以外的所有值，向下舍入的结果加1都是正确的(因为在这种情况下，floor和ceil方法应该返回相同的结果)，所以从输入值中减去1就足够了(对于其他情况，它不会改变答案)，然后将1加到结果中就足够了。|2465110|这通常比通过显式检查2的确切幂(例如，添加!!(x+&+(x+-+1))项)来调整该值的方法略快。它避免了任何比较和条件操作或分支，更有可能在内联时更简单，更易于矢量化，等等。|2465111|这依赖于大多数CPU使用clang/icc/+__builtin_clzl内置的BitScanReverse提供的“计数前导位”功能，但其他平台提供了类似的功能(例如，Visual+Studio中固有的CPU)。|2465112|不幸的是，这可能会为log(1)返回错误的答案，因为这会导致__builtin_clzl(0)，这是基于gcc文档的未定义行为。当然，一般的“前导零计数”函数在0处有完美的行为定义，但gcc内置函数是这样定义的，因为在x86上的BMI+ISA扩展之前，它将使用本身具有未定义行为的bsr+instruction。|2465113|如果您知道您拥有lzcnt指令，那么可以通过直接使用lzcnt内部函数来解决这个问题。除了x86以外的大多数平台从一开始就没有经历过bsr错误，并且可能还提供了访问其“计数前导零”指令的方法(如果有的话)。|2465114|entityMap|0|LINK|mutability|MUTABLE|url|http://www.felixcloutier.com/x86/BSR.html^0|G|4|1I|9|0|0|17|5|1D|4|0|L|F|0|N|E|14|E|0|A|6|U|H|3W|3|3W|F|0|0|8|5|Q|5|1U|3|0^^$0|@$1|2|3|4|5|6|7|12|8|@$9|13|A|14|B|C]|$9|15|A|16|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|17|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|18|8|@$9|19|A|1A|B|C]|$9|1B|A|1C|B|C]]|D|@]|E|$]]|$1|M|3|N|5|6|7|1D|8|@$9|1E|A|1F|B|C]]|D|@]|E|$]]|$1|O|3|P|5|6|7|1G|8|@$9|1H|A|1I|B|C]|$9|1J|A|1K|B|C]]|D|@]|E|$]]|$1|Q|3|R|5|6|7|1L|8|@$9|1M|A|1N|B|C]|$9|1O|A|1P|B|C]|$9|1Q|A|1R|B|C]]|D|@$9|1S|A|1T|1|1U]]|E|$]]|$1|S|3|T|5|6|7|1V|8|@$9|1W|A|1X|B|C]|$9|1Y|A|1Z|B|C]|$9|20|A|21|B|C]]|D|@]|E|$]]|$1|U|3|-4|5|6|7|22|8|@]|D|@]|E|$]]]|V|$W|$5|X|Y|Z|E|$10|11]]]]

The fastest approach I'm aware of uses a fast <code>log2</code> that rounds down, combined unconditional adjustment of input value before and after to handle the rounding up case as in <code>lg_down()</code> shown below.

<pre><code>/* 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;
}
</code></pre>

Basically adding 1 to the rounded-down result is already correct for all values except exact powers of two (since in that case the <code>floor</code> and <code>ceil</code> approaches should return the same answer), so it is sufficient to subtract 1 from the input value to handle that case (it doesn't change the answer for the other cases) and add one to the result. 

This is usually slightly faster than the approaches that adjust the value by explicitly checking for exact powers of two (e.g., adding a <code>!!(x &amp; (x - 1))</code> term). It avoids any comparisons and conditional operations or branches, is more likely to simply when inlining, is more amenable to vectorization, etc.

This relies on the "count leading bits" functionality offered by most CPUs using the clang/icc/gcc builtin <code>__builtin_clzl</code>, but other platforms offer something similar (e.g., the <code>BitScanReverse</code> intrinsic in Visual Studio).

Unfortunately, this many return the wrong answer for <code>log(1)</code>, since that leads to <code>__builtin_clzl(0)</code> which is undefined behavior based on the gcc documentation. Of course, the general "count leading zeros" function has perfectly defined behavior at zero, but the gcc builtin is defined in this way because prior to the BMI ISA extension on x86, it would have been using the <a href="http://www.felixcloutier.com/x86/BSR.html" rel="noreferrer"><code>bsr</code> instruction</a> which itself has undefined behavior.

You could work around this if you know you have the <code>lzcnt</code> instruction by using the <code>lzcnt</code> intrinsic directly. Most platforms other than x86 never went through the <code>bsr</code> mistake in the first place, and probably also offer methods to access their "count leading zeros" instruction if they have one.

blocks|key|1494407|text|在撰写本文时，我将为您提供x86-64的最快方法，以及一个通用技术，如果您有一个快速的基础，即对小于2%5E63的参数有效，如果您关心整个范围，请参见下面的内容。|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|1494408|我对其他答案的低质量感到惊讶，因为他们告诉你如何获得地板，但以一种非常昂贵的方式转换地板(使用条件句和所有东西！)一直到天花板。|1494409|如果您可以快速获得对数的下限，例如，使用__builtin_clzll，那么很容易获得下限，如下所示：|CODE|1494410|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);
}|code-block|syntax|javascript|1494411|它之所以有效，是因为它将结果加1，除非x恰好是2的幂。|1494412|请参阅x86-64汇编程序差异at+the+compiler+explorer，了解类似这样的另一种实现：|1494413|auto+log2CeilingDumb(unsigned+long+x)+{
++++return+log2Floor(x)+%2B+(!!(x+&+(x+-+1)));
}|1494414|提供：|1494415|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+%2B+rdi]
++add+rax,+-1
++bsr+rax,+rax
++ret|1494416|对于整个范围，它是在前面的答案中：return+log2Floor(x+-+1)+%2B+1，这明显更慢，因为它在x86-64中使用四条指令，而不是上面的三条指令。|1494417|entityMap|0|LINK|mutability|MUTABLE|url|https://gcc.godbolt.org/z/zrzwaW^0|1B|7|0|0|K|F|0|0|0|F|O|0|0|0|0|0|H|R|0^^$0|@$1|2|3|4|5|6|7|19|8|@$9|1A|A|1B|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|1C|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|1D|8|@$9|1E|A|1F|B|J]]|D|@]|E|$]]|$1|K|3|L|5|M|7|1G|8|@]|D|@]|E|$N|O]]|$1|P|3|Q|5|6|7|1H|8|@]|D|@]|E|$]]|$1|R|3|S|5|6|7|1I|8|@]|D|@$9|1J|A|1K|1|1L]]|E|$]]|$1|T|3|U|5|M|7|1M|8|@]|D|@]|E|$N|O]]|$1|V|3|W|5|6|7|1N|8|@]|D|@]|E|$]]|$1|X|3|Y|5|M|7|1O|8|@]|D|@]|E|$N|O]]|$1|Z|3|10|5|6|7|1P|8|@$9|1Q|A|1R|B|J]]|D|@]|E|$]]|$1|11|3|-4|5|6|7|1S|8|@]|D|@]|E|$]]]|12|$13|$5|14|15|16|E|$17|18]]]]

I will give you the fastest way for x86-64 at the time of writing, and a general technique if you have a fast floor that works for arguments &lt; 2^63, if you care for the full range, then see below.

I am surprised about the low quality of the other answers because they tell you how to get the floor but transform the floor in a very expensive way (using conditionals and everything!) to the ceiling.

If you can get the floor of the logarithm quickly, for example, using <code>__builtin_clzll</code>, then the floor is very easily obtained like this:

<pre><code>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);
}
</code></pre>

It works because it adds 1 to the result unless x is exactly a power of 2.

See the x86-64 assembler difference <a href="https://gcc.godbolt.org/z/zrzwaW" rel="nofollow noreferrer">at the compiler explorer</a> for another implementation of ceiling like this:

<pre><code>auto log2CeilingDumb(unsigned long x) {
 return log2Floor(x) + (!!(x &amp; (x - 1)));
}
</code></pre>

Gives:

<pre><code>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
</code></pre>

For the full range, it is in a previous answer: <code>return log2Floor(x - 1) + 1</code>, this is significantly slower since it uses in x86-64 four instructions compared to three above.

blocks|key|1497380|text|我已经对64位“最高位”的几个实现进行了基准测试。实际上，最“分支自由”的代码并不是最快的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1497381|这是我的highest-bit.c源文件：|offset|length|style|CODE|1497382|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%2B%2B)+{
++++int+mi+=+lo+%2B+(hi+-+lo)+/+2;

++++if+((n+>>+mi)+!=+0)
++++++lo+=+mi;
++++else+if+((n+&+(mask[i]+<<+lo))+!=+0)
++++++hi+=+mi;
++}

++return+lo+%2B+1;
}

int+highest_bit_shift(unsigned+long+long+n)
{
++int+i+=+0;
++for+(;+n;+n+>>=+1,+i%2B%2B)
++++;+/*+empty+*/
++return+i;
}

static+int+count_ones(unsigned+long+long+d)
{
++d+=+((d+&+0xAAAAAAAAAAAAAAAA)+>>++1)+%2B+(d+&+0x5555555555555555);
++d+=+((d+&+0xCCCCCCCCCCCCCCCC)+>>++2)+%2B+(d+&+0x3333333333333333);
++d+=+((d+&+0xF0F0F0F0F0F0F0F0)+>>++4)+%2B+(d+&+0x0F0F0F0F0F0F0F0F);
++d+=+((d+&+0xFF00FF00FF00FF00)+>>++8)+%2B+(d+&+0x00FF00FF00FF00FF);
++d+=+((d+&+0xFFFF0000FFFF0000)+>>+16)+%2B+(d+&+0x0000FFFF0000FFFF);
++d+=+((d+&+0xFFFFFFFF00000000)+>>+32)+%2B+(d+&+0x00000000FFFFFFFF);
++return+d;
}

int+highest_bit_parallel(unsigned+long+long+n)
{
++n+%7C=+n+>>+1;
++n+%7C=+n+>>+2;
++n+%7C=+n+>>+4;
++n+%7C=+n+>>+8;
++n+%7C=+n+>>+16;
++n+%7C=+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%2B%2B)+{
++++int+k+=+(((x+&+t[i])+==+0)+?+0+:+j);
++++y+%2B=+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+%2B=+32;
++++value+=+value+>>+32;
++}
++if+(value+&+0x00000000FFFF0000ULL)
++{
++++pos+%2B=+16;
++++value+=+value+>>+16;
++}
++if+(value+&+0x000000000000FF00ULL)
++{
++++pos+%2B=+8;
++++value+=+value+>>+8;
++}
++if+(value+&+0x00000000000000F0ULL)
++{
++++pos+%2B=+4;
++++value+=+value+>>+4;
++}
++if+(value+&+0x000000000000000CULL)
++{
++++pos+%2B=+2;
++++value+=+value+>>+2;
++}
++if+(value+&+0x0000000000000002ULL)
++{
++++pos+%2B=+1;
++++value+=+value+>>+1;
++}
++return+pos;
}|code-block|syntax|javascript|1497383|这是highest-bit.h|1497384|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);|1497385|和主程序(对所有的复制和粘贴感到抱歉)：|1497386|#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%2B%2B)+{
++++for+(v+=+0x8000000000000000;+v;+v+>>=+1)
++++++highest_bit_unrolled(v);
++}

++end+=+clock();

++printf("highest_bit_unrolled+=+%256.3fs\n",+timedelta(start,+end));

++start+=+clock();

++for+(i+=+0;+i+<+10000000;+i%2B%2B)+{
++++for+(v+=+0x8000000000000000;+v;+v+>>=+1)
++++++highest_bit_parallel(v);
++}

++end+=+clock();

++printf("highest_bit_parallel+=+%256.3fs\n",+timedelta(start,+end));

++start+=+clock();

++for+(i+=+0;+i+<+10000000;+i%2B%2B)+{
++++for+(v+=+0x8000000000000000;+v;+v+>>=+1)
++++++highest_bit_bs(v);
++}

++end+=+clock();

++printf("highest_bit_bs+=+%256.3fs\n",+timedelta(start,+end));

++start+=+clock();

++for+(i+=+0;+i+<+10000000;+i%2B%2B)+{
++++for+(v+=+0x8000000000000000;+v;+v+>>=+1)
++++++highest_bit_shift(v);
++}

++end+=+clock();

++printf("highest_bit_shift+=+%256.3fs\n",+timedelta(start,+end));

++start+=+clock();

++for+(i+=+0;+i+<+10000000;+i%2B%2B)+{
++++for+(v+=+0x8000000000000000;+v;+v+>>=+1)
++++++highest_bit_so(v);
++}

++end+=+clock();

++printf("highest_bit_so+=+%256.3fs\n",+timedelta(start,+end));

++start+=+clock();

++for+(i+=+0;+i+<+10000000;+i%2B%2B)+{
++++for+(v+=+0x8000000000000000;+v;+v+>>=+1)
++++++highest_bit_so2(v);
++}

++end+=+clock();

++printf("highest_bit_so2+=+%256.3fs\n",+timedelta(start,+end));

++return+0;
}|1497387|我试过各种英特尔x86盒，有旧的也有新的。|1497388|与highest_bit_parallel+(无分支比特操作)相比，highest_bit_unrolled+(展开的二进制搜索)的速度始终要快得多。这比highest_bit_bs+(二进制搜索循环)快，反过来又比highest_bit_shift+(朴素移位和计数循环)快。|1497389|highest_bit_unrolled也比可接受的SO答案(highest_bit_so)中的快，也比另一个答案(highest_bit_so2)中的快。|1497390|基准测试循环遍历覆盖连续位的一位掩码。这是为了试图击败展开的二进制搜索中的分支预测，这是现实的:在现实世界的程序中，输入案例不太可能展示位位置的局部性。|1497391|以下是在旧Intel(R)+Core(TM)2+Duo+CPU+E4500+@+2.20GHz上的结果|1497392|$+./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|1497393|在较新型号的Intel(R)+Core(TM)+i7-6700K+CPU+@+4.00GHz上|1497394|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|1497395|在较新的硬件上，highest_bit_so2更接近于highest_bit_unrolled。顺序并不完全相同；现在highest_bit_so确实落后了，而且比highest_bit_parallel慢。|1497396|最快的是highest_bit_unrolled，它包含的代码最多，分支最多。每一个返回值都是由一组不同的条件通过它自己的专用代码实现的。|1497397|“避免所有分支”的直觉(由于担心分支错误预测)并不总是正确的。现代(甚至不再那么现代)的处理器包含了相当多的巧妙之处，以便不会被分支所阻碍。|1497398|1497399|附注：highest_bit_unrolled是在December+2011的TXR语言中引入的(有错误，自调试以来)。|1497400|最近，我开始怀疑一些更好、更紧凑的没有分支的代码可能不会更快。|1497401|我对结果感到有点惊讶。|1497402|可以说，代码实际上应该是GNU的#ifdef-ing，并使用一些编译器原语，但就可移植性而言，该版本仍然存在。|1497403|entityMap|0|LINK|mutability|MUTABLE|url|http://www.kylheku.com/cgit/txr/commit/?id=d49893bac4c0b842765bbf491720512048a1e13c^0|0|4|D|0|0|2|D|0|0|0|0|0|1|K|Y|K|25|E|30|H|0|0|K|V|E|1M|F|0|0|5|16|0|0|6|14|0|0|8|F|R|K|1N|E|2A|K|0|4|K|0|0|0|3|K|P|D|0|0|0|0|G|6|0^^$0|@$1|2|3|4|5|6|7|1X|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1Y|8|@$D|1Z|E|20|F|G]]|9|@]|A|$]]|$1|H|3|I|5|J|7|21|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|22|8|@$D|23|E|24|F|G]]|9|@]|A|$]]|$1|O|3|P|5|J|7|25|8|@]|9|@]|A|$K|L]]|$1|Q|3|R|5|6|7|26|8|@]|9|@]|A|$]]|$1|S|3|T|5|J|7|27|8|@]|9|@]|A|$K|L]]|$1|U|3|V|5|6|7|28|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|29|8|@$D|2A|E|2B|F|G]|$D|2C|E|2D|F|G]|$D|2E|E|2F|F|G]|$D|2G|E|2H|F|G]]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|2I|8|@$D|2J|E|2K|F|G]|$D|2L|E|2M|F|G]|$D|2N|E|2O|F|G]]|9|@]|A|$]]|$1|10|3|11|5|6|7|2P|8|@]|9|@]|A|$]]|$1|12|3|13|5|6|7|2Q|8|@$D|2R|E|2S|F|G]]|9|@]|A|$]]|$1|14|3|15|5|J|7|2T|8|@]|9|@]|A|$K|L]]|$1|16|3|17|5|6|7|2U|8|@$D|2V|E|2W|F|G]]|9|@]|A|$]]|$1|18|3|19|5|J|7|2X|8|@]|9|@]|A|$K|L]]|$1|1A|3|1B|5|6|7|2Y|8|@$D|2Z|E|30|F|G]|$D|31|E|32|F|G]|$D|33|E|34|F|G]|$D|35|E|36|F|G]]|9|@]|A|$]]|$1|1C|3|1D|5|6|7|37|8|@$D|38|E|39|F|G]]|9|@]|A|$]]|$1|1E|3|1F|5|6|7|3A|8|@]|9|@]|A|$]]|$1|1G|3|-4|5|6|7|3B|8|@]|9|@]|A|$]]|$1|1H|3|1I|5|6|7|3C|8|@$D|3D|E|3E|F|G]]|9|@$D|3F|E|3G|1|3H]]|A|$]]|$1|1J|3|1K|5|6|7|3I|8|@]|9|@]|A|$]]|$1|1L|3|1M|5|6|7|3J|8|@]|9|@]|A|$]]|$1|1N|3|1O|5|6|7|3K|8|@$D|3L|E|3M|F|G]]|9|@]|A|$]]|$1|1P|3|-4|5|6|7|3N|8|@]|9|@]|A|$]]]|1Q|$1R|$5|1S|1T|1U|A|$1V|1W]]]]

I have benchmarked several implementations of a 64 bit "highest bit". The most "branch free" code is not in fact the fastest.

This is my <code>highest-bit.c</code> source file:

<pre><code>int highest_bit_unrolled(unsigned long long n)
{
 if (n &amp; 0xFFFFFFFF00000000) {
 if (n &amp; 0xFFFF000000000000) {
 if (n &amp; 0xFF00000000000000) {
 if (n &amp; 0xF000000000000000) {
 if (n &amp; 0xC000000000000000)
 return (n &amp; 0x8000000000000000) ? 64 : 63;
 else
 return (n &amp; 0x2000000000000000) ? 62 : 61;
 } else {
 if (n &amp; 0x0C00000000000000)
 return (n &amp; 0x0800000000000000) ? 60 : 59;
 else
 return (n &amp; 0x0200000000000000) ? 58 : 57;
 }
 } else {
 if (n &amp; 0x00F0000000000000) {
 if (n &amp; 0x00C0000000000000)
 return (n &amp; 0x0080000000000000) ? 56 : 55;
 else
 return (n &amp; 0x0020000000000000) ? 54 : 53;
 } else {
 if (n &amp; 0x000C000000000000)
 return (n &amp; 0x0008000000000000) ? 52 : 51;
 else
 return (n &amp; 0x0002000000000000) ? 50 : 49;
 }
 }
 } else {
 if (n &amp; 0x0000FF0000000000) {
 if (n &amp; 0x0000F00000000000) {
 if (n &amp; 0x0000C00000000000)
 return (n &amp; 0x0000800000000000) ? 48 : 47;
 else
 return (n &amp; 0x0000200000000000) ? 46 : 45;
 } else {
 if (n &amp; 0x00000C0000000000)
 return (n &amp; 0x0000080000000000) ? 44 : 43;
 else
 return (n &amp; 0x0000020000000000) ? 42 : 41;
 }
 } else {
 if (n &amp; 0x000000F000000000) {
 if (n &amp; 0x000000C000000000)
 return (n &amp; 0x0000008000000000) ? 40 : 39;
 else
 return (n &amp; 0x0000002000000000) ? 38 : 37;
 } else {
 if (n &amp; 0x0000000C00000000)
 return (n &amp; 0x0000000800000000) ? 36 : 35;
 else
 return (n &amp; 0x0000000200000000) ? 34 : 33;
 }
 }
 }
 } else {
 if (n &amp; 0x00000000FFFF0000) {
 if (n &amp; 0x00000000FF000000) {
 if (n &amp; 0x00000000F0000000) {
 if (n &amp; 0x00000000C0000000)
 return (n &amp; 0x0000000080000000) ? 32 : 31;
 else
 return (n &amp; 0x0000000020000000) ? 30 : 29;
 } else {
 if (n &amp; 0x000000000C000000)
 return (n &amp; 0x0000000008000000) ? 28 : 27;
 else
 return (n &amp; 0x0000000002000000) ? 26 : 25;
 }
 } else {
 if (n &amp; 0x0000000000F00000) {
 if (n &amp; 0x0000000000C00000)
 return (n &amp; 0x0000000000800000) ? 24 : 23;
 else
 return (n &amp; 0x0000000000200000) ? 22 : 21;
 } else {
 if (n &amp; 0x00000000000C0000)
 return (n &amp; 0x0000000000080000) ? 20 : 19;
 else
 return (n &amp; 0x0000000000020000) ? 18 : 17;
 }
 }
 } else {
 if (n &amp; 0x000000000000FF00) {
 if (n &amp; 0x000000000000F000) {
 if (n &amp; 0x000000000000C000)
 return (n &amp; 0x0000000000008000) ? 16 : 15;
 else
 return (n &amp; 0x0000000000002000) ? 14 : 13;
 } else {
 if (n &amp; 0x0000000000000C00)
 return (n &amp; 0x0000000000000800) ? 12 : 11;
 else
 return (n &amp; 0x0000000000000200) ? 10 : 9;
 }
 } else {
 if (n &amp; 0x00000000000000F0) {
 if (n &amp; 0x00000000000000C0)
 return (n &amp; 0x0000000000000080) ? 8 : 7;
 else
 return (n &amp; 0x0000000000000020) ? 6 : 5;
 } else {
 if (n &amp; 0x000000000000000C)
 return (n &amp; 0x0000000000000008) ? 4 : 3;
 else
 return (n &amp; 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 &lt; sizeof mask / sizeof mask[0]; i++) {
 int mi = lo + (hi - lo) / 2;

 if ((n &gt;&gt; mi) != 0)
 lo = mi;
 else if ((n &amp; (mask[i] &lt;&lt; lo)) != 0)
 hi = mi;
 }

 return lo + 1;
}

int highest_bit_shift(unsigned long long n)
{
 int i = 0;
 for (; n; n &gt;&gt;= 1, i++)
 ; /* empty */
 return i;
}

static int count_ones(unsigned long long d)
{
 d = ((d &amp; 0xAAAAAAAAAAAAAAAA) &gt;&gt; 1) + (d &amp; 0x5555555555555555);
 d = ((d &amp; 0xCCCCCCCCCCCCCCCC) &gt;&gt; 2) + (d &amp; 0x3333333333333333);
 d = ((d &amp; 0xF0F0F0F0F0F0F0F0) &gt;&gt; 4) + (d &amp; 0x0F0F0F0F0F0F0F0F);
 d = ((d &amp; 0xFF00FF00FF00FF00) &gt;&gt; 8) + (d &amp; 0x00FF00FF00FF00FF);
 d = ((d &amp; 0xFFFF0000FFFF0000) &gt;&gt; 16) + (d &amp; 0x0000FFFF0000FFFF);
 d = ((d &amp; 0xFFFFFFFF00000000) &gt;&gt; 32) + (d &amp; 0x00000000FFFFFFFF);
 return d;
}

int highest_bit_parallel(unsigned long long n)
{
 n |= n &gt;&gt; 1;
 n |= n &gt;&gt; 2;
 n |= n &gt;&gt; 4;
 n |= n &gt;&gt; 8;
 n |= n &gt;&gt; 16;
 n |= n &gt;&gt; 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 &amp; (x - 1)) == 0) ? 0 : 1);
 int j = 32;
 int i;

 for (i = 0; i &lt; 6; i++) {
 int k = (((x &amp; t[i]) == 0) ? 0 : j);
 y += k;
 x &gt;&gt;= k;
 j &gt;&gt;= 1;
 }

 return y;
}

int highest_bit_so2(unsigned long long value)
{
 int pos = 0;
 if (value &amp; (value - 1ULL))
 {
 pos = 1;
 }
 if (value &amp; 0xFFFFFFFF00000000ULL)
 {
 pos += 32;
 value = value &gt;&gt; 32;
 }
 if (value &amp; 0x00000000FFFF0000ULL)
 {
 pos += 16;
 value = value &gt;&gt; 16;
 }
 if (value &amp; 0x000000000000FF00ULL)
 {
 pos += 8;
 value = value &gt;&gt; 8;
 }
 if (value &amp; 0x00000000000000F0ULL)
 {
 pos += 4;
 value = value &gt;&gt; 4;
 }
 if (value &amp; 0x000000000000000CULL)
 {
 pos += 2;
 value = value &gt;&gt; 2;
 }
 if (value &amp; 0x0000000000000002ULL)
 {
 pos += 1;
 value = value &gt;&gt; 1;
 }
 return pos;
}
</code></pre>

This is <code>highest-bit.h</code>:

<pre><code>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);
</code></pre>

And the main program (sorry about all the copy and paste):

<pre><code>#include &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;
#include &lt;time.h&gt;
#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 &lt; 10000000; i++) {
 for (v = 0x8000000000000000; v; v &gt;&gt;= 1)
 highest_bit_unrolled(v);
 }

 end = clock();

 printf("highest_bit_unrolled = %6.3fs\n", timedelta(start, end));

 start = clock();

 for (i = 0; i &lt; 10000000; i++) {
 for (v = 0x8000000000000000; v; v &gt;&gt;= 1)
 highest_bit_parallel(v);
 }

 end = clock();

 printf("highest_bit_parallel = %6.3fs\n", timedelta(start, end));

 start = clock();

 for (i = 0; i &lt; 10000000; i++) {
 for (v = 0x8000000000000000; v; v &gt;&gt;= 1)
 highest_bit_bs(v);
 }

 end = clock();

 printf("highest_bit_bs = %6.3fs\n", timedelta(start, end));

 start = clock();

 for (i = 0; i &lt; 10000000; i++) {
 for (v = 0x8000000000000000; v; v &gt;&gt;= 1)
 highest_bit_shift(v);
 }

 end = clock();

 printf("highest_bit_shift = %6.3fs\n", timedelta(start, end));

 start = clock();

 for (i = 0; i &lt; 10000000; i++) {
 for (v = 0x8000000000000000; v; v &gt;&gt;= 1)
 highest_bit_so(v);
 }

 end = clock();

 printf("highest_bit_so = %6.3fs\n", timedelta(start, end));

 start = clock();

 for (i = 0; i &lt; 10000000; i++) {
 for (v = 0x8000000000000000; v; v &gt;&gt;= 1)
 highest_bit_so2(v);
 }

 end = clock();

 printf("highest_bit_so2 = %6.3fs\n", timedelta(start, end));

 return 0;
}
</code></pre>

I've tried this various Intel x86 boxes, old and new.

The <code>highest_bit_unrolled</code> (unrolled binary search) is consistently significantly faster than <code>highest_bit_parallel</code> (branch-free bit ops). This is faster than than <code>highest_bit_bs</code> (binary search loop), and that in turn is faster than <code>highest_bit_shift</code> (naive shift and count loop).

<code>highest_bit_unrolled</code> is also faster than the one in the accepted SO answer (<code>highest_bit_so</code>) and also one given in another answer (<code>highest_bit_so2</code>).

The benchmark cycles through a one-bit mask that covers successive bits. This is to try to defeat branch prediction in the unrolled binary search, which is realistic: in a real world program, the input cases are unlikely to exhibit locality of bit position.

Here are results on an old <code>Intel(R) Core(TM)2 Duo CPU E4500 @ 2.20GHz</code>:

<pre><code>$ ./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
</code></pre>

On a newer model <code>Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz</code>:

<pre><code>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
</code></pre>

On the newer hardware, <code>highest_bit_so2</code> comes closer to <code>highest_bit_unrolled</code> on the newer hardware. The order is not quite the same; now <code>highest_bit_so</code> really falls behind, and is slower than <code>highest_bit_parallel</code>.

The fastest one, <code>highest_bit_unrolled</code> contains the most code with the most branches. Every single return value reached by a different set of conditions with its own dedicated piece of code.

The intuition of "avoid all branches" (due to worries about branch mis-predictions) is not always right. Modern (and even not-so-modern any more) processors contain considerable cunning in order not to be hampered by branching.

<hr>

P.S. the <code>highest_bit_unrolled</code> was introduced in the TXR language in <a href="http://www.kylheku.com/cgit/txr/commit/?id=d49893bac4c0b842765bbf491720512048a1e13c" rel="nofollow noreferrer">December 2011</a> (with mistakes, since debugged).

Recently, I started wondering whether some nicer, more compact code without branches might not be faster.

I'm somewhat surprised by the results.

Arguably, the code should really be <code>#ifdef</code>-ing for GNU C and using some compiler primitives, but as far as portability goes, that version stays.

blocks|key|3873427|text|一种对最高位的二进制搜索。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3873428|Bit+Twiddling+Hacks是stanford.edu上关于位操作技巧的一个很好的参考资料。在该参考中有许多用于许多事情的示例，包括用于计算log2值的几种算法。这包括类似的--也许更好--的方法。|offset|length|3873429|我的想法是，一种对最高有效位的二进制搜索将比简单解决方案的最大60%2B循环更快。该算法将n移位其上一次移位值的一半，以使其在最大有效位上为零。|style|CODE|3873430|对于64位的值，它需要6次迭代来确定最高有效位的位置-这是n的floor+log2。|3873431|根据我的测量，这种方法的性能并不比下面第二个示例中的简单循环好多少。|3873432|//+floor+log2+in+6+max+iterations+for+unsigned+64-bit+values.
//
int+floor_log2(unsigned+long+long+n)
{
++++int+shval+=+32;
++++int+msb+++=++0;
++++while+(shval)+{
++++++++if+(n+>>+shval)+{
++++++++++++msb+%2B=+shval;
++++++++++++n++>>=+shval;
++++++++}
++++++++shval+>>=+1;
++++}
++++return+msb;
}

int+ceil_log2(unsigned+long+long+n)+
{
++++return+floor_log2(2+*+n+-+1);
}|code-block|syntax|javascript|3873433|简单的算法：|3873434|int+floor_log2_simple(unsigned+long+long+n)
{
++++int+c+=++0;
++++while+(n)+{
++++++++n+>>=+1;
++++++++c%2B%2B;
++++}
++++return+c+-+1;
}|3873435|在Rust中实现的这些相同的算法执行起来几乎相同。top方法的性能稍好一些--但平均只差几纳秒。无论对算法进行多少调整，都不会带来任何更好的性能。|3873436|嗯..。|3873437|entityMap|0|LINK|mutability|MUTABLE|url|https://graphics.stanford.edu/%257Eseander/bithacks.html#IntegerLogObvious^0|0|0|J|0|0|17|1|0|T|1|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|18|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|19|8|@]|9|@$D|1A|E|1B|1|1C]]|A|$]]|$1|F|3|G|5|6|7|1D|8|@$D|1E|E|1F|H|I]]|9|@]|A|$]]|$1|J|3|K|5|6|7|1G|8|@$D|1H|E|1I|H|I]]|9|@]|A|$]]|$1|L|3|M|5|6|7|1J|8|@]|9|@]|A|$]]|$1|N|3|O|5|P|7|1K|8|@]|9|@]|A|$Q|R]]|$1|S|3|T|5|6|7|1L|8|@]|9|@]|A|$]]|$1|U|3|V|5|P|7|1M|8|@]|9|@]|A|$Q|R]]|$1|W|3|X|5|6|7|1N|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|1O|8|@]|9|@]|A|$]]|$1|10|3|-4|5|6|7|1P|8|@]|9|@]|A|$]]]|11|$12|$5|13|14|15|A|$16|17]]]]

A sort of binary search for the highest order bit.
A good reference on bitwise operation hacks posted on stanford.edu: <a href="https://graphics.stanford.edu/%7Eseander/bithacks.html#IntegerLogObvious" rel="nofollow noreferrer">Bit Twiddling Hacks</a>.
There are a lot of examples in that reference for many things, including several algorithms for computing log2 values. This includes similar - and maybe better - approaches to this one.
I had the idea that a sort of binary search for the most significant bit would be faster than the max 60+ loops of the simple solution. The algorithm shifts <code>n</code> by half of it's last shift value each iteration to zero in on the msb.
For 64-bit values, it requires 6 iterations to determine the position of the most significant bit - which is the floor log2 of <code>n</code>.
The performance of this approach, as I measured it, wasn't much better than the simple loop in the 2nd example below.
<pre class="lang-c prettyprint-override"><code>// floor log2 in 6 max iterations for unsigned 64-bit values.
//
int floor_log2(unsigned long long n)
{
 int shval = 32;
 int msb = 0;
 while (shval) {
 if (n &gt;&gt; shval) {
 msb += shval;
 n &gt;&gt;= shval;
 }
 shval &gt;&gt;= 1;
 }
 return msb;
}

int ceil_log2(unsigned long long n) 
{
 return floor_log2(2 * n - 1);
}
</code></pre>
Simple algorithm:
<pre class="lang-c prettyprint-override"><code>int floor_log2_simple(unsigned long long n)
{
 int c = 0;
 while (n) {
 n &gt;&gt;= 1;
 c++;
 }
 return c - 1;
}
</code></pre>
These same algorithms implemented in Rust performed nearly identically. The top approach performed a tiny amount better - but by only by a couple nano seconds on average. No amount of tweaking the algorithm gave any better performance.
meh...

What is a fast way to compute the <code>(long int) ceiling(log_2(i))</code>, where the input and output are 64-bit integers? Solutions for signed or unsigned integers are acceptable. I suspect the best way will be a bit-twiddling method similar to those found <a href="http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious" rel="noreferrer">here</a>, but rather than attempt my own I would like to use something that is already well tested. A general solution will work for all positive values.

For instance, the values for 2,3,4,5,6,7,8 are 1,2,2,3,3,3,3 

Edit: So far the best route seems to be to compute the integer/floor log base 2 (the position of the MSB) using any number of fast existing bithacks or register methods, and then to add one if the input is not a power of two. The fast bitwise check for powers of two is <code>(n&amp;(n-1))</code>.

Edit 2: A good source on integer logarithms and leading zeroes methods is Sections 5-3 and 11-4 in <a href="http://www.hackersdelight.org/" rel="noreferrer">Hacker's Delight</a> by Henry S. Warren. This is the most complete treatment I've found.

Edit 3: This technique looks promising: <a href="https://stackoverflow.com/a/51351885/365478">https://stackoverflow.com/a/51351885/365478</a>

Compute fast log base 2 ceiling

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

在输入和输出都是64位整数的情况下，计算(long int) ceiling(log_2(i))的快速方法是什么？有符号或无符号整数的解决方案是可接受的。我怀疑最好的方法是使用类似于的方法，而不是尝试我自己的方法，而不是使用已经经过良好测试的方法。一个通用的解决方案将适用于所有正值。例如，2,3,4,5,6,7,8的值...

问计算快速对数底2上限
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问计算快速对数底2上限EN