Can I create a 1-to-64 bits bitmask without a conditional in Java?

Question

I want to write a function that takes an int between 1 and 64, and returns an appropriate "bitmask", with as many 1 bits as the input.

I started like this:

/** Computes a bitmaks */
private static long mask(final int bitsPerValue) {
    return (1L << bitsPerValue) - 1L;
}

But realized that it gives the wrong value for 64:

(1L << 64) - 1L == 1L - 1L == 0

Now I have this:

/** Computes a bitmaks */
private static long mask(final int bitsPerValue) {
    return (bitsPerValue == 64) ? -1 : ((1L << bitsPerValue) - 1L);
}

It's rather ugly. And conditionals can change the control flow, so they are more expensive than simple arithmetic operations. I could just pre-compute the masks and put them in a static array, but array access is also more expensive than simple arithmetic operations, probably even more expensive than the conditional.

Is there a reasonable way of writing this without a conditional? This code is going to run zillions of time per second, so it has to be fast.

Answer 1

I tried:

long value = 0xffffffffffffffffl >>> (64 - i); // that's ef ef ef... el.

but this seems to give a problem with i = 0. My gripe with Java not having unsigned ints again. The above works in c. Maybe the above will work in Java 7, given that 'value' is unsigned.

However, since you don't need zero, the above will work fine for you, i.e. values 1 to 64.

Answer 2

Here is a way to do it without conditionals:

private static long mask(final int bitsPerValue) {
    return ((1L << bitsPerValue) - (bitsPerValue >> 6)) - 1L;
}

In Java, 1L << bitsPerValue only uses the six lowest-order bits of bitsPerValue, which means that calling your original function with bitsPerValue=64 is the same as calling it with bitsPerValue=0. The version I present above takes care of that: when bitsPerValue=64, the expression reduces to

(1L - 1L) - 1L == -1L

Now, if you're really going to be calling this "zillions of times per second", I think the best strategy is to benchmark all variants of the code, including the one with conditionals and the one with the lookup table.

Answer 3

IMHO, adding an requirement to have 65-bit value is not good enough. I'd just use OR operation for generating value, it shouldn't take a lot. Like this:

private static long mask(final int bitsPerValue) {
  long mask = 1;
  long value = 0;
  for (int i=0; i<bitsPerValue; i++ ) {
    value = value | mask;
    mask = mask << 1;
  }
  return value;
}

I see that you don't want to use static arrays, but it would be the fastest way which just uses 64 * 8 bytes memory. Moreover, I don't think it's easy to achieve small memory footprint and good enough speed simultaneously. So, just in case, the fastest approach would be:

long valarray[] = new long[64];

private static long[] generateValues() {
  long mask = 1;
  long value = 0;
  for (int i=0; i<64; i++ ) {
    value = value | mask;
    mask = mask << 1;

    valarray[i] = value;
  }
  return valarray;
}

private static long[] mask(final int bitsPerValue) {
  return valarray[bitsPerValue-1];
}

Another possible approach is to use BigInteger for the latest, 64 '1's bit, case. But I don't think it's fast and not ugly.