by sjvsworldtour » Sat Jun 18, 2011 5:58 am
The bit minipulation gets a lot easier if you understand what each bit means. To do this you need to understand why hexadecimal is used so much in programming. It is very easy to convert from binary to hex if you remember the following table.
Bin Hex Dec
0000 0 0
0001 1 1
0010 2 2
0011 3 3
0100 4 4
0101 5 5
0110 6 6
0111 7 7
1000 8 8
1001 9 9
1010 A 10
1011 B 11
1100 C 12
1101 D 13
1110 E 14
1111 F 15
Each digit in a binary number increases by 2 as you move from left to right, so the value of the bit places are 8421. Notice that if I look at D, which is 1101 and replace the ones with the bit position values I get 8 4 0 1 and if I add those up I get 13, the decimal value.
It is similar for hex. What if I have a hex number like 0x3B. The digit positions in hex are times 16, not 2 as in binary, so the digit values get bigger much quicker. From left to right that are 16^1, 16^0 which is 16 and 1. This is a simple example. Once you add more digits for hex it gets really messy. But for the example you do something similar to what was done above with decimal. Above we basically multiplied each number by the value in the bit position, which is why 0 ended up in one place. The bit position was 0 so 0 time 2 is 0. Now here, since it is base 16, you multiply by 16. So to convert 0x3B to decimal, you just multiply by the digits position and the value 3*16 + 11(which is B) * 1 which is 48+11 which is 59 in decimal.
Yea, that explanation was too long. Maybe I can do better with the shifting. Think of it this way. Left shift multiplies by 2 and right shift divides by 2. This is true as long as you don't get into underflow or overflow.
For easy examples, lets deal with nibbles, which are 4 bits. The biggest number you can store in a nibble is 255, which is 2^4-1. The 4 is the number of bits. Why minus one? It is because we count starting at zero. For instance in decimal the biggest number that can be held in two digits is 99, which is 10^2-1, which is 100-1, which is 99.
A nibble is only good for demonstration purposes because you aren't likely going to run into a 4 bit processor, but 8 bit is common. I am just making the numbers easier. So above we decided that the biggest number we could store would be 255 in our nibble. Now lets shift some bits. For simplicity, lets shift 0x01. What do we get if we do 1<<7? Well, I already said think of it as multiplying by two or dividing by 2. So here you are going to multiply by two 7 times.
So we get 1*2*2*2*2*2*2*2 = 4 * 4 * 4 * 2 = 16 * 8 = 128. Yea, that is right. Now, happens if I shift it one more time? The answer you get is zero. Why? Because 128*2=256, which is bigger than the 255 we said a nibble could hold. Since we were only shifting one bit, the only set bit was shifted off. Basically, each time you shift a bit off to the left, you subtract 256 from your total. So 128*2-256=0.
No lets look at shifting right, which is much quicker. As I have said, shifting right is like dividing by 2. So if we have 3 stored in our nibble and we shift it right once, what do we get? 3/2 = 1. The lowest order bit got shifted right and disappeared (underflow). The bit that was in the 2 position is shifted to the one position and you get the answer of 1. If you shift it again, you get zero, because the one position bit will disappear.
You also mentioned XOR(^). Don't confuse it with my use of the same character above for raising a number to a power. In C, there is no operator to raise a number to a power, although there is a function to do it. So, understand that ^ means exclusive or, lets make it simple. Exclusive or means one but not both. So the truth table is like this.
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
The only difference between the truth table for an or and the truth table for an exclusive or is when both are one. For a regular or, then answer would be 1.
Now for a neat trick you can do with exclusive or. This actually comes in handy when memory is extremely tight. You can swap the places of two numbers without needing a third location. For instance, if you had plenty of memory, you do this.
C = A
A = B
B = C
And you swapped A and B. With exclusive or, you can do this.
A = A ^ B;
B = A ^ B;
A = A ^ B;
The values of A and B will be swapped. Try it with any combination of A and B with each equal to 1 or 0. Yea, amazing isn't it. And yes, it will work with bigger numbers through bit manipulation.