3
$\begingroup$

I am aware that you can keep dividing a decimal number by two, finding the remainders in the process, in order to convert the number to binary.

However, when I am working with a long decimal number such as 2147483647, is there any easier way of converting this to binary? Manually dividing this number by two repeatedly would take an entire page of long division to do, and human error is likely.

Thanks in advance.

EDIT: SOLUTION. Thanks to the help I received from joriki and pjs36 I discovered that instead of dividing by 2 I can divide by 16. Where dividing by two will give you binary as a result, dividing by 16 will give you hex as a result. This hex value can then be converted easily to binary , and is is a much shorter process that dividing by 2.

$\endgroup$
  • 1
    $\begingroup$ You just need a list of powers of $2$ and subtraction, probably much simpler than division. $\endgroup$ – pjs36 Aug 18 '15 at 16:05
  • $\begingroup$ It's not too hard to divide things by two, without long division. $\endgroup$ – Akiva Weinberger Aug 18 '15 at 17:39
4
$\begingroup$

To expand on my comment: Let's say we want to convert $409$ to binary. We first need to know how many bits we'll need; we need to know the largest power of $2$ that's less than $409$. We'll also need all smaller powers of $2$, so let's write those down (they are all very easy to calculate by hand).

\begin{array}{c|c|c|c|c|c} k & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 \\\hline 2^k &256 & 128 & 64 & 32 & 16 & 8 & 4 & 2 & 1 \end{array}

So we'll need $9$ bits. To find them, we essentially subtract the largest power of $2$ from our remainders, repeatedly (for example, $409 - 256 = 153$): \begin{align*} 409 &= 256\cdot 1 + 153 \\ 153 &= 128 \cdot 1 + 25 \\ 25 &= 16 \cdot 1 + 9 \\ 9 &= 8 \cdot 1 + 1 \\ 1 &= 1 \cdot 1 \end{align*}

Since we saw $256,\ 128,\ 16,\ 8,$ and $1$ show up in the process, we have $$409_{10} = 110011001_2.$$

Of course, for a number like yours, we would need many more powers of $2$, in general.

But! It just so happens that $2147483647 = 2^{31} - 1$, and its binary representation is literally $$2147483647_{10} = \underbrace{111\ldots 1_2}_{31\text{ times}}$$ (try smaller numbers that are one less than a power of $2$, like $7, 15, 31$, and you'll see the pattern).

$\endgroup$
2
$\begingroup$

You can convert to a different power-of-two base, e.g. octal or hexadecimal, first. That's $3$ or $4$ times fewer divisions, and then you can very quickly convert to binary using a lookup table for the octal or hexadecimal digits.

$\endgroup$
0
$\begingroup$

Here is a 'color-coded' algorithm converting $409$ to binary representation and each step can be easily checked to minimize the chance of human error:

enter image description here

The binary representation for $409$ is obtained by taking the green binary digits in the last row and putting them in reverse order,

$\quad 409 = 110011001_{\,\text{Base-}2}$

Observe that this string processing algorithm can be applied to any integer using only a finite number of arithmetic rules that can be hard-coded into the logic. For example, the largest integer that will ever be divided by $2$ is $18$.

An implementation of this algorithm can be found here.

$\endgroup$
0
$\begingroup$

I felt using the remainder method is quite easy for me. if u got a remainder with decimal when divided with 2 it should be considered a 1 in bitstring and if the remainder doesn't have a decimal it is a 0 bitstring.

then u read from top to bottom as the right to left. i.e 110011001

  • 409/2 = 204.5 - 1
  • 204/2 = 102 - 0
  • 102/2 = 51 - 0
  • 51/2 = 25.5 - 1
  • 25/2 = 12.5 - 1
  • 12/2 = 6 - 0
  • 6/2 = 3 - 0
  • 3/2 = 1.5 - 1
  • 1/2 = 0.5 - 1
$\endgroup$

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.