问题描述
什么是获得一个数字,我只知道的权力基础2的对数的最佳解决方案两( 2 ^氏/ code>)。 (当然,我知道只有值
2 ^氏/ code>不是
K
本身。)
What is the best solution for getting the base 2 logarithm of a number that I know is a power of two (
2^k
). (Of course I know only the value 2^k
not k
itself.)
我想这样做的一种方法是通过减去1,然后做一个位计数:
One way I thought of doing is by subtracting 1 and then doing a bitcount:
lg2(n) = bitcount( n - 1 ) = k, iff k is an integer
0b10000 - 1 = 0b01111, bitcount(0b01111) = 4
但是,有没有这样做(没有缓存)的一个更快的方法?另外一些不那么快大约涉及将位计数是很好,知道吗?
But is there a faster way of doing it (without caching)? Also something that doesn't involve bitcount about as fast would be nice to know?
其中的应用程序是这样的:
One of the applications this is:
suppose you have bitmask
0b0110111000
and value
0b0101010101
and you are interested of
(value & bitmask) >> number of zeros in front of bitmask
(0b0101010101 & 0b0110111000) >> 3 = 0b100010
this can be done with
using bitcount
value & bitmask >> bitcount((bitmask - 1) xor bitmask) - 1
or using lg2
value & bitmask >> lg2(((bitmask - 1) xor bitmask) + 1 ) - 2
有关它比没有缓存它应该是快于
O(LG电子(K))
,其中 K
是数存储位。
For it to be faster than bitcount without caching it should be faster than
O(lg(k))
where k
is the count of storage bits.
推荐答案
许多架构有一个发现第一个指令(BSR,CLZ,bfffo,cntlzw等),这将是比位计数方法快得多。
Many architectures have a "find first one" instruction (bsr, clz, bfffo, cntlzw, etc.) which will be much faster than bit-counting approaches.
这篇关于如何获得一个数字,是2 ^ k的LG2的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!