如何获得一个数字，是2 ^ k的LG2 [英] How to get lg2 of a number that is 2^k

问题描述

什么是获得一个数字，我只知道的权力基础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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！