Binary expansion, finding the greatest power of $2$ less than a given number

Question

I'm looking to better understand binary for a CS50 problem set. I'm not understanding transferring decimal notation to binary.

For example, use 237. How to find the largest power of $2$ less than $237$?

Answer 1

I'll give you a method and then I'll explain it.

I'll use 237 to demonstrate the method.

Calculate $\log_2{(237)} = 7.88\ldots$ we only care about the first digit as it tells us that $2^7$ is the largest power of 2 smaller than 237.

An explanation of this is that is that the logarithm tells us what we need to take 2 to the power of to get 237. As the result was 7.88\ldots we know that 8 would be too large and 7 too small which implies that the largest power we can take out of 237 without it going negative would be $2^7$.

We can then repeat this

$$237 - 2^7 = 109\\\log_2{(109}) = 6.768\ldots\\ 237 - 2^7 - 2^6 = 45\\ \log_2{(45)} = 5.49\ldots\\ 237 - 2^7 - 2^6 - 2^5 = 13\\ \log_2{(13)} = 3.700\ldots 237 - 2^7 - 2^6 - 2^5 - 2^3 = 5\\ \log_2{(5)} = 2.32\ldots\\ 237 - 2^7 - 2^6 - 2^5 - 2^3 - 2^2 = 1\\ \log_2{(1)} = 0\\ 237 - 2^7 - 2^6 - 2^5 - 2^3 - 2^2 - 2^0 = 0 \implies 237 = 2^7 + 2^6 + 2^5 + 2^3 + 2^2 + 2^0\\ \implies 237 = 11101101 \mbox{ (in binary)}$$

Answer 2

The simplest thing to do, especially from an algorithmic standpoint, is to do successive doubling: if $n$ is the decimal integer to be converted to binary, compute powers of $2$ using a recursive loop, at each step checking the condition that you have not exceeded $n$: So if $n = 237$, then we calculate: $$1, 2, 4, 8, 16, 32, 64, 128, 256.$$ The final value, $256$, exceeds $n$ so we know that $128$ is the largest power of $2$ not exceeding $237$, and that was computed on the $7^{\rm th}$ iteration (the initial starting value was $1$). Next, we calculate the difference $$237 - 128 = 109,$$ and again we do the doubling and lookup. The whole algorithm stops when the calculated difference is zero.

---

Note that I do not presume to use any logarithms as the purpose of this exercise is to convert base 10 into base 2, which is presumably more elementary than calculating a logarithm, thus we should have a way to do it with basic arithmetic operations.

As an instructive exercise, you may want to calculate the average running time of this algorithm, and the worst-case scenario running time.