Integers on Computer

Integers are stored in binary format. Integer types in the C language come in different sizes. On our computer we have:

char          8 bits
short        16 bits
int          32 bits
long         64 bits

We can also add the word unsigned before each type. Example: the definition

unsigned char x;

tells the C compiler to treat the 8 bits as a positive number. If we leave off the word unsigned then by default each type is signed. This means some of the bit patterns stored in the variable will treated as positive and some will be treated as negative. How are negative numbers stored? There is no negative sign! The only thing stored are bits (0 or 1). The rule: if the number is signed AND the left-most bit is 1, then the number is negative. Note the left-most bit is called the leading bit.

Two's Complement Format.

Signed positive numbers have leading bit equal to zero. We can find the value of a positive number by converting it as talked about on the previous page. For instance, consider the char

00101110

So the decimal equivalent is

32+8+4+2 = 46

Now consider the char

11010010

This has the decimal value -46. You can check this by doing binary addition:

 11010010
+00101110      
---------
100000000

Since a char is only 8 bits, the carry out from the 8th column, the 1, is lost and we are left with 8 zero bits. Since the second bit pattern represents the number 46, the first bit pattern represents the number -46! We say that these two bit patterns are twos complements of each other because they add to zero. This works for the other sizes of integers too. Let's work some more examples.

Problem: Given the char bit pattern 10001101, what decimal number is it?

The number is negative because its type is signed (default) and the leading bit is 1. Strategy: Compute the twos complement. Find its decimal value. Then put a minus in front.

The twos complement is a bit pattern that added to the given one makes zeros.

 10001101
+????????
---------
 00000000

Working from right to left. We need to get a 0 in the right-most column of the result:

 10001101
+       ?
---------
        0

The question mark above is either 0 or 1. The 0 does not work. The 1 gives us 1+1 which is 10 in binary. The 0 is written down and the 1 is carried:

       1
 10001101
+      ?1
---------
        0

We are now working on the second column. We need two 1's in the second column to get the result 10. Since we already have one 1, we make the question mark above a 1 to get two 1's. Now we have:

      11
 10001101
+     ?11
---------
       00

In the third column we already have two 1's so we make the question mark above be a 0. So the result is 10 and we have a carry of 1 into the fourth column:

     111
 10001101
+    ?011
---------
      000

We continue:

    1111       11111     111111    1111111    1111111
 10001101    10001101   10001101   10001101   10001101
+   ?0011   +  ?10011  + ?110011  +?1110011  +01110011
---------   ---------  ---------  ---------  ---------
     0000       00000     000000    0000000   00000000

So the twos complement is 01110011. This is a positive number. We convert to decimal: 64+32+16+2+1 = 115. So our original number has a decimal value of -115.

Problem: a char value has a bit pattern of 11110000, what is its decimal value? First the number is negative because it is signed and the leading bit is 1. So we find the twos complement:

 11110000
+????????
---------
 00000000

The right-most 4 question marks are zeros:

    0
 11110000
+   ?0000
---------
    00000

The question mark above must be a 1 to get a 10 result.

   10         110        1110
 11110000    11110000    11110000     11110000
+  ?10000   + ?010000   +?0010000    +00010000
---------   ---------   ---------    ---------
   000000     0000000    00000000     00000000

So the twos complement is 00010000 which is 16 in decimal. So the decimal value of the original number is -16.

Problem: Given the decimal number -94. Find the signed char bit pattern for the number. We'll do this in two steps: we will get the bit pattern for 94, then we'll take the twos complememt of that pattern. So 94 = 64+16+8+4+2 so the 8-bit pattern is:

01011110

Now we find the twos complement as before. The result is

10100010

This is the bit pattern for -94.

next: Bit Operations