Chapter 5. Data representation: Integers

Internally, computers represent all data using sequences of bits — pieces of memory that are either 0 or 1. Since integers constitute the most important type of data that a computer manipulates, we should understand how they are represented using bits. Understanding this is helpful in many ways, such as understanding how to manipulate bits directly using the bit operators found in C, Java, and many other programming languages.

In this chapter we'll study both how integers are represented, and we'll learn about how to use the bit operators to manipulate these integers.

5.1. Binary numbers

We can already represent integers from zero to one using a single bit. To represent larger numbers, we need to use combinations of bits. The most convenient technique for assigning values to combinations is based on binary notation (also called base 2).

You're already familiar with decimal notation (also called base 10). You may remember the following sort of diagram from grade school.

That is, in representing the number 1024, we put a 4 in the ones place, a 2 in the tens place, a 0 in the hundreds places, and a 1 in the thousands place. This system is called base 10 because there are 10 possible digits for each place (0 through 9) and because the place values go up by factors of 10 (1, 10, 100, 1000,…).

In binary notation, we have only two digits (0 and 1) and the place values go up by factors of 2. So we have a ones place, a twos place, a fours place, an eights place, a sixteens place, and so on. The following diagrams a number written in binary notation.

This value, 1011(2), represents a number with 1 eight, 0 fours, 1 two, and 1 one: 1 ⋅ 8 + 0 ⋅ 4 + 1 ⋅ 2 + 1 ⋅ 1 = 11(10). (The parenthesized subscripts indicate whether the number is in binary notation or decimal notation.)

We'll often want to convert numbers between their binary and decimal representations. We saw how to convert binary to decimal with 1011(2). Here's another example: Suppose we want to identify what 100100(2) represents. We first determine what places the 1's occupy.

We then add up the values of these places to get a base-10 value: 32 + 4 = 36(10).

To convert a number from decimal to binary, we repeatedly determine the largest power of two that fits into the number and subtract it, until we reach zero. The binary representation has a 1 bit in each place whose value we subtracted. Suppose, as an example, we want to convert 88(10) to binary. We observe the largest power of 2 less than 88 is 64, so we decide that the binary expansion of 88 has a 1 in the 64's place, and we subtract 64 to get 88 − 64 = 24. Then we see than the largest power of 2 less than 24 is 16, so we decide to put a 1 in the 16's place and subtract 16 from 24 to get 8. Now 8 is the largest power of 2 that fits into 8, so we put a 1 in the 8's place and subtract to get 0. Once we reach 0, we write down which places we filled with 1's.

We put a zero in each empty place and conclude that the binary representation of 88(10) is 1011000(2).

5.2. Integer representation

Now we can look at how computers are actually stored by the computer.

5.2.1. Unsigned integer representation

We can now examine how computers remember integers on the computer. (Recall that integers are numbers with no fractional part, like 2, 105, or −38.)

Modern computers usually represent numbers in a fixed amount of space. For example, we might decide that each byte represents a number. A byte, however, is very limiting: The largest number we can fit is 11111111(2) = 255(10), and we often want to deal with larger numbers than that.

Thus, computers tend to use groups of bytes called words. Different computers have different word sizes. Very simple machines have 16-bit words; today, most machines use 32-bit words, though some computers use 64-bit words. (The term word comes from the fact that four bytes (32 bits) is equivalent to four ASCII characters, and four letters is the length of many useful English words.) Thirty-two bits is plenty for most numbers, as it allows us to represent any integer from 0 up to 232 − 1 = 4,294,967,295. But the limitation is becoming increasingly irritating, and so people are beginning to move to 64-bit computers. (This isn't because people are dealing with larger numbers today than earlier, so much as the fact that memory has become much cheaper, and so it seems silly to continue trying to save money by skimping on bits.)

The representation of an integer using binary representation in a fixed number of bits is called an unsigned representation. The term comes from the fact that the only numbers representable in the system have no negative sign.

But what about negative integers? After all, there are some perfectly respectable numbers below 0. We'll examine two techniques for representing integers both negative and positive: sign-magnitude representation and two's-complement representation.

5.2.2. Sign-magnitude representation

Sign-magnitude representation is the more intuitive technique. Here, we let the first bit indicate whether the number is positive or negative (the number's sign), and the rest tells how far the number is from 0 (its magnitude). Suppose we are working with 8-bit sign-magnitude numbers.

3would be represented as 00000011
−3would be represented as 10000011

For −3, we use 1 for the first bit, because the number is negative, and then we place 3 into the remaining seven bits.

What's the range of integers we can represent with an 8-bit sign-magnitude representation? For the largest number, we'd want 0 for the sign bit and 1 everywhere else, giving us 01111111, or 127(10). For the smallest number, we'd want 1 for the sign bit and 1 everywhere else, giving us −127(10). An 8-bit sign-magnitude representation, then, can represent any integer from −127(10) to 127(10).

This range of integers includes 255 values. But we've seen that 8 bits can represent up to 256 different values. The discrepency arises from the fact that the representation includes two representations of the number zero (0 and −0, represented as 00000000 and 10000000).

Arithmetic using sign-magnitude representation is somewhat more complicated than we might hope. When you want to see if two numbers are equal, you would need additional circuitry so that −0 is understood as equal to 0. Adding two numbers requires circuitry to handle the cases of when the numbers' signs match and when they don't match. Because of these complications, sign-magnitude representation is not often used for representing integers.

5.2.3. Two's-complement representation

Nearly all computers today use the two's-complement representation for integers. In the two's-complement system, the topmost bit's value is the negation of its meaning in an unsigned system. For example, in an 8-bit unsigned system, the topmost bit is the 128's place.

In an 8-bit two's-complement system, then, we negate the meaning of the topmost bit to be −128 instead.

To represent the number −100(10), we would first choose a 1 for the −128's place, leaving us with (−100) − (−128) = 28. (We are using the repeated subtraction algorithm described in Section 3.2. Since the place value is negative, we subtract a negative number.) Then we'd choose a 1 for the 16's place, the 8's place, and the 4's place to reach 0.

Thus, the 8-bit two's-complement representation of −100(10) would be 10011100.

3would be represented as 00000011
−3would be represented as 11111101

What's the range of numbers representable in an 8-bit two's-complement representation? To arrive at the largest number, we'd want 0 for the −128's bit and 1 everywhere else, giving us 01111111, or 127(10). For the smallest number, we'd want 1 for the −128's bit and 0 everywhere else, giving −128(10). In an 8-bit two's-complement representation, we can represent any integer from −128(10) up to 127(10). (This range includes 256 integers. There are no duplicates as with sign-magnitude representation.)

It's instructive to map out the bit patterns (in order of their unsigned value) and their corresponding two's-complement values.

bit patternvalue
000000000
000000011
000000102
:
01111110126
01111111127
10000000−128
10000001−127
:
11111110−2
11111111−1

Notice that the two's-complement representation wraps around: If you take the largest number, 01111111, and add 1 to it as if it were an unsigned number, and you get 10000000, the smallest number. This wrap-around behavior can lead to some interesting behavior. In one game I played as a child (back when 16-bit computers were popular), the score would go up progressively as you guided a monster through a maze. I wasn't very good at the game, but my little brother mastered it enough that the score would hit its maximum value and then wrap around to a very negative value! Trying to get the largest possible score — without wrapping around — was an interesting challenge.

5.2.4. Adding two's-complement numbers

One of the nice things about two's-complement numbers is that you can add them just as you add regular numbers. Suppose we want to add −3 and 5.

We can attempt to do this using regular addition, akin to the technique we traditionally use in adding base-10 numbers.
We get an extra 1 in the ninth bit of the answer, but if we ignore this ninth bit, we get the correct answer of 2(10).

We can reason that this is correct as follows: Say one of the two numbers is negative and the other is positive. That is, one of the two numbers has a 1 in the −128's place, and the other has 0 there. If there is no carry into the −128's place, then the answer is OK, because that means we got the correct sum in the last 7 bits, and then when we add the −128's place, we'll maintain the −128 represented by the 1 in that location in the negative number.

If there is a carry into the −128's place, then this represents a carry of 128 taken from summing the 64's column. This carry of 128 (represented by a carry of 1), added to the −128 in that column for the negative number (represented by a 1 in that column), should give us 0. This is exactly what we get we add the carry of 1 into the leftmost column to the 1 of the negative number in this column and then throw away the carry (1 + 1 ≠ 10(2)).

A similar sort of analysis will also work when we are adding two negative numbers or two positive numbers. Of course, the addition only works if you end up with something in the representable range. If you add 120 and 120 with 8-bit two's-complement numbers, then the result of 240 won't fit. The result of adding 120 and 120 as 8-bit numbers would turn out to be −16!

The upshot of all this is that the adding circuit that we built for adding unsigned integers works also for two's-complement integers. The extra carry bit output doesn't have an obvious meaning, but as long as we only heed the actual bits.

5.3. Bit operators

The representation of integers is important enough that programmers sometimes find it useful to tell the computer to manipulate integers' bits directly.

5.3.1. Bitwise operators

The most significant operators along these lines are the bitwise operators, which give a way of performing logic operations on all the bits of the number. For example, the bitwise NOT operator ~ (also called the bitwise complement) is a unary operator, which takes the NOT of all the bits in the number. For example, if b holds the int value 00110111, then ~b holds the int value 11001000 — all of the bits have been complemented.

The other bitwise operators are the bitwise AND &, bitwise OR |, and bitwise XOR ^. These work by pairing corresponding bits in the two operands and performing the logical operation on them. For example, to compute the bitwise OR of 1100 and 1010, we take the OR of the first bits of each number, followed by the OR of the second bits, then the third bits, then the fourth bits; we end up with 1110.

The following illustrates all of these operators at work.

int a = 0x23;                /* 00100011 */
int b = 0x36;                /* 00110110 */
printf("%x\n", ~a);          /* prints DC (hex for 11011100) */
printf("%x\n", a & b);       /* prints 22 (hex for 00100010) */
printf("%x\n", a | b);       /* prints 37 (hex for 00110111) */
printf("%x\n", a ^ b);       /* prints 15 (hex for 00010101) */

5.3.2. Shifts

C provides two shift operators for shifting values: the left-shift operator << and the right-shift operator >>. These are binary operators, with the value to be shifted on the left side of the operator, and the distance to shift the value on the right side.

For example, the value of 5 << 2 is 20, since the binary representation of 5 is 101(2), which we shift left two spaces to get 10100(2) = 20(10). We fill in the empty spots with zeroes. Bits that go off the right end are simply lost. (Many programmers would say they fall into the bit bucket (or, more verbosely, the great bit bucket in the sky), a mythical location where bits go when they disappear.)

Notice that left-shifting by n bits is equivalent to multiplying by 2n, since we've essentially multiplied the value of each one bit in the number by that much. In the example of left-shifting 5 by 2, we get 5 ⋅ 22 = 20.

The right-shift operator works analogously: The value of 20 >> 2 is 5, since 20's binary representation is 10110(2), which shifted right two spots is 101(2) = 5. Again, the bits pushed off the right end simply fall into the bit bucket. Note that right-shifting is similar to dividing by a power of 2.

C doesn't specify how to handle right-shifting negative numbers. There are two common alternatives. In the first, called the logical right shift, a right-shift of a negative number will leave zeroes at the top end. The second, the arithmetic right shift, leaves ones on the top end for a negative number. Logical right shifts look more intuitive; but most compilers will use the arithmetic right shift, because programmers frequently want to right-shift in place of dividing by a power of 2. If you take −24 and arithmetically right-shift by 2, you'd get −6.

(Java resolves this ambiguity by providing two separate right-shift operators: the arithmetic right-shift operator >>, and the logical right-shift operator >>>.

int c = -20; // (11101100)
System.out.println(c >> 2); // prints -5 = 11111111111111111111111111111011
System.out.println(c >>> 2); // prints 1073741822 = 00111111111111111111111111111011

The logical right shift produced a value with an obscure relationship to original negative number.

5.3.3. Operator hierarchy

These fit into the operator hierarchy as follows in C and Java.

~ - (unary operators)
* / %
+ -
<< >> (and in Java, >>>)
< > <= >=
== !=
&
^
|
&&
||
conditional operator (?:)
= *= /= %= += -= <<= >>= &= ^= |=

At the bottom level, you can see that the bitwise and shift operators can be combined with the assignment operator, much like +=.

5.4. Counting one bits

This is a problem that's a favorite question in computer science: Write a function countOnes() that, given an int value, returns the number of bits in that number that are set to 1. For example, countOnes(21) should return 3, since 21's binary representation 10101(2) has three one bits in it. In fact, I visited Microsoft once interviewing for an internship, and one interviewer spent our appointment discussing various solutions to this question. (Many software companies like to spend interviews gauging interest and mastery using problems like this.)

5.4.1. Count technique

The simplest technique is to keep right-shifting the number until you reach 0, counting the number of times you right-shift a one bit off.

int countOnesA(int what) {
    int ret = 0;
    int i;
    for(i = 0; i < 32; i++) {
        ret += what & 1;
        what >>= 1;
    }
    return ret;
}

A similar alternative checks each bit of the number from right to left.

int countOnesB(int what) {
    int ret = 0;
    int mask = 1;
    int i;
    for(i = 1; i < 32; i++) {
        if((what & mask) != 0) ++ret;
        mask <<= 1;
    }
    return ret;
}

Note the importance of the parentheses in the if condition: If they were omitted, then the compiler would interpret the expression as what & (mask != 0), since the operator hierarchy places != above &. Because C treats Boolean expressions as integers, this would compile fine, but it would not be what is desired. Many programmers always place parentheses around the Boolean operators because their precedence can result is such unexpected behavior.

5.4.2. A clever technique

A different technique — which my interviewer showed me — is pretty clever. It employs the observation that, when you subtract a number by 1, all of the bits change up to and including the final 1 bit; but the rest of the bits stay the same. So if I do a bitwise AND of n with n − 1, essentially I will remove the last one bit from n.

int countOnesC(int what) {
    int ret;
    ret = 0;
    while(what != 0) {
        what &= what - 1;
        ++ret;
    }
    return ret;
}

So which of these techniques is better? I'd choose countOnesA. While the technique of countOnesC is quite elegant and would usually be a bit faster, it involves quite a bit of insight without all that much benefit, so I wouldn't actually use it. But it is a neat approach.