Why is `23` equals to `10111` in binary

Question

I've tried to convert 23 to binary and came up with the number 100111 by using the calculation inspired by this answer:

1) Find out the least significant bit:

$$ 23 = \underbrace{(e_n\times 2^n + ... + e_1\times 2^1)}_{22} + 1\times2^0 $$

Which is 1 here. Continue by shifting to the left by dividing by 2:

2) 22/2 = 10 + 1 // next bit is 1
3) 10/2 = 4 + 1 // next bit is 1
4) 4/2 = 2 + 0 // next bit is 0

So I'm left with the 2 in decimal, which is 10 in binary. Now I'm writing down the number:

10 plus the the bits from the operations 4, 3, 2, 1 gives me 100111, however, the answer is 10111. Where is my mistake?

Answer 1

Let's start with some powers of $2$:

• $2^0 = 1$
• $2^1 = 2$
• $2^2 = 4$
• $2^3 = 8$
• $2^4 = 16$
• $2^5 = 32$

We need to write out $23$, so this is enough powers of $2$.

Start with the highest power of $2$ that is equal to or less than the number. This is $16$. So write a $1$ down and subtract it out: $23-16 = 7$.

The next highest power, $8$, is greater than $7$, so write a zero: $10$.

The next one, $4$, is not greater than $7$, so subtract it out ($7-4=3$) and write a $1$: $101$.

The next one, $2$, is not greater than $3$, so subtract it out ($3-2=1$) and write another $1$: $1011$.

The last one, $1$, is not greater than $1$, so subtract it out ($1-1=0$) and write a $1$: $10111$, and we're done.

Answer 2

I've decided to write down the number in the following form:

$$ 2\times(2\times(2\times(1\times2^1+0\times2^0)+1\times2^0)+1\times2^0)+1\times2^0 $$

And from this form it's clear that there are only 4 steps needed, so:

1) 23 = 22 + 1 // the first bit is 1
2) 22/2 = 10 + 1 // next bit is 1
3) 10/2 = 4 + 1 // next bit is 1
4) 4/2 = 2 + 0 // here, `2 + 0` can be represented as:

$$ (1\times2^1+0\times2^0) $$ so, I have two required bits here - 10, and then I add bits from the previous steps and get the correct result 10111. It seems that I need to divide by 2 until the quotient has no powers of 2 greater than 1.

It is also possible to have the fifth step in the calculations and then the number would look like this:

$$ 2\times(2\times(2\times(2\times(0\times2^1 + 1\times2^0)+0\times2^0)+1\times2^0)+1\times2^0)+1\times2^0 $$

In this way I need to continue dividing until no powers of 2 remain.