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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.