Power of two check, Stream gotcha

October 1, 2017

Recently I came across a rather simple and innocent looking question which highlighted an issue you might run into when using Streams.
The question was: how could you decide if a number is a power of two?
If you are interested only in the possible issue, jump to the gotcha.

Possible solutions

Division by two

The first solution which might come to mind is rather simple: start dividing the number with 2 and check the reminder. If it is 0, then keep dividing, if it is not 0, then return false. If we can keep dividing the number until we get to 1, then it is a power of two.

public static boolean withDivideByTwo(int x){
  while(x % 2 == 0 && x > 1){
    x /= 2;
  }
  return x == 1;
}

Comparing to numbers which are power of two

Since there is only a finite number of integers which are power of two, we can simply collect such numbers and compare the parameter to these numbers. Of course this only works because of the limitation of the numbers an integer can represent.

public static boolean withPregeneratedPowerOfTwo(final int x){
  return (x == 1 || x == 2 || x == 4 || x == 8 || x == 16 || x == 32 ||
          x == 64 || x == 128 || x == 256 || x == 512 || x == 1024 ||
          x == 2048 || x == 4096 || x == 8192 || x == 16384 ||
          x == 32768 || x == 65536 || x == 131072 || x == 262144 ||
          x == 524288 || x == 1048576 || x == 2097152 ||
          x == 4194304 || x == 8388608 || x == 16777216 ||
          x == 33554432 || x == 67108864 || x == 134217728 ||
          x == 268435456 || x == 536870912 || x == 1073741824);
}

Checking the binary representation

Since a number which is a power of two contains only one 1 in it’s binary representation, we can use the Integer.toBinaryString method:

public static boolean withBinaryRepresentation(final int x){
  return Integer.toBinaryString(x).matches("0*10*");
}

Since this involves creating a String and then using a regexp this will be probably slower than the other solutions, so we can check the number of zeros in the number, since integers are always represented with 32 bits.

public static boolean withLeadingAndTrailingZeros(final int x){
  return Integer.numberOfLeadingZeros(x) + Integer.numberOfTrailingZeros(x) == 31;
}

Decrement and compare

This one-liner could be familiar to people who used to work with C, a similar code was used in the malloc.c:

public static boolean withDecreaseAndCompare(final int x){
  return ((x != 0) && (x & (x - 1)) == 0);
}

It seems a bit complicated, but if you recall binary subtraction it will be easier to understand: the x != 0 is a necessary check since the second half only works with positive integers. If x is a power of two, that means it has only one 1 in its binary representation. Let’s say that this single 1 is at position n, this means that there are n-1 zeros before it. If you subtract 1 from x, then at the position n you will have a 0 and all the n-1 bits before it turn into 1. This would mean that x and x-1 has no 1 at the same position and we can check this with a bitwise and operator.

Gotcha: Generating the numbers which are power of two with a Stream

Remember the solution where we hardcoded in an if statement the numbers which were power of two? How about using a Stream which starts at 1 and to get the next element we multiply by 2 while the number is smaller than x? Seems straightforward with the new iterate method in Java 9, but this will result in an infinite loop if x is not a power of two:

public static boolean withGeneratingPowerOfTwoStream(final int x){
  return IntStream.iterate(1, i -> i < x, i -> i *= 2)
    .filter(value -> value == x)
    .findFirst()
    .isPresent();
}

Your first reaction might be to blame the stream for some weird issue, so what happens when we rewrite it to a regular while loop? Damn, it is still an infinite loop:

public static boolean withGeneratingPowerOfTwoWhileLoop(final int x){
  int powerOfTwo = 1;

  while (powerOfTwo < x) {
    powerOfTwo *= 2;
  }

  return (x == powerOfTwo);
}

Why? Short answer: the built-in integer operators do not indicate an overflow or underflow in any manner. So what happens if x is not a power of two that i gets multiplied by two until it reaches 1,073,741,824, then when it gets multiplied by two, it will overflow and you will get -2,147,483,648 which is Integer.MIN_VALUE. Then this gets multiplied by two which will result in 0 and then it will keep multiplying 0 with 2.
Because of this we need to check if an overflow happened:

public static boolean withGeneratingPowerOfTwoStream(final int x){
  return IntStream.iterate(1, i -> (i < x && i != Integer.MIN_VALUE), i -> i *= 2)
    .filter(value -> value == x)
    .findFirst()
    .isPresent();
}

Or with a regular while loop:

public static boolean withGeneratingPowerOfTwo(final int x){
  int powerOfTwo = 1;

  while (powerOfTwo < x && powerOfTwo != Integer.MIN_VALUE) {
    powerOfTwo *= 2;
  }

  return (x == powerOfTwo);
}

Benchmark

Let’s see how to different solution perform when we check 1 million randomly generated integers with them. The random integer generation happens the same way as I did in this post.

Benchmark                                           Mode  Cnt  Score    Error  Units
PowerOfTwo.withBinaryRepresentation                 avgt    5  0.331 ±  0.025   s/op
PowerOfTwo.withDecreaseAndCompare                   avgt    5  0.002 ±  0.001   s/op
PowerOfTwo.withDivideByTwo                          avgt    5  0.012 ±  0.001   s/op
PowerOfTwo.withGeneratingPowerOfTwoWhileLoop        avgt    5  0.027 ±  0.001   s/op
PowerOfTwo.withGeneratingPowerOfTwoStream           avgt    5  0.115 ±  0.001   s/op
PowerOfTwo.withLeadingAndTrailingZeros              avgt    5  0.002 ±  0.001   s/op
PowerOfTwo.withPregeneratedPowerOfTwo               avgt    5  0.009 ±  0.001   s/op

Conclusion

There are two things which you should take from this post:
1. Sometimes it is worth considering lower level concepts, such as how the primitive data type are represented in the JVM
2. Streams just like loops can result in infinite processing, so always try to understand when and why they will terminate when you expect them to terminate

András Döbröntey

About the Author

András Döbröntey

Leave a Comment:

Bitnami