CODEWITHSUNDEEP
javabitmapbit-manipulation
Hanno Fietz
Hanno Fietz

Reputation: 31370

How do I determine the position of the nth most significand bit set in a 64-bit value?

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?

Upvotes: 0

Views: 615

Answers (3)

Tim Bender
Tim Bender

Reputation: 20442

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.

Upvotes: 1

Alexander Kj&#228;ll
Alexander Kj&#228;ll

Reputation: 4336

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

Upvotes: 1

dweeves
dweeves

Reputation: 5605

I've found this in C++ for 32 bits, which could be easily adapted to Java & 64 bits

http://lsjandysf.spaces.live.com/blog/cns!54FF19028BDE00EA!440.entry

Upvotes: 0

Related Questions