How do I calculate the closest power of 2 or 10 a number is?

Question

What is the most efficient way to cacluate the closest power of a 2 or 10 to another number? e.g.

3.5 would return 4 for power of 2 and 1 for power of 10

123 would return 128 for power of 2 and 100 for power of 10

0.24 would return 0.25 for power of 2 and 0.1 for power of 10

I'm just looking for the algorithm and don't mind the language.

Answer 1

n^round(log_n(x))

where log_n is the logarithm to base n. You may have to modify the round() depending on how you define "closest".

Note that log_n(x) can be implemented as:

log_n(x) = log(x) / log(n)

where log is a logarithm to any convenient base.

Answer 2

I think that I might approach the problem, but using log base 2 and log base 10.

log10 of (123) is 2.something. take the floor of that then raise 10 to that power, and that ought to get you close.

the same thing ought to work with log base 2.

log2 of (9) is 3.something take the floor of that then raise to to that power

you might play with rounding of the log.

Answer 3

For power of 2 and >= 1 you can see how many times you can bit shift right. For each time this is 1 extra power of 2 you are taking away. Once you get down to 0 you have your number.

Answer 4

For power of 2 on integers, there is a smart trick that consist of copying the last bit over and over to the right. Then, you only have to increment your number and you have your power of 2.

int NextPowerOf2(int n)
{
   n |= (n >> 16);
   n |= (n >> 8);
   n |= (n >> 4);
   n |= (n >> 2);
   n |= (n >> 1);
   ++n;
   return n;
}

Answer 5

You may have to modify the round() depending on how you define "closest".

@Greg Hewgill's answer is correct except it rounds up too early for the examples you gave. For example, 10^round(log_10(3.5)) == 10, not 1. I'm assuming that's what he means by 'how you define "closest"'.

Probably the simplest way to use Greg's formula and if it's too high (or too low for x < 1), use the next lower power of two:

closest = n ^ round(log_n(x))

if (closest > x) {
    other = closest / n
} else {
    other = closest * n
}

if (abs(other - x) < abs(closest - x)) {
    return other
} else {
    return closest
}