Decimal to Binary
Converting from decimal to binary notation is slightly more difficult conceptually, but can easily be done once you know how through the use of algorithms. Begin by thinking of a few examples. We can easily see that the number 3= 2+1. and that this is equivalent to (1*2^1)+(1*2^0). This translates into putting a "1" in the 2^1 column and a "1" in the 2^0 column, to get "11". Almost as intuitive is the number 5: it is obviously 4+1, which is the same as saying [(2*2) +1], or 2^2+1. This can also be written as [(1*2^2)+(1*2^0)]. Looking at this in columns,
2^2 | 2^1 | 2^0
1 0 1
or 101.
What we're doing here is finding the largest power of two within the number (2^2=4 is the largest power of 2 in 5), subtracting that from the number (5-4=1), and finding the largest power of 2 in the remainder (2^0=1 is the largest power of 2 in 1). Then we just put this into columns. This process continues until we have a remainder of 0. Let's take a look at how it works. We know that:
2^0=1
2^1=2
2^2=4
2^3=8
2^4=16
2^5=32
2^6=64
2^7=128
and so on. To convert the decimal number 75 to binary, we would find the largest power of 2 less than 75, which is 64. Thus, we would put a 1 in the 2^6 column, and subtract 64 from 75, giving us 11. The largest power of 2 in 11 is 8, or 2^3. Put 1 in the 2^3 column, and 0 in 2^4 and 2^5. Subtract 8 from 11 to get 3. Put 1 in the 2^1 column, 0 in 2^2, and subtract 2 from 3. We're left with 1, which goes in 2^0, and we subtract one to get zero. Thus, our number is 1001011.
Making this algorithm a bit more formal gives us:
- Let D=number we wish to convert from decimal to binary
- Repeat until D=0
- a. Find the largest power of two in D. Let this equal P.
- b. Put a 1 in binary column P.
- c. Subtract P from D.
- Put zeros in all columns which don't have ones.
This algorithm is a bit awkward. Particularly step 3, "filling in the zeros." Therefore, we should rewrite it such that we ascertain the value of each column individually, putting in 0's and 1's as we go:
- Let D= the number we wish to convert from decimal to binary
- Find P, such that 2^P is the largest power of two smaller than D.
- Repeat until P<0
- If 2^P<=D then
- put 1 into column P
- subtract 2^P from D
- Else
- End if
- Subtract 1 from P
Now that we have an algorithm, we can use it to convert numbers from decimal to binary relatively painlessly. Let's try the number D=55.
- Our first step is to find P. We know that 2^4=16, 2^5=32, and 2^6=64. Therefore, P=5.
- 2^5<=55, so we put a 1 in the 2^5 column:
1-----.
- Subtracting 55-32 leaves us with 23. Subtracting 1 from P gives us 4.
- Following step 3 again, 2^4<=23, so we put a 1 in the 2^4 column:
11----.
- Next, subtract 16 from 23, to get 7. Subtract 1 from P gives us 3.
- 2^3>7, so we put a 0 in the 2^3 column:
110---
- Next, subtract 1 from P, which gives us 2.
- 2^2<=7, so we put a 1 in the 2^2 column:
1101--
- Subtract 4 from 7 to get 3. Subtract 1 from P to get 1.
- 2^1<=3, so we put a 1 in the 2^1 column:
11011-
- Subtract 2 from 3 to get 1. Subtract 1 from P to get 0.
- 2^0<=1, so we put a 1 in the 2^0 column:
110111
- Subtract 1 from 1 to get 0. Subtract 1 from P to get -1.
- P is now less than zero, so we stop.
Another algorithm for converting decimal to binary
However, this is not the only approach possible. We can start at the right, rather than the left.
All binary numbers are in the form
a[n]*2^n + a[n-1]*2^(n-1)+...+a[1]*2^1 + a[0]*2^0
where each a[i] is either a 1 or a 0 (the only possible digits for the binary system). The only way a number can be odd is if it has a 1 in the 2^0 column, because all powers of two greater than 0 are even numbers (2, 4, 8, 16...). This gives us the rightmost digit as a starting point.
Now we need to do the remaining digits. One idea is to "shift" them. It is also easy to see that multiplying and dividing by 2 shifts everything by one column: two in binary is 10, or (1*2^1). Dividing (1*2^1) by 2 gives us (1*2^0), or just a 1 in binary. Similarly, multiplying by 2 shifts in the other direction: (1*2^1)*2=(1*2^2) or 10 in binary. Therefore
{a[n]*2^n + a[n-1]*2^(n-1) + ... + a[1]*2^1 + a[0]*2^0}/2
is equal to
a[n]*2^(n-1) + a[n-1]*2^(n-2) + ... + a[1]2^0
Let's look at how this can help us convert from decimal to binary. Take the number 163. We know that since it is odd, there must be a 1 in the 2^0 column (a[0]=1). We also know that it equals 162+1. If we put the 1 in the 2^0 column, we have 162 left, and have to decide how to translate the remaining digits.
Two's column: Dividing 162 by 2 gives 81. The number 81 in binary would also have a 1 in the 2^0 column. Since we divided the number by two, we "took out" one power of two. Similarly, the statement a[n-1]*2^(n-1) + a[n-2]*2^(n-2) + ... + a[1]*2^0 has a power of two removed. Our "new" 2^0 column now contains a1. We learned earlier that there is a 1 in the 2^0 column if the number is odd. Since 81 is odd, a[1]=1. Practically, we can simply keep a "running total", which now stands at 11 (a[1]=1 and a[0]=1). Also note that a1 is essentially "remultiplied" by two just by putting it in front of a[0], so it is automatically fit into the correct column.
Four's column: Now we can subtract 1 from 81 to see what remainder we still must place (80). Dividing 80 by 2 gives 40. Therefore, there must be a 0 in the 4's column, (because what we are actually placing is a 2^0 column, and the number is not odd).
Eight's column: We can divide by two again to get 20. This is even, so we put a 0 in the 8's column. Our running total now stands at a[3]=0, a[2]=0, a[1]=1, and a[0]=1.
We can continue in this manner until there is no remainder to place.
Let's formalize this algorithm:
1. Let D= the number we wish to convert from decimal to binary.
2. Repeat until D=0:
a) If D is odd, put "1" in the leftmost open column, and subtract 1 from D.
b) If D is even, put "0" in the leftmost open column.
c) Divide D by 2.
End Repeat
For the number 163, this works as follows:
1. Let D=163
2. b) D is odd, put a 1 in the 2^0 column.
Subtract 1 from D to get 162.
c) Divide D=162 by 2.
Temporary Result: 01 New D=81
D does not equal 0, so we repeat step 2.
2. b) D is odd, put a 1 in the 2^1 column.
Subtract 1 from D to get 80.
c) Divide D=80 by 2.
Temporary Result: 11 New D=40
D does not equal 0, so we repeat step 2.
2. b) D is even, put a 0 in the 2^2 column.
c) Divide D by 2.
Temporary Result:011 New D=20
2. b) D is even, put a 0 in the 2^3 column.
c) Divide D by 2.
Temporary Result: 0011 New D=10
2. b) D is even, put a 0 in the 2^4 column.
c) Divide D by 2.
Temporary Result: 00011 New D=5
2. a) D is odd, put a 1 in the 2^5 column.
Subtract 1 from D to get 4.
c) Divide D by 2.
Temporary Result: 100011 New D=2
2. b) D is even, put a 0 in the 2^6 column.
c) Divide D by 2.
Temporary Result: 0100011 New D=1
2. a) D is odd, put a 1 in the 27 column.
Subtract 1 from D to get D=0.
c) Divide D by 2.
Temporary Result: 10100011 New D=0
D=0, so we are done, and the decimal number 163 is equivalent to the binary number 10100011.
Since we already knew how to convert from binary to decimal, we can easily verify our result. 10100011=(1*2^0)+(1*2^1)+(1*2^5)+(1*2^7)=1+2+32+128= 163.
ref:
http://www.math.grin.edu/~rebelsky/Courses/152/97F/Readings/student-binary
wanna practice what you learnt? try: TCHS SRM 27 250 pt: Brick Mystery:
http://community.topcoder.com/stat?c=problem_statement&pm=7331&rd=10651
