# The Penguin Programmer

## Binary Operations

Now, I mentioned that binary was important, and the reason for this is that its the base with the fewest digits, making it the simplest way to represent a number. What’s more, we can use the fact that binary only requires two digits to associate each digit with one of two states, say `true`

and `false`

, or `high voltage`

and `low voltage`

. This is one of the reasons why binary is particularly good for computers; numbers can be processed by the computer by just switching from a low voltage to a higher one.

Another reason why binary is so great is that it greatly simplifies many mathematical operations. Addition is not improved by much when done by hand (though a circuit performing base 2 addition is far simpler than one in base 10), being performed in the same way in any base, although there exist algorithms for multiplication and division that are more efficient when dealing with a binary representation, as well as for many other more advanced operations. How for example, would we compute `0b1010 + 0b1010`

?

I’m assuming you’re familiar with the usual layout I’ve used above, but note that here, because we can only use 0 and 1, the sum `1 + 1`

is 0 and we carry the 1, instead of obtaining 2 as in decimal and not carrying anything. Also note that the result is exactly the same as the operands, but with all the digits shifted one to the left. With a little bit of thought, we can see why this is the case. Consider, in decimal, the equation `5 * 10 = 50`

. Multiplying by 10 shifts the operand (5) one digit to the left, and adds a 0 to the end, but multiplying by 10 is the same as adding the operand to itself ten times. Analogously, adding a binary number to itself is equivalent to multiplying it by 2, which similarly is a shift to the left by one digit. Multiplying by 2 is a much more useful operation than multiplying by 10, so much so that the act of shifting a number a certain number of places to the left (or right) is its own operation, called *bit shifting*. C++ supports this using the `<<`

and `>>`

operators respectively. (These are not the stream operators, which are overloads of the bit shift operators for non-integral types.)

For example, say we wish to find `104 * 256`

. Certainly we can simply calculate this using the normal method of multiplication, but we can also do this

`256 = 2^8`

and so multiplying by 256 is the same as multiplying by 2 eight times. Of course converting to binary, shifting the number, then converting it back to decimal is unlikely to be faster by hand, but since with a computer the numbers are already stored in binary this operation can be significantly faster. This is more of a theoretical point than a practical one however, in most cases the speedup isn’t significant compared to the rest of the program and any modern compiler will recognise that `104 * 256 = 104 << 8`

and will make the optimisation for you automatically. This doesn’t mean bit shifting isn’t useful though, it can be very handy when dealing with non-text data, especially images. (Where bitshifting and some other operators we’re about to meet allow you to extract the red, green, and blue components of the colour.)

As I mentioned earlier, we can associate each digit of a binary number with either `true`

(1) or `false`

(0). This allows us to define analogues of the logical `and`

, `or`

, and `not`

operators for numbers. These operators are defined *bitwise*, that is they apply to each bit in sequence. This’ll make more sense when we look at examples.

Consider the usual logical `and`

, the `&&`

operator. The expression `a && b`

evaluates to `true`

if both `a`

and `b`

are true statements, and evaluates to `b`

otherwise. Similarly, given two bits the bitwise `and`

operator, `&`

returns `1`

if both bits are `1`

and returns `0`

otherwise. The `&`

operator performs this on each corresponding bit in sequence, so for example the expression `0b10101 & 0b10110`

evaluates to `0b10100`

.

We then have the bitwise `or`

and bitwise `not`

operators, denoted `|`

and `~`

respectively, which act much as you would expect:

There’s one more bitwise operation that’s commonly used, the so called `exclusive or`

or `xor`

operator, denoted `^`

. Whereas the standard (inclusive) `or`

returns `true`

if at least one of the bits are `true`

, the `^`

operator only returns `true`

if exactly one of the bits is. For example, `0b10101 ^ 0b10110 = 0b00011`

. Note however that if we perform the `xor`

again with the same operand `0b10101 ^ 0b00011 = 0b10101`

we get back the same number we started with! This property makes the `xor`

operator very useful for encryption, as we can take a message, `xor`

it with a secret key, and transmit the encrypted message, and the other person only needs to `xor`

it with the same key to get back the original input. If the key is sufficiently long, this becomes very hard to crack despite its simplicity!

If you’ve been running these examples in C++ whilst you’ve been reading this then I apologise for the all the compiler errors you’re probably having; sadly, whilst C++ has native support for octal literals (numbers written in octal) as of the C++11 standard it does not support binary literals. The upcoming C++14 standard does however, so if you’re lucky and your compiler has already implemented this part of the new C++ specification then all this code will run fine, as the `0b`

prefix is part of the new standard (and is used in several other languages too, such as Ruby and Java).