Linux with Operating System Concepts

x
i
i
i
0
7
2
*
This formula says to sum the products of x
i
*2
i
for each i from 0 to 7. What is x
i
and what 
is 2
i
? The value x
i
is the ith bit of the number, where x
7
is the leftmost bit and x
0
is the right-
most bit. For instance, the number 11001010
2
will have x
7
=
1, x
6
=
1, x
5
=
0, x
4
=
0, x
3
=
1, 
x
2
=
0, x
1
=
1, x
0
=
0. The value 2
i
is the value 2 raised to the power i, or the ith value in the 
sequence of the powers of 2. If you are not familiar with powers of 2, you can get the values 
from Table A.1.
Now that we have explained the formula, let us apply it and convert 11001010
2
to decimal.
11001010
2
=
1*2
7
+
1*2
6
+
0*2
5
+
0*2
4
+
1*2
3
+
0*2
2
+
1*2
1
+
0*2
0
=
1*128 
+
1*64 
+
0*32 
+
0*16 
+
1*8 
+
0*4 
+
1*2 
+
0*1
=
128 
+
64 
+
8 
+
2 
=
202
We can simplify this formula by noting that 0*a number 
=
0. Thus, we can eliminate any 
of the 0 digits. Redoing our conversion, we have 11001010
2
=
1*2
7
+
1*2
6
+
1*2
3
+
1*2
1
=
20
2. We could even eliminate the 1 bits because 1*a number is that number. In this case, we 
see that 1*2
7
is 2
7
, 1*2
6
is 2
6
, and so on. So, we perform our conversion by adding powers of 
2 for the columns in the binary number that contain a 1. This gives us 11001010
2
=
128 
+
64 
+
8 
+
2 
=
202.
Let us try a few more:
• 00011101
2
=
0*2
7
+
0*2
6
+
0*2
5
+
1*2
4
+
1*2
3
+
1*2
2
+
0*2
1
+
1*2
0
=
16 
+
8 
+
4 
+
1 
=
29
• 00001111
2
=
8 
+
4 
+
2 
+
1 
=
15
• 10101010
2
=
128 
+
32 
+
8 
+
2 
=
170
• 11111111
2
=
128 
+
64 
+
32 
+
16 
+
8 
+
4 
+
2 
+
1 
=
255
• 00000011
2
=
2 
+
1 
=
3
If we are going to convert values larger than 8 bits, we have to extend our formula by 
increasing the upper limit for i. If the value is a 16-bit number, we sum up x
i
*2
i
for i between 
0 and 15. Unfortunately, Table A.1 does not extend beyond i 
=
10 but you should have little 
difficulty extending the table yourself. For instance, for i 
=
11, 2
i
=
2*1024 
=
2048. Can you 

---

Appendix
◾
635
figure out 2
i
for i 
=
12, 13, 14, and 15? This question is given as a review problem at the end 
of the appendix.
Another way to cope with computing a power of 2 where i is greater than 10 is to use 
some algebra. In algebra, we learn that 2
x
+
y
=
2
x
*2
y
. This looks horribly abstract, how is it 
useful? Let us look at an example. We want to determine what 2
15
is. Since 15 
=
5 
+
10, 
2
15
=
2
5
*2
10
. How does this help us? Well, 2
5
and 2
10
are in Table A.1. Looking these up, we 
see that the two values are 32 and 1024, respectively. So, 2
15
=
32*1024.
Although 32*1024 looks like a challenge to compute, it really is not once we realize that 
1024 is equal to 1K. So 2
15
=
32*1K 
=
32K. Now that we know this handy little algebraic 
formula, we can put it to use with one more piece of useful information. It turns out that all 
of the powers of 2 where i is a multiple of 10 (10, 20, 30, 40, etc.) have handy abbreviations. 
We see this in Table A.2.
Given Tables A.1 and A.2, we should be able to determine any power of two up through 
2
69
. Let us see a few examples.
• 2
19
=
2
9
*2
10
=
512*1K 
=
512K (roughly 512 thousand)
• 2
22
=
2
2
*2
20
=
4*1M 
=
4M (roughly 4 million)
• 2
36
=
2
6
*2
30
=
64*1G 
=
64G (roughly 64 billion)
• 2
58
=
2
8
*2
50
=
256*1P 
=
256P (over 256 quadrillion)
Let us put this together and convert a 16-bit binary number into decimal. We will use the 
number 0101010101010101
2
. Ignoring the 0s in the binary number, we have 2
14
+
2
12
+
2
10
+
2
8
+
2
6
+
2
4
+
2
2
+
2
0
=
2
4
*2
10
+
2
2
*2
10
+
2
10
+
2
8
+
2
6
+
2
4
+
2
2
+
2
0
=
16*1024 
+
4*1024 
+
1024 
+
256 
+
64 
+
16 
+
4 
+
1 
=
16384 
+
4096 
+
1024 
+
256 
+
64 
+
16 
+
4 
+
1 
=
21845.
How about converting from decimal into binary? There are two different algorithms 
used for this conversion. One uses division by 2 and one uses subtraction. People will favor 
one or the other based on whichever is easier for them to perform. The division approach 
is the more common version.
The first algorithm requires dividing the original decimal number by 2 and recording 
both the quotient and remainder. You repeat this on the quotient from the most recent 
division until the quotient is 0. The binary number is then the remainder in the opposite 
order of what was recorded.
TABLE A.2 
Large Powers of 2