“There are 10 kinds of people in this world, 1 who know binary and 1 who doesnt.”
Confused?? How come 10 ? Well, such is the power of binary numbers that even 2 is written as 10. :P
With more of the high level programming language used these days, the power and effectiveness of using bits is becoming history now. Bit manipulation is one of the most useful and effective low-level optimization. It can help improve the speed and size of the program and also help simplify coding sometimes.
The four basic bit operators are AND (&), OR ( | ), NOT (!) and XOR (^). Here is the truth table:
So if A = 0101 (5) and B = 1011 (11), then:
- !A = 11111010 (number of leading 1’s depend on the type of A)
- A&B = 0001
- A|B = 1111
- A^B = 1110
Two more operators involving bits are left-shift ( a<<b) and right shift (a>>b) operators. Left-shift shifts the bits in a by b positions to the left, and assuming numbers are positive, this is equivalent to multiply a with 2band right shifting is same as dividing the number a with 2 b. The use of this is to set or clear a particular bit. Suppose a is 3. Then 1<<a in binary form is 1000(8). Thus every bit can be accessed in this way. So the following is the way to set or clear bits of a number:
To set a bit (b) of A, : A | = 1 << b
To clear a bit(b) of A: A&= ~(1 << b), where (~ is the negation symbol).
Many set operations can be done with bit manipulations:
- Set Union : A|B
- Set Intersection : A&B
- Set subtraction: A & ~B
- Set negation : SET_ALL_BIT ^ A
Where SET_ALL_BIT represent a number with all bits set
Also if one wishes to find all possible sets possible, which is (2N) he may iterate over all binary numbers in the range of 0 to (1<<N) . In Java, one can easily find the binary of a number by Integer.toBinaryString(i) method.
If anyone has any further doubt, he can reach me personally.
Follow up question : How would you take out the last set bit(1) of any natural number.
最近のコメント