How many Java programmers does it take to round up to a power of two? | Hacker News Reader

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

forum.java.sun.com

22 pointsnickb11 comments

Funny thread! :)

I guess the thing here is that bit operators are not really "in you face" in Java. If you are programming in assembler, or even C, bits will be what you know. Programming at a higher level, you may not be that aware of bit functions and how to use them in real life. You should, but many are not.

The second approach by gojomo here is neat and effective and works directly at the bits instead of bloating with creating Strings and other objects for this simple task. So it's not the fault of the tool, it about the abstraction level people are thinking in.

What are the bit operators in Common Lisp? My google-fu fails me...

CL has logand, logior, logxor, lognot, etc. It also has a parameterized version, boole http://www.lisp.org/HyperSpec/Body/fun_boole.html

http://pastie.caboo.se/113312

float precision issues make me nervous (although it's probably ok here), not to mention log() is kind of expensive compared to bit shifting

why not just something like

def fn(n): ret=1; while ret < n: ret <<= 1; return ret

(news.yc/browsers mangle whitespace; proper formatting is left as an exercise to the reader)

To format code, add a whole bunch of returns and then indent 4-5 spaces

      (5 returns and 6 spaces later
          whitespace does what I want)

I think it's supposed to be 4 and 4, but I had some issues once and since then I just pile on returns and spaces until I get bored.

I thought it's 2 and 1:

 print 'Hello world'

Yup, that's it. A blank line before the indented block, then any amount of indentation.

Reddit is 2 and 4.

You could use that approach in Java...

 public int roundUpToPowerOfTwo(int i) {
  return 1 << (int)(Math.ceil(Math.log(i)/Math.log(2)));
 }

...but the first approach that occurred to this Java coder was instead...

 public int roundUpToPowerOfTwo(int i) {
  int rounded = 1;
  while(rounded<i) rounded <<= 1; 
  return rounded;
 }

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;
  }

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? :)

Here is a mediocre lisper and an advanced lisper's take on the question (edit: and also another lisper's take, too):

http://lispy.wordpress.com/2007/11/02/my-solution-to-the-rou...

Reply on news.ycombinator.com