Section 4 - Bit Operations
3A.4.1 Shift Operators
Now that we know how numbers are stored internally, we can manipulate them as bits rather than numbers. By that I mean you can shift the bits left or right a specified number of positions.
- 101 shifted left one position is 1010
- 101 shifted left three positions is 101000
- 101 shifted right one position is 10
- 101 shifted right three position is 0
Shifting left and right turns out to be a useful operation in cellular automata, as you will discover. C++ and Java support shift operations using the << (shift left) and >> (shift right) operators.
x = y << 3; // shift y left three positions and store the result in x
You undoubtedly know that multiplying by 10 is easily done by adding a zero to the number. This is a left-shift operation! Adding two zeros, i.e., shifting left two places, is the same as multiplying by 100. In binary, shifting left once is equivalent to multiplying by 2, shifting left twice is equivalent to multiplying by 4, etc. Similarly, shifting right is like dividing by 10 in decimal and dividing by 2 in binary. Of course, when we shift right we lose the fractional place, so this is really an integer division, not a floating point one.
3A.4.2 Logical bit operators
If we think of the bit 1 as true and the bit 0 as false, we can apply the operations and, or and not to bits just as we did with bools. The bitwise operator for and, or and not are &, | and ~, respectively. The definitions for these operators on a single bit are:
| a | b | a|b |
|---|---|---|
| 1 | 1 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 0 | 0 |
| a | b | a&b |
|---|---|---|
| 1 | 1 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 0 | 0 | 0 |
| a | ~a |
|---|---|
| 1 | 0 |
| 0 | 1 |
Now, this only gives the result of a single bit. Numbers in computers are stored in words that are several bits - 8, 16, 32 and 64 typically. If you do a bitwise operation on two numbers, then the result will be applied to each bit position individually, the result of one position having no influence on the result of any other position.
For example,
- 11110000 | 01010101= 11110101
- 11110000 & 01010101= 01010000
- ~11110000 = 00001111
- ~01010101 = 10101010
Apply the above rules to each position, individually, to see this. If you want to prove it to yourself, convert 11110000 and 01010101 to either hex or decimal so you can use them in a program, and assign them to two variables. Then apply the bitwise operators and display the results. Convert the results to binary and you should get the answers shown above.
Warning: the bitwise not (complement) operator, ~, will convert all the 0s of the number to 1s. Since this includes left-most 0s (that we don't usually think about) the answer will be a number with a lot of 1s in the leftmost positions. Since this results in a negative value for most ints, the answer you see will be a strange looking negative number. Unless you want to look-up "two's complement" to see how this negative number is stored internally, you'll probably just have to take my word for the last two results. (Can you think of an easy -- almost trivial -- way to test that bit-wise complement seems to work correctly?)