Bitwise operations
While in general people do not work with any unit smaller than a byte, occasionally one wishes to manipulate individual bits. To do this, we use what is called bitwise operations.
Why use individual bits? We usually use bitwise operations when we want to manipulate data at a very fine level. For instance if we want to save memory, we can often combine several pieces of information into a single byte. Because a boolean can only be true or false, we can represent it with a single bit. Since there are 8 bits in a byte, we are able to store 8 boolean values in a single char.
One of the more common examples of bitwise ops is where you do something like this:
byte monkeyState = RUNNING + PANTING + THIRSTY;In a single byte, we have stored 8 things about the monkey: he is running, panting and thirsty. We also know that he is NOT hungry, scared, bored, walking or tired. How do we fit all this information in a single byte?
By defining a set of constants to suitable values (powers of 2, actually), we can
easily store the monkey's exact state:
WALKING = 1 (00000001) RUNNING = 2 (00000010) PANTING = 4 (00000100) HUNGRY = 8 (00001000) THIRSTY = 16 (00010000) SCARED = 32 (00100000) BORED = 64 (01000000) TIRED = 128 (10000000)I have included the binary representation of each number to the side. Notice that each number has only one '1', and that each number has its '1' in a different column. When we said that monkeyState = RUNNING + PANTING + THIRSTY, we really said
monkeyState = 2 + 4 + 16 = 22 (00010110)Now, it's easy to convert the monkey's state into the number 22, but how do you do the reverse? For instance, what does the number 162 say about the monkey? To find out, convert 162 into binary (10100010), then look at the bits that are '1'. Which states do they correspond to?
- The '1' in the 1st position means that he is TIRED
- The '1' in the 3rd position means that he is SCARED
- The '1' in the 7th position means that he is RUNNING
The & (AND) operator
This operator is similar to && that you are probably used to. However it is different in that it takes two numbers, not two booleans. It returns a number that has a '1' in every position that both input numbers have a '1' in. For example:
10011101 (157) 11110000 (240) 11110000 (240) & 10100100 (164) & 00001111 (15) & 11001100 (204) ---------- ---------- ---------- 10000100 (132) 00000000 (0) 11000000 (192)It turns out that this is really useful for finding out how the monkey is feeling. Let's say that we have been told monkeyState = 72. We want to know if he is tired and wants to be put to bed.
01010000 (72 - monkeyState) & 10000000 (128 - TIRED) ---------- 00000000 (0 - he is not tired)Maybe he's hungry...
01001000 (72 - monkeyState) & 00001000 (8 - HUNGRY) ---------- 00001000 (8 - he is HUNGRY)
To test for any of the states, here is the generic if statement:
if ((monkeyState & [state]) == [state]) // Monkey is [state] else // Monkey is not [state]
We can also test for more than one state at a time. Let's see if he is both HUNGRY and THIRSTY:
if ((monkeyState & HUNGRY + THIRSTY) == HUNGRY + THIRSTY) //Give the monkey his dinner and milk else //Don't waste the food HUNGRY + THIRSTY = 8 + 16 = 24 01010000 (72 - monkeyState) & 00011000 (24 - HUNGRY and THIRSTY) ---------- 00010000 (16 - he is THIRSTY) if ((72 & 24) == 24) // Monkey is HUNGRY and THIRSTY else if ((72 & 24) == 0) // Monkey is neither HUNGRY nor THIRSTY else // Monkey is either HUNGRY or THIRSTYSince 72 & 24 is 16, not 24, we know that he is not both HUNGRY and THIRSTY, but because the answer isn't 0, we know that one of the conditions must be true.
An important thing to remember is ANDing any bit with 0 will result in 0. ANDing any bit with 1 will leave that bit unchanged.
The | (OR) operator
The | operator is the opposite of the & operator: the result of ORing two numbers together is a number who's bits are '1' in all the positions that either number had a '1' in.
10011101 (157) 11110000 (240) 11110000 (240) | 10100100 (164) | 00001111 (15) | 11001100 (204) ---------- ---------- ---------- 10111101 (189) 11111111 (255) 11111100 (252)
This is useful in setting states in an already existing monkey. In this case, we cannot use + without checking first to see that the monkey is not already in that state. Let's say the monkey is HUNGRY (8). If we do
monkeyState = monkeyState + HUNGRY;monkeyState will now be 16 (8 + 8), which means he is THIRSTY. Notice that not only is he THIRSTY now, but he is no longer HUNGRY, even though we tried to set his state as that. To avoid this problem, we use | instead. HUNGRY | HUNGRY= HUNGRY.
00001000 (8 - HUNGRY) | 00001000 (8 - HUNGRY) ---------- 00001000 (8 - HUNGRY)Notice how this time, reasserting that he is HUNGRY does not make him THIRSTY. Setting him to HUNGRY does nothing other than make him HUNGRY. Even if he was HUNGRY before now, he will still be HUNGRY and nothing else.
We can set multiple states at once. Let's say we want to make him HUNGRY and BORED:
monkeyState = monkeyState | (HUNGRY + BORED);HUNGRY + BORED = 8 + 64 = 72 (01001000). ORing that with monkeyState will turn those bits on if they weren't on before now. If they were on, they won't be changed.
The rule with OR is any bit ORed with 1 will result in 1. Any bit ORed with 0 will leave that bit unchanged
The ~ (NOT) operator
The ~ operator simply returns a number where every bit is the opposite of corresponding bit in the number it is given. For example:
~ 11000110 (198) ---------- 00111001 (57)The ~ operator is generally used in conjunction with & or |. For instance, to stop the monkey from being BORED, we can say monkeyState = monkeyState & ~BORED.
BORED = 01000000 ~BORED = 10111111 11011001 (old monkeyState - TIRED, BORED, THIRSTY, HUNGRY and WALKING) & 10111111 (~BORED) ---------- 10011001 (new monkeyState - TIRED, THIRSTY, HUNGRY and WALKING)Because of the rule given above (any bit ANDed with 0 will become 0, any bit ANDed with 1 will stay the same), if we AND monkeyState with ~BORED, it will leave all the bits other than the BORED bit in monkeyState alone (because ~BORED is 1 in all of those positions). However the BORED bit is 0, thus when you AND it with monkeyState, the BORED bit in monkeyState will be turned off, giving back the monkey his interest in life.
The ^ (XOR) operator
The ^ operator results in a number with the bits that are different being turned on. For instance, if the 6th bit was on in either A or B (but not both), the 6th bit in the result would be turned on. If that bit was on in both A and B or off in both A and B, the same bit in the result would be off.
10011101 (157) 11110000 (240) 11110000 (240) ^ 10100100 (164) ^ 00001111 (15) ^ 11001100 (204) ---------- ---------- ---------- 00111001 (57) 11111111 (255) 00111100 (60)
One of the interesting things about XOR is if you do the operation twice with the same number, you will get back to your original answer. That is to say if A ^ B = C, then C ^ B = A and C ^ A = B. Using the example above:
00111001 (57) 10100100 (164) ^ 10100100 (164) ^ 00111001 (57) ---------- ---------- 10011101 (157) 10011101 (157)Notice that it also does not matter which order A and B are in, you will always get the same result.
The << and >> (bitshift) operators
These operators move the bits in a number left or right the specified number of places. Eg:11 << 3 = 88 00001011 (Move everything 3 to the left) 01011000 (Note that the right is filled in by 0's) 88 >> 2 = 22 01011000 (Move everything 2 to the right) 00010110 (This time the left is filled in with 0's)Every bit you shift to the left multiplies the number by 2, so shifting 5 bits (x << 5) multiplies by (2 * 2 * 2 * 2 * 2) = 32. Simarly shifting to the right divides by 2, so shifting 3 bits (x >> 3) divides the number by (2 * 2 * 2) = 8. This form of division is much faster than the normal arithmetic division the CPU uses, because it does not involve a lookup table. Note that you can only use bitshifting to multiply or divide by a power of 2.
Using bitshift operators to scan bits
Say for example you want to find the leftmost or rightmost bit that is either 1 or 0. Using the bitshift and bitwise AND operators, it is easy to program this task. All you have to do is keep shifting by one bit in a certain direction, then ANDing the result with a number that has only either the MSB or LSB bit 1 (all the rest are 0).
int bitfield; // The contents of this would come from somewhere else in the program
int tempBitfield = bitfield; //We don't want to destroy the information in here, so make a copy
int bitNumber = 0; //The position of the first bit that is 1
while ((tempBitfield & 1) == 0 && bitNumber < [Number of bits in bitfield])
{
tempBitfield = tempBitfield >> 1;
bitNumber++;
}
How does this program work? The binary representation of 1 is 00000001. This means that when we AND it, only the last bit will be remaining in the number. All of the other bits have been set to 0. The only numbers that will not be 0 when we AND them with 1 are numbers with 1 in the final (LSB) bit. Therefore if we keep shifting and count how many times we have shifted, we can tell how many bits from the right the first 1 is.
Example find the rightmost '1' in 72: 72 = 01001000 (bitNumber = 0) 01001000 & 00000001 = 0, therefore tempBitfield >> 1, bitNumber++ (bitNumber = 1) 00100100 & 00000001 = 0, therefore tempBitfield >> 1, bitNumber++ (bitNumber = 2) 00010010 & 00000001 = 0, therefore tempBitfield >> 1, bitNumber++ (bitNumber = 3) 00001001 & 00000001 = 1, we have found the first '1'. Since bitNumber = 3, we know that the 4th bit from the right is the first '1'
How would you do it in reverse (look for the leftmost bit that is 1)? Instead of shifting to the right, you would now be shifting to the left, and the number that you AND it with would have to be the number with the only '1' being in the leftmost position that we are using. Eg, assuming that the number of bits in our bitfield is 8, the number we would use is 2
while ((tempBitfield & 128) == 0 && bitNumber < [Number of bits in bitfield]) { tempBitfield = tempBitfield << 1; bitNumber++; } Example find the leftmost '1' in 72: 72 = 01001000 (bitNumber = 0) 01001000 & 10000000 = 0, therefore tempBitfield << 1, bitNumber++ (bitNumber = 1) 10010000 & 10000000 = 128, we have found the first '1' Since bitNumber = 1, we know that the 2nd bit from the left is the first '1'
