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

发布于 2024-08-05 17:53:34 字数 819 浏览 5 评论 0原文

我在 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;
    }
}

我已经看到了很多聪明的小技巧，我不禁觉得应该有更好的方法。有没有？

原文

I'm using some long values as bitmaps in a Java program. Here's my method so far:

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;
    }
}

I've seen so many clever bit tricks that I can't help but feeling that there should be a better way. Is there?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

杀手六號 2024-08-12 17:53:35

我认为这就是你想要的，没有关于这一切效率的线索。

//      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 位未设置。

I think this is what you want, no clues about efficiency of it all.

//      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++;
        }

This seems to count from the left, where the MSB is position 1 and LSB is position 64. If i==65, then n bits were not set.

回复收藏 0 原文

真心难拥有 2024-08-12 17:53:35

这里有一些不同的快速算法：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];

Here is a couple of different fast algorithms: bit hacks, look for calculating the log 2 of the number.

The most beautiful is this one, but it only works for 32 bit numbers:

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];

回复收藏 0 原文