Guava: Add *Math.nextPowerOfTwo

[ghost]

There are existing *Math.isPowerOfTwo methods, it seems like a nextPowerOfTwo method is a good method to go alongside it, to return the smallest integer >= n that is a power of two (I was surprised this doesn't exist in guava already, TBH)

This is a simple operation that has a wide range of applications (sizing buffers, primarily, but it also has uses in collection implementations etc), and it's not immediately obvious what the bit-twiddling algorithm is doing when it appears in a codebase. Would seem like a prime candidate for an addition to guava.

There's a simple bit-twiddling algorithm for ints & longs; doubles & bigintegers can probably use a combination of the existing log, floor & pow methods, unless there are clever ways of doing the same for those types (also see http://stackoverflow.com/questions/466204/rounding-up-to-nearest-power-of-2)

[ogregoire]

return Integer.highestOneBit(n) << 1 ?

[ghost]

When n is already a power of two, this will return the next highest one (I want >=, not >). Admittedly, this can be solved using a check for IntMath.isPowerOfTwo, but it's still not exactly obvious. There is a related method BigInteger.bitLength that can be used for bigintegers, but nothing for doubles that I can see...

[ogregoire]

Well, if I have int n = 4; and I call int x = Blah.nextPowerOfTwo(n), I logically expect that x == 8. Because "next", to me, means "not this one, but the one after".

[ben-manes]

A simple version of that is below, which is what I use. As its a one-liner I put the method in the class since its only rarely needed.

static int ceilingNextPowerOfTwo(int x) {
  // From Hacker's Delight, Chapter 3, Harry S. Warren Jr.
  return 1 << (Integer.SIZE - Integer.numberOfLeadingZeros(x - 1));
}

[tworec]

+1 :)

[ogregoire]

With Ben's insight, you can still write:

return Integer.highestOneBit(n - 1) << 1;

Note the n - 1.

[tworec]

doesn't work for n <= 0

[ogregoire]

Powers of two are positive, it makes no sense to use negative values...

[tworec]

but your code returns 0 for 0 and all negative integers, and should return 1

[lowasser]

If we were to implement this, then we'd almost certainly just throw on
negative input rather than guessing at what behavior is "most sensible."

On Wed, Jan 27, 2016 at 7:37 AM Piotr Chromiec [email protected]
wrote:

but your code returns 0 for 0 and all negative integers, and should return
1

—
Reply to this email directly or view it on GitHub
https://github.com/google/guava/issues/2370#issuecomment-175692420.

[tworec]

If this is purpose (as @simonmcooper originallly wrote)

nextPowerOfTwo
return the smallest integer >= n that is a power of two

than you should return at least 1 for all inputs (or throw)
see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2Float

[leventov]

Strange that this is not in Guava

[ben-manes]

Are you looking for IntMath#ceilingPowerOfTwo(x)? I think it was implemented due to this issue, but accidentally not closed.

[leventov]

@ben-manes thank you. Google (the search engine, not the company) is somehow bad at finding methods in published Guava's Javadocs.