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 |
\ is actually |. The bitwise OR operators which is denote by | can’t be used inside a mdx table
Common Patterns to remember
Common Operations
1. Checking if a bit is set or not
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
if n + 1 == 0:
return n # All bits are already set
return n | (n + 1)
# Brian Keringhan's Algorithm
if n == 0:
return 0 # No set bits to unset
return n & (n - 1)
"""
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)
n = 5 # 101
k = 0
n = n & ~(1 << k) # 100 → 4
n = 5 # 101
k = 0
n = n ^ (1 << k) # 100 → 4
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
"""
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
a ^ a = 0 a ^ 0 = aa ^ b ^ a = b (commutative and associative)
Applications:
Find unique number in array where every other number occurs twice.
arr = [2, 3, 2, 4, 4]
res = 0
for num in arr:
res ^= num
print(res) # Output: 3
# 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)
a = 5
b = 3
a ^= b
b ^= a
a ^= b
n = 10 # 1010
rightmost = n & -n # 0010 → 2
n = 10 # 1010
n = n & (n - 1) # 1000
Tip for Interviews:
- Always think in terms of 0 and 1.
- Many problems on Leetcode: Single Number, Counting Bits, Subset Sum DP, Missing Number, Power of Two.
- Visualize bits as switches — “on/off” to simplify reasoning.
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
# 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
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
In python, Logical AND is different from Bitwise &
Solution to All recursion solutions Github Basics
- Check if the ith bit is set
- Check if a number is odd or not
- Check if a number is power of 2 or not
- Count the number of set bits
- Set/Unset the rightmost unset bit T
- Swap two numbers Trick
- Divide two numbers Trick
Medium Problems
- Count the number of bits to be flipped to convert A to B
- Single Number
- Power set
- Find xor of numbers from L to R
- Find the two numbers appearing odd number of times
Math problems
- Print Prime Factors of a Number
- All Divisors of a Number
- Sieve of Eratosthenes
- Find Prime Factorisation of a Number using Sieve
- Power(n, x)
