Lesson 3 � Intermediate

Bit Manipulation Tricks

Bit manipulation se tum binary numbers ke saath directly kaam kar sakte ho. Ye tricks interview mein bahut useful hain � O(1) mein power of 2 check karo, single number find karo, subsets generate karo!

? 25 min✓ Intermediate✓ Basic binary

Basic Bit Operators

AND (&)

Dono bits 1 hone chahiye result 1 ke liye. Masking ke liye use hota hai � specific bits isolate karna.

1010 & 1100 = 1000

OR (|)

Kam se kam ek bit 1 ho toh result 1. Bits set karne ke liye use hota hai.

1010 | 1100 = 1110

XOR (^)

Dono bits alag honi chahiye result 1 ke liye. Toggle karne ke liye use hota hai. Unique element find karne mein magic hai!

1010 ^ 1100 = 0110

Bit Shifts

# Left Shift: << (multiply by 2)
5 << 1 # 10 (5 * 2)
5 << 3 # 40 (5 * 8)
1 << 10 # 1024 (2^10)

# Right Shift: >> (divide by 2)
20 >> 1 # 10 (20 / 2)
20 >> 2 # 5 (20 / 4)
100 >> 3 # 12 (100 / 8, integer division)

# Binary representation
print(bin(5)) # 0b101
print(bin(5<<1)) # 0b1010
print(bin(5>>1)) # 0b10

Essential Bit Tricks

# 1. Check if ith bit is set
def is_bit_set(n, i):
 return (n >> i) & 1 == 1

# 2. Set the ith bit
def set_bit(n, i):
 return n | (1 << i)

# 3. Clear the ith bit
def clear_bit(n, i):
 return n & ~(1 << i)

# 4. Toggle the ith bit
def toggle_bit(n, i):
 return n ^ (1 << i)

# 5. Check if number is power of 2
def is_power_of_2(n):
 return n > 0 and (n & (n - 1)) == 0

# 6. Count set bits (Brian Kernighan's)
def count_bits(n):
 count = 0
 while n:
 n &= n - 1 # Clear lowest set bit
 count += 1
 return count

# Examples
print(is_bit_set(13, 2)) # True (13=1101, bit 2 is 1)
print(set_bit(5, 1)) # 7 (101 -> 111)
print(clear_bit(7, 1)) # 5 (111 -> 101)
print(is_power_of_16(16)) # True
print(is_power_of_2(18)) # False
print(count_bits(13)) # 3 (1101 mein 3 ones)

Magic Formula: n & (n-1) se lowest set bit clear hota hai. Agar ye 0 ke barabar aa gaya toh power of 2 hai! Kyunki power of 2 mein sirf ek hi bit set hoti hai � 1000 (8), 10000 (16).

Single Number

XOR ka sabse famous application � array mein ek element baar mein aata hai, baaki sab do baar:

def single_number(nums):
 result = 0
 for num in nums:
 result ^= num
 return result

# Example
nums = [4, 1, 2, 1, 2]
print(single_number(nums)) # 4

# Kyunki: 4 ^ 1 ^ 2 ^ 1 ^ 2
# = 4 ^ (1^1) ^ (2^2)
# = 4 ^ 0 ^ 0
# = 4

# XOR properties:
# a ^ a = 0 (same elements cancel)
# a ^ 0 = a (XOR with 0 is identity)
# a ^ b = b ^ a (commutative)
# (a^b)^c = a^(b^c) (associative)

Subset Generation using Bits

def subsets(nums):
 n = len(nums)
 result = []
 
 # 2^n subsets hain
 for mask in range(1 << n):
 subset = []
 for i in range(n):
 # Agar ith bit set hai toh element include karo
 if mask & (1 << i):
 subset.append(nums[i])
 result.append(subset)
 
 return result

# Usage
nums = [1, 2, 3]
for s in subsets(nums):
 print(s)
# []
# [1]
# [2]
# [1, 2]
# [3]
# [1, 3]
# [2, 3]
# [1, 2, 3]

Try it: code khud likho

Exercise

Question: Array [3, 3, 5, 5, 9] mein ek element sirf ek baar aata hai, baaki sab do baar. Wo element kya hai✓ Answer mein number daalo.

Question: Number 64 power of 2 hai ya nahi✓ Answer mein True ya False daalo.

Common mistakes

Operator precedence: n & 1 << i pehle 1 << i karega phir AND karega � ye galat hai! Hamesha brackets use karo: (n >> i) & 1.
Negative numbers: Right shift negative numbers pe implementation defined hai. Python mein sign extend hota hai. Hamesha positive numbers pe bit manipulation karo.
XOR vs OR confusion: XOR mein same bits cancel hote hain (a ^ a = 0), OR mein nahi (a | a = a). Single number problem XOR use karta hai, OR nahi.
Power of 2 check: n & (n-1) == 0 sirf power of 2 ke liye kaam karta hai. Zero ke liye special case lagao � n > 0 check karo.

Lesson complete?

Bit Manipulation tricks samajh aa gayi✓ Ab Interview Patterns dekhte hain � sab patterns ka comprehensive recap!