1

I am struggling to understand Decimal to Binary using the following method, given on the second last page of http://www.ling.ohio-state.edu/~scott/teaching/2008/spring/384/handouts/decimal-binary.pdf.

Could someone give some maths behind this. I dont really understand how if there is a remainder, after diving a number by $2$, this represent a $1$ in the corresponding bit.

Intuitively to me, it would seem that if a number was divisible (no remainder) by two, then a $1$ should be placed in the corresponding filed.

Thanks.

1 Answers1

8

Every number has a binary representation $$ n = \sum_{i=0}^m b_i 2^i, \qquad b_i \in \{0,1\}, $$ for an appropriate $m$. For example, $$ 10 = 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0. $$ Here are some hints on how the algorithm works:

  1. How can you tell whether $b_0 = 0$ or $b_0 = 1$?
  2. Suppose that $(b_k \cdots b_0)_2$ is the binary representation of some number. What number is represented by $(b_k \cdots b_1)_2$? (e.g. $10 = (1010)_2$, so $(101)_2 = ?$)
  3. How can the foregoing be used to convert a number to binary?
Yuval Filmus
  • 57,157