Unit 1.2 -- Binary Numbers
Schaum, Chapter 1
SILVER, Section 1.2, 4.1, 4.2
POP pages A-1 to A-4
Algorithm to convert a decimal number to binary:
1) Find the smallest power of two greater than or equal to
the number.
2) For each power of two going down, starting at one found
in step one:
a) if power of two smaller than or equal to number
- subtract power of two from number
- set proper bit of number to one
else
- set to zero
program convert_binary(input,output);
var temp1,n:integer; {number to convert}
i,powerof2:integer;
binary:array[0..31] of boolean; {0 is least significant bit}
begin
{this program will convert a positive integer into binary
purpose is to illustrate algorithm in class}
for i:=0 to 31 do
binary[i]:=false;
write('input integer in decimal to be converted to binary');
writeln;
read(n);
powerof2:=1;
i:=0;
while(powerof2<n) do begin
powerof2:=powerof2*2;
i:=i+1;
end;
temp1:=n;
while(temp10) do begin
if powerof2<=temp1 then begin
binary[i]:=true;
temp1:=temp1-powerof2;
end;
powerof2:=powerof2 div 2;
i:=i-1;
end;
{dump number out}
for i:=31 downto 0 do begin
if binary[i] then
write('1')
else
write('0');
end;
writeln;
end.
Converting a binary number to a decimal:
To understand the binary number system, first let's look at
what a decimal number actually means.
Consider the decimal number 4,687.
Think of it as an array called Num
where the value of Num(0) is 7,
the value of Num(1) is 8,
the value of Num(2) is 6,
and the value of Num(3) is 4.
Now, note that we say
1) Num(0) is in the one's place and that 100 = 1
2) Num(1) is in the ten's place and that 101 = 10
3) Num(2) is in the hundred's place and that 102 = 100
4) Num(3) is in the thousand's place and that 103 =
1,000.
Thus we have,
[100*Num(0)] + [101*Num(1)] + [102*Num(2)] + [103*Num(3)] =
[ 1 * 7 ] + [10 * 8] + [100 * 6] + [1,000 * 4] =
4,687.
The same basic idea works for binary numbers. The only
thing different is that instead of working with 10 and 10
raised to a power, we work with 2 and 2 raised to a power.
(See below.)
Consider the binary number 0111. (0111 in binary = 7 in
decimal)
Think of it as an array called Num
where the value of Num(0) is 1,
the value of Num(1) is 1,
the value of Num(2) is 1,
and the value of Num(3) is 0.
Now, note that we say
1) Num(0) is in the one's place and that 20 = 1
2) Num(1) is in the two's place and that 21 = 2
3) Num(2) is in the four's place and that 22 = 4
4) Num(3) is in the eight's place and that 23 =
8.
Thus we have,
[20*Num(0)] + [21*Num(1)] + [22*Num(2)] + [23*Num(3)] =
[1 * 1] + [2 * 1] + [4 * 1] + [8 * 0] = 7 in
decimal.
Algorithm to add two binary numbers together:
1) Call the rightmost column not yet processed "this
column."
2) Call the top digit "Top Number," the bottom digit
"Bottom Number," and the carried digit "Carry (this
column)."
3) Determine the Result of "this column" and the Carry of
the next column by using the table below. (Read the
table from left to right.)
4) Repeat these steps until the two binary numbers are
added.
Top Bottom Carry Result Carry
Number Number (this (this (next column)
column) column)
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
Examples:
Carries Carries
Will Be: 00000000 Will Be: 00000010
5 = 00000101 5 = 00000101
+ 16 = 00010000 + 17 = 00010001
----------------- -----------------
21 = 00010101 22 = 00010110
Negative Numbers and Subtraction
Negative numbers represented as two's complement.
Algorithm to convert number to two's complement form:
1) invert each bit of item
2) add one
Example:
0000 0000 0001 1010 this is +26 decimal
Invert each bit:
1111 1111 1110 0101
Add one:
1111 1111 1110 0110 this is how -26 is represented in
computer
Algorithm to subtract two binary numbers:
item1
- item2
result
1) invert each bit of item2
2) add one to result of step 1, using binary addition
3) add item1 and result of step 2, using binary addition
In other words, convert item2 into two's complement form and
then add this result to item1.
Negative numbers - 1 in first bit
Positive numbers - 0 in first bit
Integers are usually either stored in
8 bits
16 bits (16 bits = a half word)
32 bits (32 bits = a full word).
In signed arithmetic where no sign bit is kept separately,
a ONE in the LEFTMOST bit position indicates a NEGATIVE
number.
Thus, OVERFLOW occurs either
1) when there IS a carry INTO the leftmost bit
position but there is NO carry OUT, or
2) when there is NO carry INTO the leftmost bit
position but there IS a carry OUT.
Reason the above considered OVERFLOWS:
In 1), it means two positive numbers where added but the
leftmost bit position of the answer turned out to be a one,
thus indicating a negative number answer, which is of course
impossible.
In 2), it means two negative numbers where added but the
leftmost bit position of the answer turned out to be a zero,
thus indicating a positive number answer, which is of course
impossible.
Examples:
Assuming an eight bit machine.
57 0011 1001 35 0010 0011
-35 1101 1101 -57 1100 0111
--------------- ---------------
+22 0001 0110 -22 1110 1010
-57 1100 0111
-35 1101 1101
---------------
-92 1010 0100
+57 0011 1001
+92 0101 1100
--------------
1001 0101 <-- OVERFLOW -- Answer is read to be a
negative number because it starts with a one.
(1001 0101 binary = -107 decimal)
-57 1100 0111
-92 1010 0100
---------------
0110 1011 <-- OVERFLOW -- Answer is read to be a
positive number because it start with a zero.
(0110 1011 binary = 107 decimal)