DS&A

Binary Numbers

Using multiple bits to represent an integer requires deciding what the bits mean. A simple scheme for representing numbers could be to represent e.g. the integer value 3 by using three 1s, like so:

(This interactive feature requires Javascript to be enabled in your browser.)

This works for representing small numbers, but it’s a terrible solution — we’d need lots of bits to represent big numbers, and it’s inefficient because each bit means the same thing so there are many equivalent ways to represent each number. We can do much better:

(This interactive feature requires Javascript to be enabled in your browser.)

Try using this scheme to represent numbers such as 12 and 157. There is a logic to it: each bit is “worth” twice as much as the next bit, making a binary number system instead of the decimal number system we’re used to.(1)

Let’s explore this scheme a bit further. We don’t just want to represent integers so that we can store and transmit them; we also want to compute with them. We want to be able to perform operations like +, -, * and / on integers represented this way. Let’s just consider the simplest arithmetic operation, ‘add 1’:

(This interactive feature requires Javascript to be enabled in your browser.)

After experimenting with this for a while, you might notice the pattern. There is a simple procedure to perform the ‘add 1’ operation on the bits directly, without having to “decode” and “re-encode” the numbers:

• Start at the right hand side.
• If the current bit is 1, change it to 0, move left, and repeat this step.
• Otherwise the current bit is 0, so change it to 1 and stop.

Try following this procedure by hand, instead of clicking the ‘Increment’ button; check that it really does increase the number by 1.(2)

So now we have a scheme for representing data values in the computer’s memory, and a procedure for performing operations on that data. That is, we have a data structure, and an algorithm.

Although this example is very simple compared to “real” data structures and algorithms, it’s useful because it demonstrates a few important things which we’ll keep thinking about when studying data structures and algorithms:

• Each type of value (such as int) has operations which can be performed on that type (such as +).
• To represent values, we need a data structure for that type.
• To implement an operation on a data structure, we need an algorithm.

We’ve also seen that we can have more than one data structure for a type: the first scheme (where every bit is “worth” 1) also represents integers, but in a different way. Notice also that the ‘add 1’ algorithm is specific to the data structure we used; we’d need a different algorithm to ‘add 1’ using the first scheme.

Footnotes

1. In decimal, each digit is “worth” 10 times the next digit, because with the 10 symbols 0, 1, 2, …, 9, the smallest number we need to use an extra digit for is 10. In binary, we have the 2 symbols 0 and 1, so 2 is the smallest number we need an extra bit for, and hence each bit is “worth” 2 times the next bit.
2. In fact, this algorithm is very similar to the way we usually add decimal numbers — by carrying to the next column when the sum is too big. If the current bit is 0, then 0 + 1 = 1 and we don’t need to carry; if it’s 1 then 1 + 1 = 2 so we do need to carry to the next column.

• Tags: 
• binary