Bit Manipulation Tricks: Essential Techniques for Interviews

# Basic bitwise operations

operations = {
    "& (AND)": "1 if both bits are 1",
    "| (OR)": "1 if either bit is 1",
    "^ (XOR)": "1 if bits are different",
    "~ (NOT)": "Inverts all bits",
    "<< (Left Shift)": "Shifts left, multiplies by 2^n",
    ">> (Right Shift)": "Shifts right, divides by 2^n"
}

# Examples
a, b = 5, 3  # 101, 011

print(a & b)   # 001 = 1
print(a | b)   # 111 = 7
print(a ^ b)   # 110 = 6
print(~a)      # -6 (two's complement)
print(a << 1) # 1010 = 10
print(a >> 1)  # 010 = 2

# Check if nth bit is set
def get_bit(num, n):
    return (num >> n) & 1

# Set nth bit
def set_bit(num, n):
    return num | (1 << n)

# Clear nth bit
def clear_bit(num, n):
    return num & ~(1 << n)

# Toggle nth bit
def toggle_bit(num, n):
    return num ^ (1 << n)

# Update nth bit to value
def update_bit(num, n, value):
    return (num & ~(1 << n)) | (value << n)

# Get rightmost set bit
def rightmost_set_bit(num):
    return num & (-num)  # -num = ~num + 1

# Clear rightmost set bit
def clear_rightmost_bit(num):
    return num & (num - 1)

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

# Check if odd or even
def is_odd(n):
    return n & 1

# Check if two numbers have opposite signs
def opposite_signs(a, b):
    return (a ^ b) < 0

# Check if nth bit is set
def is_nth_bit_set(n, i):
    return (n >> i) & 1

# Swap two numbers without temp
def swap(a, b):
    a = a ^ b
    b = a ^ b
    a = a ^ b
    return a, b

# Absolute value without branching
def abs_value(n):
    mask = n >> 31  # All 1s if negative
    return (n + mask) ^ mask

# Count set bits (Brian Kernighan's algorithm)
def count_set_bits(n):
    count = 0
    while n:
        n = n & (n - 1)  # Clear rightmost bit
        count += 1
    return count

# Built-in
def count_bits_python(n):
    return bin(n).count('1')

# Count bits needed to represent number
def bits_needed(n):
    if n == 0:
        return 1
    return n.bit_length()

# Reverse bits
def reverse_bits(n):
    result = 0
    for i in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

# Create mask with n bits set
def create_mask(n):
    return (1 << n) - 1

# Extract lowest n bits
def extract_low_bits(num, n):
    return num & ((1 << n) - 1)

# Extract highest n bits
def extract_high_bits(num, n):
    return num >> (num.bit_length() - n)

# Check if num is in range [a, b]
def in_range(num, a, b):
    mask = create_mask(b.bit_length() + 1)
    return ((num - a) & ~((b - a) & mask)) == 0

# Find element that appears once (others appear twice)
def single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

# Find two numbers appearing once
def two_single_numbers(nums):
    # XOR all
    xor_all = 0
    for num in nums:
        xor_all ^= num
    
    # Find rightmost set bit
    rightmost = xor_all & (-xor_all)
    
    # Partition and XOR
    a = b = 0
    for num in nums:
        if num & rightmost:
            a ^= num
        else:
            b ^= num
    
    return [a, b]

# Find missing number in array [0, n]
def missing_number(nums):
    result = len(nums)
    for i, num in enumerate(nums):
        result ^= i ^ num
    return result

# Find missing two numbers
def find_missing_two(nums):
    xor = 0
    for i, num in enumerate(nums):
        xor ^= i ^ num
    xor ^= len(nums)
    xor ^= len(nums) + 1
    
    rightmost = xor & (-xor)
    
    a = b = 0
    for i, num in enumerate(nums):
        if i & rightmost:
            a ^= i
        else:
            b ^= i
    
    for num in nums:
        if num & rightmost:
            a ^= num
        else:
            b ^= num
    
    return [a, b]

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

# Check if power of 4
def is_power_of_4(n):
    if n <= 0:
        return False
    # Power of 2 AND has only 1 bit in odd position
    return (n & (n - 1)) == 0 and (n & 0x55555555) != 0

# Check if power of 8
def is_power_of_8(n):
    if n <= 0:
        return False
    # Only 1 bit set AND bit index is multiple of 3
    return (n & (n - 1)) == 0 and n.bit_length() % 3 == 1

# Multiply by 2
def multiply_2(n):
    return n << 1

# Divide by 2
def divide_2(n):
    return n >> 1

# Multiply by any constant
def multiply(n, k):
    result = 0
    while k:
        if k & 1:
            result += n
        n <<= 1
        k >>= 1
    return result

# Divide without division
def divide(dividend, divisor):
    sign = (dividend < 0) ^ (divisor < 0)
    dividend = abs(dividend)
    divisor = abs(divisor)
    
    result = 0
    while dividend >= divisor:
        temp = divisor
        count = 1
        while dividend >= (temp << 1):
            temp <<= 1
            count <<= 1
        dividend -= temp
        result += count
    
    return -result if sign else result

# Find duplicate (if all numbers 1 to n)
def find_duplicate(nums):
    slow = fast = nums[0]
    
    # Find intersection
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    
    # Find entrance to cycle
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    
    return slow


# Find missing and duplicate
def find_missing_duplicate(nums):
    xor = 0
    for i, num in enumerate(nums + [len(nums) + 1]):
        xor ^= i ^ num
    
    rightmost = xor & -xor
    
    a = b = 0
    for i, num in enumerate(nums + [len(nums) + 1]):
        if i & rightmost:
            a ^= i
        else:
            b ^= i
        
        if num & rightmost:
            a ^= num
        else:
            b ^= num
    
    # Determine which is which
    for num in nums:
        if num == a:
            return [a, b]  # [duplicate, missing]
    
    return [b, a]

# Quick reference

tricks = {
    "power of 2": "n > 0 and (n & n-1) == 0",
    "rightmost bit": "n & -n",
    "clear rightmost": "n & (n-1)",
    "set bits count": "while n: n &= n-1; count += 1",
    "swap": "a ^= b; b ^= a; a ^= b",
    "abs": "(n + mask) ^ mask where mask = n >> 31",
    "max": "b ^ ((a ^ b) & -(a < b))",
    "min": "a ^ ((a ^ b) & -(a < b))"
}