5

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.

Sebastien Diot
  • 7,183
  • 6
  • 43
  • 85
  • 2
    Have you profiled this? Do you really see any significant difference if you just let it run without the conditional and incorrect results, vs. with the conditional and the correct results? – ziesemer Jan 23 '12 at 11:10
  • Is this for a bitboard-based chess engine? :-) – Jaco Van Niekerk Jan 23 '12 at 11:39
  • 1
    @ziesemer - I bet he wont see any difference (actually, if 64 is demanded often, it could even be faster). Problem is people are so obsessed with performance, yet do not know how JITs and CPUs work ... they just think runtime will be proportional to java expression size in characters ..... – Ingo Jan 23 '12 at 11:40
  • I don't think the above is about the if-statement taking long. It's about elegance. You have to agree that aix's solution below is far more elegant than the above which needs to explicitly check for the special case. I am sure that's Sebastien's reasoning as well. – Jaco Van Niekerk Jan 23 '12 at 11:58
  • @ziesemer Not yet, because I haven't useable test data yet. But even if it was somehow optimized by the JVM, I still thinks it's ugly. – Sebastien Diot Jan 23 '12 at 11:59
  • @Jaco Nope. Voxels! Zillions of voxels! – Sebastien Diot Jan 23 '12 at 11:59

3 Answers3

5

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.

Community
  • 1
  • 1
NPE
  • 486,780
  • 108
  • 951
  • 1,012
3

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.

Jaco Van Niekerk
  • 4,180
  • 2
  • 21
  • 48
  • 0 makes no sense in my case. A data type with a 0 bit depth is no data at all, not even 0 and 1. Your version is simple and easy to understand. Thanks! – Sebastien Diot Jan 23 '12 at 12:08
0

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.

Wizart
  • 940
  • 5
  • 8