Bit Manipulation

# Basic bitwise operations - your bit toolkit! a = 12 # 1100 in binary b = 10 # 1010 in binary # AND (&) - Both bits must be 1 # Like: "Do you have BOTH permissions?" print(f"{a} & {b} = {a & b}") # 12 & 10 = 8 (1000) # OR (|) - At least one bit must be 1 # Like: "Do you have ANY permission?" print(f"{a} | {b} = {a | b}") # 12 | 10 = 14 (1110) # XOR (^) - Bits must be different # Like: "Toggle the switch!" print(f"{a} ^ {b} = {a ^ b}") # 12 ^ 10 = 6 (0110) # NOT (~) - Flip all bits # Like: "Invert everything!" print(f"~{a} = {~a}") # ~12 = -13 (two's complement) # Left shift (<<) - Multiply by 2^n # Like: "Double it n times!" print(f"{a} << 2 = {a << 2}") # 12 << 2 = 48 (12 * 4) # Right shift (>>) - Divide by 2^n # Like: "Halve it n times!" print(f"{a} >> 2 = {a >> 2}") # 12 >> 2 = 3 (12 / 4)

def check_bit(n, i): """Check if ith bit is set (1 or 0)""" return (n & (1 << i)) != 0 def set_bit(n, i): """Set ith bit to 1""" return n | (1 << i) def clear_bit(n, i): """Clear ith bit (set to 0)""" return n & ~(1 << i) def toggle_bit(n, i): """Toggle ith bit (0→1 or 1→0)""" return n ^ (1 << i) def count_set_bits(n): """Count number of 1s (Brian Kernighan's algorithm)""" count = 0 while n: n &= n - 1 # Remove rightmost set bit count += 1 return count # Examples n = 28 # 11100 in binary print(f"Number: {n} (binary: {bin(n)})") print(f"Bit 2 is set: {check_bit(n, 2)}") # True print(f"Set bit 0: {set_bit(n, 0)}") # 29 print(f"Clear bit 3: {clear_bit(n, 3)}") # 20 print(f"Count set bits: {count_set_bits(n)}") # 3

def is_power_of_two(n): """Check if number is power of 2 Powers of 2 have exactly one bit set! Examples: 1(1), 2(10), 4(100), 8(1000) """ return n > 0 and (n & (n - 1)) == 0 def next_power_of_2(n): """Find next power of 2 greater than n""" if n <= 0: return 1 n -= 1 # Handle case where n is already power of 2 n |= n >> 1 n |= n >> 2 n |= n >> 4 n |= n >> 8 n |= n >> 16 return n + 1 # Fast multiplication/division by powers of 2 def multiply_by_power_of_2(n, power): return n << power # n * 2^power def divide_by_power_of_2(n, power): return n >> power # n / 2^power # Examples print(f"Is 16 power of 2? {is_power_of_two(16)}") # True print(f"Is 18 power of 2? {is_power_of_two(18)}") # False print(f"Next power of 2 after 10: {next_power_of_2(10)}") # 16 print(f"5 * 8 = {multiply_by_power_of_2(5, 3)}") # 40

def swap_without_temp(a, b): """Swap two numbers without temporary variable""" a = a ^ b b = a ^ b # b = (a^b)^b = a a = a ^ b # a = (a^b)^a = b return a, b def find_single_number(nums): """Find the single number when all others appear twice XOR properties: a^a=0, a^0=a, XOR is commutative """ result = 0 for num in nums: result ^= num return result def find_missing_number(nums, n): """Find missing number from 0 to n""" xor_all = 0 xor_array = 0 # XOR all numbers from 0 to n for i in range(n + 1): xor_all ^= i # XOR all numbers in array for num in nums: xor_array ^= num # Missing number = xor_all ^ xor_array return xor_all ^ xor_array # Examples print(f"Swap 5 and 7: {swap_without_temp(5, 7)}") # (7, 5) print(f"Single number in [2,2,1]: {find_single_number([2,2,1])}") # 1 print(f"Missing in [0,1,3]: {find_missing_number([0,1,3], 3)}") # 2

def generate_all_subsets(arr): """Generate all subsets using bit manipulation For n elements, iterate through 0 to 2^n - 1 Each bit represents whether to include element """ n = len(arr) subsets = [] # 2^n possible subsets for mask in range(1 << n): subset = [] for i in range(n): # Check if ith bit is set if mask & (1 << i): subset.append(arr[i]) subsets.append(subset) return subsets # Example: Generate all subsets of [1, 2, 3] arr = [1, 2, 3] subsets = generate_all_subsets(arr) print("All subsets:") for subset in subsets: print(subset) # Output: [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]

def traveling_salesman_dp(dist): """TSP using DP with bitmask dp[mask][i] = min cost to visit cities in mask, ending at i """ n = len(dist) all_visited = (1 << n) - 1 # dp[mask][last] = minimum cost dp = [[float('inf')] * n for _ in range(1 << n)] # Start from city 0 dp[1][0] = 0 for mask in range(1 << n): for last in range(n): if dp[mask][last] == float('inf'): continue # Try to visit each unvisited city for next_city in range(n): if mask & (1 << next_city): continue # Already visited new_mask = mask | (1 << next_city) dp[new_mask][next_city] = min( dp[new_mask][next_city], dp[mask][last] + dist[last][next_city] ) # Find minimum cost to visit all cities return min(dp[all_visited])