How many Java programmers does it take to round up to a power of two?

Re:How many Java programmers does it take to round up to a p... by tallpapab on Friday November 02, 2007 @03:04PM (#75542)

You have an infinite loop when i < 2^30.

  static int nextOne(int theInt) {
    int answer = 1;
    while (answer < theInt && 0 < answer) {
      answer <<= 1;
    }
    if (answer < 1) {
      throw new IllegalArgumentException("Sorry, " +
        theInt + " is bigger than 2 to the power of 30 (1073741824).");
    }
    return answer;
  }

[ Parent | on HN ]

Re:How many Java programmers does it take to round up to a p... by gojomo on Friday November 02, 2007 @04:14PM (#75573)

Good point. (And, as your signature indicates, this is more likely to be a static utility method.)

If I were defensively programming against unanswerable input, I'd tend towards failing fast with a single early check:

 static int roundUpToPowerOfTwo(int i) {
  if(i>(1<<30)) throw new IllegalArgumentException("Answer overflows int");
  int rounded = 1;
  while(rounded<i) rounded <<= 1; 
  return rounded;
 }

If we needed to give answers for any size integer (or at least up to 2^(2^31-1)), we could use BigInteger, whose #bitLength method is useful:

  static BigInteger roundUpToPowerOfTwo(BigInteger i) {
   return BigInteger.ONE.shiftLeft(i.subtract(BigInteger.ONE).bitLength());
  }

And if we weren't being literal-minded about the original request, it might make sense to just return the exponent rather than the power-of-2 itself, and let the caller worry about overflows:

 static int ceilLog2(long val) {
  return BigInteger.valueOf(val-1).bitLength();
 }

Of course we are ignoring negative exponents, in the integer spirit of the original question.

There, is it done to death yet? :)

[ Parent | on HN ]