# 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.
```python
def is_odd(n):
    return (n & 1) == 1
```

### Multiply or Divide by 2
Bit shifting is generally faster than arithmetic multiplication/division.
```python
x = 10
doubled = x << 1  # 20
halved = x >> 1   # 5
```

### Swap two numbers without a temp variable
Using XOR properties ($A \oplus A = 0$ and $A \oplus 0 = A$).
```python
a = 5
b = 3

a = a ^ b
b = a ^ b # b becomes original a
a = a ^ b # a becomes original b
```

## 3. 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.

[[programming/algorithms]]
[[programming/common-syntax]]