Bit Manipulation
Bit manipulation involves applying logical operations on a sequence of bits to achieve a result. It is a low-level technique often used for optimization, cryptography, and working with hardware drivers.
1. Bitwise Operators
Most programming languages (C, Java, Python, JavaScript) support these standard operators.
AND (&)
Returns 1 if both bits are 1.
5 & 3->101 & 011->001(1)
OR (|)
Returns 1 if at least one of the bits is 1.
5 | 3->101 | 011->111(7)
XOR (^)
Returns 1 if the bits are different.
5 ^ 3->101 ^ 011->110(6)
NOT (~)
Inverts all the bits (One's Complement).
~5->~00000101->11111010(Depends on integer size/signedness)
Bit Shifts
- Left Shift (
<<): Shifts bits to the left, filling with 0. Equivalent to multiplying by $2^n$.5 << 1->1010(10)
- Right Shift (
>>): Shifts bits to the right. Equivalent to dividing by $2^n$.5 >> 1->0010(2)
2. Common Tricks
Check if a number is Odd or Even
Instead of using modulo % 2, check the last bit.
def is_odd(n):
return (n & 1) == 1Multiply or Divide by 2
Bit shifting is generally faster than arithmetic multiplication/division.
x = 10
doubled = x << 1 # 20
halved = x >> 1 # 5Swap two numbers without a temp variable
Using XOR properties ($A \oplus A = 0$ and $A \oplus 0 = A$).
a = 5
b = 3
a = a ^ b
b = a ^ b # b becomes original a
a = a ^ b # a becomes original b3. Why use it?
- Space Efficiency: Storing booleans as bits in an integer (Bitmasking) saves massive amounts of memory.
- Speed: Bitwise operations are directly supported by the processor and are extremely fast.