Bitwise Operation
Bitwise means working at the level of single bits (rather than larger data units) -> copied from "Babylon Translator".
In C, bitwise operators are & (AND), | (OR), ^ (XOR), ~ (NOT), << (SHIFT LEFT), >> (SHIFT RIGHT)
To be able to understand bitwise operation, you have to be very familiar with base 2. That is, numbers consist of zeros and ones. All of these operators operate in base 2.
If you are using 32 bit C compiler, then an int variable is 32 bit length.
If you use 16 bits C compiler, an int variable is 16 bit length.
But remember, a char variable is always 8 bits length.
Why is 16 bits compiler and 32 bits compiler are put into our consideration?
Because they will behave differently on some cases! see the examples below, you will understand it automatically.
During bitwise operation, you have to align right the bits! (just like addition, multiplication,...)
The shorter bits can have trailing zeros at the front.
& (AND) operator
This table will clearly explains the bitwise operator & (AND):
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
Example:
What is the value of 24052 & 4978 ?
To solve this, you have to operate in base 2.
So, convert both number into base 2:
24052 -> 101110111110100
4978 -> 1001101110010
Now, align right the bits :
24052 -> 101110111110100
4978 -> 1001101110010
Now, AND the numbers : (shorter bits can have trailing zeros at the front)
24052 -> 101110111110100
4978 -> 001001101110010
----------------- &
001000101110000 -> 4464
Each bit-column is AND-ed using the AND table above.
The result of 24052 & 4978 = 4464.
| (OR) operator
This table summarize the OR operations :
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
Now, using the same example above, let's do it using | (OR) operator :
24052 -> 101110111110100
4978 -> 001001101110010
----------------- |
101111111110110 -> 24566
Each bit-column is OR-ed using the OR table above.
^ (XOR) operator
This table summarize the OR operations :
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
Now, using the same example above, let's do using | (OR) operator :
24052 -> 101110111110100
4978 -> 001001101110010
----------------- |
100111010000110 -> 20102
Easy, isn't it?
Now, the hard parts :
~ (NOT) operator
This operator is different from the above operators. This operator is called unary operator, since it only needs one operand. Operand is the number to be operated. The operators &, |, ^ are binary operators, since it takes 2 operands/number to be operated.
This ~ (NOT) operator, inverts all the bits in a variable. That is, changes all zeros into ones, and changes all ones into zeros.
Remember! that the result of this ~ (NOT) operation, is highly depends on the length of the bit in a variable!
Example:
int a = 10;
printf("%d",~a);
The output is -11.
To understand how in the hell -11 come from, you have to understand about binary representation of negative integers of an int variable!
Look at the operation of 16 bit C compiler : (that is, an int variable is 16 bits long)
a = 10 -> 0000000000001010 (16 bits)
------------------ ~
1111111111110101 -> -11
This is correct! Because computer stores -11 as 1111111111110101 in binary! (If you don't believe, you can read a computer organization book, or digital design book, or else that talks about how computer stores negative numbers).
Anyway, if you don't have time to read the book, just change the printf argument to show the unsigned value of ~a :
int a = 10;
printf("%u",~a);
The output is 65525. Now, it makes sense!
Argument %u will print the unsinged value of ~a.
Grab your calculator and calculate the decimal value of 1111111111110101 (binary), you will get 65525.
If you print the binary as "signed", then the output will be -11. (left most bit will act as a sign bit)
If you print the binary as "unsigned", then the output will be 65525. (left most bit is treated as a number as the other bits)
Don't be surprised if you got the output of the unsigned value of -11 is 4294967285.
I've said before that I use 16 bit C compiler.
If you use 32 bit C compiler, you actually will get
-11 as 11111111111111111111111111110101 in binary representation :
a = 10 -> 00000000000000000000000000001010 (32 bits)
--------------------------------- ~
11111111111111111111111111110101 -> -11 (for signed)
-> 4294967285 (for unsigned)
Is that clear?
<< (SHIFT LEFT) operator
This operator is mostly used if someone would like to multiply a number by 2 or power of 2.
This operator is also depends highly on the length of the bits of an int variable.
Actually this operator only "shift" or moves all the bits to the left.
Example : (I use 16 bit C compiler -> IMPORTANT)
int a = 4978;
printf("%d",a<<1);
The output will be 9956.
Do you see the relation of 4978 with 9956?
YES, 4978 * 2 = 9956. (it's the same as 4978 multiplied by 2)
For more detailed explanation, I will operate it in base 2 :
a = 4978 -> 0001001101110010 (16 bit)
------------------ << 1 (SHIFT LEFT the bits by one bit)
0010011011100100 -> 9956
Just move left all the bits by one. The left most bit is lost! and at the rightmost, a zero is added.
Second example: count 4978 << 8 (count 4978 shifted left by 8 bits)
Answer:
4978 -> 0001001101110010 (16 bit)
------------------ << 8 (SHIFT LEFT the bits by 8 bit)
0111001000000000 -> 29184
So, using 16 bit compiler, 4978 << 8 is 29184.
You can see that some of the left bits are lost...
It will not, however, if you use 32 bit compiler!
AGAIN! Don't be surprised if you got the output of 4978 << 8 is 1274368.
I've told you before that this operator depends the length of bits that an int can store (16 bits or 32 bits or else).
You have to know your compiler!
4978 -> 00000000000000000001001101110010 (32 bit)
---------------------------------- << 8 (SHIFT LEFT the bits by 8 bit)
00000000000100110111001000000000 -> 1274368
As you can see, no bits are lost after shifting the bits left by 8 bits if you use 32 bit compiler!
That's why 16 bit compiler and 32 bits compiler are put into our consideration...
Note that you don't have to have an int to store the value! In C, you can just print like this :
printf("%d", 4978 << 8);
The output will be 29184 for 16 bit compiler as Turbo C (Some bits will be lost)
The output will be 1274368 for 32 bit compiler as GNU C (All bits are reserved since it has bigger capacity)
Now you know why shifting left 1 bit is the same as multiply the number by 2 right?
And shifting left 8 bits is exactly the same as multiplying the number by 28 times!
If you notice:
4978 << 8 = 1274368 (in 32 bits compiler)
4978 * 28 = 4978 * 256 = 1274368. (exactly the same, isn't it)
I use 32 bit, because in 16 bit compiler, the left bits are lost! (hence will produce wrong answer)
BTW, you know why 4978 << 8 is the same as 4978 * 28, don't you?
>> (SHIFT RIGHT) operator
Not much different with << (SHIFT LEFT) operator. It just shift all the bits to the right instead to the left.
This operator is mostly used if you want to divide a number by 2, or other division by the power of 2.
Example :
count 4978 >> 8
Answer :
4978 >> 8 = 19 (in 16 bits compiler or 32 bits compiler, they both produce the same output)
I'm sure you do know why 16 or 32 bits compiler will result the same result for >> (SHIFT RIGHT) operator.
Detailed explanation :
4978 -> 0001001101110010 (16 bit)
------------------ >> 8 (SHIFT RIGHT the bits by 8 bit)
0000000000010011 -> 19
4978 -> 00000000000000000001001101110010 (32 bit)
---------------------------------- >> 8 (SHIFT RIGHT the bits by 8 bit)
00000000000000000000000000010011 -> 19
If you notice:
4978 >> 8 = 19 (in 32 bits compiler)
4978 / 28 = 4978 / 256 = 19. (They both the same, but using bitwise operator >> (SHIFT RIGHT) is a LOT faster!)
Suggestions
Do use bitwise operations instead of other mathematical operators such as * (MULTIPLICATION), / (DIVISION), + (ADDITION), - (SUBTRACTION). Because bitwise operators are A LOT FASTER than those operators.
But, give comment as the replacement for the readibility of your own source code! Since not so many people understand bitwise operations! They are too afraid to use them somehow, I don't know why...
Just drag those people to this page, they will thank you :)
Please contact me if I'm wrong, click here
|