代码之家 › 专栏 › 技术社区 › James McMahon

如何确定64位值中第n个最高有效位集的位置?

bit-manipulation bitmap java

James McMahon · 技术社区 · 15 年前

我在Java程序中使用一些长的值作为位图。到目前为止,我的方法是:

public class BitmapUtil
{
    private static final long _B_MASK_LEFT_ON = 0x8000000000000000L;

    public static long setNthMsb(int n)
    {
        return BitmapUtil._B_MASK_LEFT_ON >>> n;
    }

    public static boolean isNthMsbSet(long b, int n)
    {
        return (b & (BitmapUtil.setNthMsb(n))) != 0L;
    }

    public static int getNthMsbPosition(long b, int n)
    {
        int ix = 0;
        while (ix < 64 && n >= 0) {
            if (BitmapUtil.isNthMsbSet(b, ix)) {
                if (n == 0) {
                    return ix;
                } else {
                    n--;
                }
            }
            ix++;
        }
        return -1;
    }
}

我看过很多聪明的小把戏,我禁不住觉得应该有更好的方法。有?

3 回复 | 直到 15 年前

Tim Bender 15 年前

我想这就是你想要的,没有任何关于效率的线索。

//      long val = 0xAF00000000000000L;
        long val = 0x0000000000000001L;
        int n = 2;
        int count = 0;
        int i = 0;
        while (i < 65 && count < n) {
            if ((val & 0x8000000000000000L) != 0) {
                count++;
            }
            val = val << 1;
            i++;
        }

这似乎从左边开始计数,其中MSB是位置1,LSB是位置64。如果i==65,则N位未设置。

Alexander Kjäll 15 年前

以下是几种不同的快速算法: bit hacks ,查找该数字的对数2。

最漂亮的是这个,但它只适用于32位数字:

unsigned int v; // find the log base 2 of 32-bit v
int r;          // result goes here

static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

v |= v >> 1; // first round down to power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v = (v >> 1) + 1;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x077CB531U) >> 27];