I have this equation and I've been stuck with it for a couple of hours.

$\lfloor\log_2x\rfloor + 1 = \lceil\log_2(x+1)\rceil$

I've tried using this ceiling property:

$\lceil x\rceil = n \Leftarrow\Rightarrow x\le n\lt x+1$

Which gives me:

$\log_2(x+1)\le\lfloor\log_2x\rfloor + 1 \lt \log_2(x+1)+1$

But then, if I try to use the equivalent property for the floor function or try with the integer floor(x) + fractional part I get confused and I don't know how to proceed.

Thanks for your help!


A good place to start is to observe that $\lfloor \log_2 x \rfloor +1=\lceil \log_2 x \rceil$ unless $x$ is a power of $2$ and that $\lceil \log_2 x \rceil=\lceil \log_2 (x+1) \rceil$ unless ???

  • $\begingroup$ Unless $x$ is between a power of 2 minus 1 and a power of 2. $2^i \lt x \le 2^{i+1} - 1 $ I think. Is it correct? That would be the answer! Thank you! $\endgroup$ – Tlaquetzal Mar 10 '16 at 6:10

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.