8
\$\begingroup\$

Here is one of the possible solutions:

  public static int getNextPowerOfTwo(int value) {
    int result = value;
    result -= 1;
    result |= result >> 16;
    result |= result >> 8;
    result |= result >> 4;
    result |= result >> 2;
    result |= result >> 1;
    return result + 1;
}

As in your opinion is it good enough or may you suggest better one?

\$\endgroup\$
  • \$\begingroup\$ I don't get the reason for subtracting 1 (in the beginning) then adding 1 again in the end. Wouldn't the result be the same if one leaves that away? Just using right shift and or ... Have tried it out with a few numbers and get correct results anyway. What's the reason for the subtracting / adding. I'm dying for curiosity. \$\endgroup\$ – michael.zech Mar 15 '17 at 14:28
9
\$\begingroup\$

Java has Integer.highestOneBit that can make this a bit simpler:

int highestOneBit = Integer.highestOneBit(value);
if (value == highestOneBit) {
    return value;
}
return highestOneBit << 1;
\$\endgroup\$
  • \$\begingroup\$ Thanks, @janos! Integer.highestOneBit looks very simillar to my version. \$\endgroup\$ – Nolequen Mar 11 '17 at 9:54
6
\$\begingroup\$

Your function is misleadingly named. It rounds up to the nearest power of 2 rather than "getting the next power of 2". The difference has led @janos to suggest an answer with an off-by-one error (i.e. an off-by-a-factor-of-2-error when the input is already a power of 2).

\$\endgroup\$
5
\$\begingroup\$

Minor suggestion:

As you do not mutate the parameter value, you can consider marking it final to indicate to the user that the parameter is not changed. However, as value is of type int, which is passed by value, not by reference, you can mutate it within your method without affecting the argument, in which case, you may choose to eliminate the result variable.

Overall, my suggestion is either:

public static int getNextPowerOfTwo(final int value) {
    int result = value - 1;// note - you don't need to do this in 2 steps
    result |= result >> 16;
    result |= result >> 8;
    result |= result >> 4;
    result |= result >> 2;
    result |= result >> 1;
    return result + 1;
}

or,

public static int getNextPowerOfTwo(int value) {
    value -= 1;
    value |= value >> 16;
    value |= value >> 8;
    value |= value >> 4;
    value |= value >> 2;
    value |= value >> 1;
    return value + 1;
}

You have an unrolled loop, which is good for performance (especially because in Java the size of an int is fixed to be 32 bits). However, you could consider turning it into a loop if this performance is not required, that would reduce code duplication. Which means that you could also try:

public static int getNextPowerOfTwo(int value) {
    value -= 1;
    for( int shift = 16; shift > 0; shift >>= 1) {
        value |= value >> shift;
    }
    return value + 1;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.