> ## Documentation Index
> Fetch the complete documentation index at: https://akshanshgusain.mintlify.site/llms.txt
> Use this file to discover all available pages before exploring further.

# Bit Manipulation

# Theory

### Basics of Bits

* `Bit`: The smallest unit of data in a computer, either 0 or 1.
* `Binary Representation`: Any integer can be represented in base-2.
  Example: 5 in binary → 101, 10 in binary → 1010.
* **Why Bit Manipulation?**
  * Faster than arithmetic operations (O(1) for most operations).
  * Saves space (storing multiple states in a single integer).
  * Useful in problems involving sets, flags, XOR, AND masks.

### Common Bitwise Operators

| Operator    | Symbol | Operation                          | Example                              |
| :---------- | :----- | :--------------------------------- | :----------------------------------- |
| AND         | `&`    | 1 & 1 = 1, else 0                  | 5 & 3 = 101 & 011 = 001 = 1          |
| OR          | `\`    | 0 `\` 0 = 0, else 1                | 5 `\` 3 = 101 `\` 011 = 111 = 7      |
| XOR         | `^`    | `1 ^ 1 = 0, 0 ^ 1 = 1`             | 5 ^ 3 = 101 ^ 011 = 110 = 6          |
| NOT         | `~`    | Inverts bits                       | \~5 = \~101 = 010 (two's complement) |
| Left Shift  | `<<`   | Shifts bits left (multiply by 2^n) | `5 << 1 = 1010 = 10`                 |
| Right Shift | `>>`   | Shifts bits right (divide by 2^n)  | `5 >> 1 = 10 = 2 `                   |

<Note> `\` is actually `|`. The bitwise OR operators which is denote by `|` can't be used inside a mdx table</Note>

# Common Patterns to remember

### Common Operations

**1. Checking if a bit is set or not**

```python theme={null}
from typing import Final
"""
In binary representation, indexing typically starts from right to left, with the least significant bit (LSB) at
    position 0 and the most significant bit (MSB) at the highest position.

    Intuition:
    - We create a bitmask with only the i-th bit set by left-shifting 1 by i places: (1 << i).
    - Using bitwise AND with the original number keeps only the overlapping set bits.
      If the result is non-zero, the i-th bit in the number was set.
"""
mask: Final[int] = 1 << index
is_set: bool = (number & mask) != 0
```

**Setting the rightmost set bit to 1**

```ptyhon theme={null}
if n + 1 == 0:
    return n  # All bits are already set
return n | (n + 1)
```

**Unsetting the rightmost set bit to 1**

```ptyhon theme={null}
# Brian Keringhan's Algorithm

if n == 0:
    return 0  # No set bits to unset
return n & (n - 1)
```

**2. Setting Kth bit to 1**

```python theme={null}
"""
Create a mask by left-shifting 1 by k
Apply the mask by OR-ing it with the number
"""

n = 5
k = 1
# 111 → 7
n = n | (1 << k)
```

**3. Setting Kth bit to 0(Clearing Kth bit)**

```python theme={null}
n = 5        # 101
k = 0
n = n & ~(1 << k)  # 100 → 4
```

**4. Toggling Kth bit**

```python theme={null}
n = 5        # 101
k = 0
n = n ^ (1 << k)  # 100 → 4

```

**5. Counting set bits**

```python theme={null}
def count_set_bits(n: int) -> int:
    """
    Count the number of set bits (1s) in the binary representation of a number.

    Intuition:
    - We need to count how many 1s are present in the binary representation of n.
    - We can use bitwise operations to check each bit position.
    - There are several approaches: iterative, Brian Kernighan's algorithm, and built-in functions.
    - The key insight is that we can repeatedly remove the least significant set bit.

    Approach:
    1. Initialize a counter to 0.
    2. While n is greater than 0:
       - Check if the least significant bit is set using n & 1.
       - Add 1 to counter if bit is set.
       - Right shift n by 1 to check the next bit.
    3. Return the final count.

    Key Insights:
    - n & 1 checks if the least significant bit is set.
    - n >>= 1 removes the least significant bit (equivalent to n // 2).
    - We continue until n becomes 0.
    - This approach works for both positive and negative numbers.

    Example:
    n = 13 (binary: 1101)
    Iteration 1: n & 1 = 1, count = 1, n = 6 (110)
    Iteration 2: n & 1 = 0, count = 1, n = 3 (11)
    Iteration 3: n & 1 = 1, count = 2, n = 1 (1)
    Iteration 4: n & 1 = 1, count = 3, n = 0
    Result: 3 set bits

    Time Complexity: O(log n) - proportional to the number of bits
    Space Complexity: O(1) - constant space
    """
    count = 0
    while n > 0:
        count += n & 1  # Add 1 if least significant bit is set
        n >>= 1        # Right shift to check next bit
    return count

"""
Brian Kernighan’s Algorithm
"""
def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count
```

**6. Power of Two Check**

```python theme={null}
"""
Check if only a single bit is set in a number.
If the number is a power of two, then the number and its complement would have only one bit set.
"""
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

```

**7. XOR Tricks**

XOR Properties:

1. `a ^ a = 0`
2. ` a ^ 0 = a`
3. `a ^ b ^ a = b` (commutative and associative)

Applications:
Find unique number in array where every other number occurs twice.

```python theme={null}
arr = [2, 3, 2, 4, 4]
res = 0
for num in arr:
    res ^= num
print(res)  # Output: 3

```

**8. Subset generation using bits**

```python theme={null}
# Use an integer to represent subset
arr = [1, 2, 3]
n = len(arr)
for mask in range(1 << n):
    subset = [arr[i] for i in range(n) if mask & (1 << i)]
    print(subset)

```

**9. Swapping Numbers Using XOR**

```python theme={null}
a = 5
b = 3
a ^= b
b ^= a
a ^= b

```

**10. Finding Rightmost Set Bit**

```python theme={null}
n = 10    # 1010
rightmost = n & -n  # 0010 → 2

```

**11. Clearing Rightmost Set Bit**

```python theme={null}
n = 10    # 1010
n = n & (n - 1)  # 1000
```

<Tip>
  **Tip for Interviews:**

  1. Always think in terms of 0 and 1.
  2. Many problems on Leetcode: Single Number, Counting Bits, Subset Sum DP, Missing Number, Power of Two.
  3. Visualize bits as switches — “on/off” to simplify reasoning.
</Tip>

# Algorithms

### Brian Kernighan’s Algorithm

Brian Kernighan’s Algorithm is one of the most elegant and widely used bit manipulation tricks in DSA, especially for
counting set bits efficiently

**Trick: n & (n-1) removes the rightmost set bit from n.**

* **Every time you do `n = n & (n-1)`, you remove one 1(rightmost)**
* Count how many times you can do this → `number of 1s`

**Why does it work?**

* `n - 1` flips all bits after the rightmost 1, including that 1 itself
* ANDing it with n removes that rightmost 1

```python theme={null}
    # Step 1: n = 1100
    n-1 = 1011
    n & (n-1) = 1100 & 1011 = 1000  # removes rightmost 1

    # Step 2: n = 1000
    n-1 = 0111
    n & (n-1) = 1000 & 0111 = 0000  # removes last 1

```

```python algorithm.py theme={null}
def count_set_bits(n):
    count = 0
    while n:
        n &= (n-1)  # remove rightmost set bit
        count += 1
    return count

# Example
n = 13
print(count_set_bits(n))  # Output: 3

```

***

## Problem Set

<Warning>
  In python, Logical `AND` is different from Bitwise `&`
</Warning>

<Info>
  Solution to All recursion solutions [Github](https://github.com/akshanshgusain/data_structures_algorithms_python/tree/master/recursion)
</Info>

### Basics

1. [Check if the ith bit is set](https://takeuforward.org/plus/dsa/problems/check-if-the-i-th-bit-is-set-or-not)
2. [Check if a number is odd or not](https://leetcode.com/problems/number-of-even-and-odd-bits/description/)
3. [Check if a number is power of 2 or not](https://leetcode.com/problems/power-of-two/description/)
4. [Count the number of set bits](https://takeuforward.org/plus/dsa/problems/count-the-number-of-set-bits)
5. [Set/Unset the rightmost unset bit]() **T**
6. [Swap two numbers](https://takeuforward.org/plus/dsa/problems/swap-two-numbers) **Trick**
7. [Divide two numbers](https://leetcode.com/problems/divide-two-integers/) **Trick**

### Medium Problems

1. [Count the number of bits to be flipped to convert A to B](https://leetcode.com/problems/minimum-bit-flips-to-convert-number/)
2. [Single Number](https://leetcode.com/problems/single-number/description/)
3. [Power set](https://leetcode.com/problems/subsets/)
4. [Find xor of numbers from L to R](https://takeuforward.org/plus/dsa/problems/xor-of-numbers-in-a-given-range)
5. [Find the two numbers appearing odd number of times](https://takeuforward.org/plus/dsa/problems/single-number---iii)

### Math problems

1. [Print Prime Factors of a Number](https://takeuforward.org/plus/dsa/problems/prime-factorisation-of-a-number)
2. [All Divisors of a Number]()
3. [Sieve of Eratosthenes]()
4. [Find Prime Factorisation of a Number using Sieve]()
5. [Power(n, x)]()