# Rounding logarithm to next integer — Potential function

The problem is IV-3 of this pdf: potential function.

Defining a potential function as $\Phi(i) = 2i - 2^{\lfloor{\log_2i}\rfloor+1} + 1$

The solution states that if $i$ is not an exact power of $2$, we have:

$$\Phi(i) = 2i - i + 1 .$$

This means that $2^{\lfloor{\log_2i}\rfloor+1} = i$. I'm having some trouble understanding this equality.

Can somebody shed some light?

• This equation doesn't hold. You can try it with $i=3$, for example: $2^{\lfloor \log_23 \rfloor+1} = 2^{1+1} = 4$. – Yuval Filmus Mar 26 '17 at 15:58

1. $i$ is not a power of 2. In that case $\lfloor \log_2 i \rfloor = \lfloor \log_2 (i-1) \rfloor$ and so $\Phi(i) - \Phi(i-1) = (2i+1) - (2(i-1)+1) = 2$.
2. $i$ is a power of 2. In that case $2^{\lfloor \log_2 i \rfloor} = i$ and $2^{\lfloor \log_2 (i-1) \rfloor} = i/2$, and so $\Phi(i) - \Phi(i-1) = (2i - 2i + 1) - (2(i-1) - i + 1) = 2-i$.
• Just a small correction, the last result should be $-i + 2$ – joaoaccarvalho Mar 26 '17 at 17:33