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

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 2

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.