Bit Manipulation

मुख्य operators

& (AND) bits जांचता है, | (OR) bits सेट करता है, ^ (XOR) bits toggle करता है, ~ सभी bits पलटता है, और <</>> bits shift करते हैं — 2 की घातों से गुणा/भाग। ये एक ही CPU cycle में चलते हैं, इसलिए bit trick बेहद तेज़ होते हैं।

आम recipes

Position i पर एक bit check/set/clear करें, और classic n & (n-1) trick जो सबसे कम set bit हटा देता है — set bits गिनने या 2 की घात जांचने में उपयोगी।

def get_bit(n, i):
    return (n >> i) & 1

def set_bit(n, i):
    return n | (1 << i)

def clear_bit(n, i):
    return n & ~(1 << i)

def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)   # drops the lowest set bit
        count += 1
    return count

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

Output:

count_set_bits(11)      # 11 = 0b1011 -> 3
is_power_of_two(16)     # True

अकेला number खोजने के लिए XOR

XOR खुद का उलटा है: x ^ x = 0 और x ^ 0 = x। हर element को XOR करने से जोड़े कट जाते हैं, केवल अकेला value बचता है।

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

Output:

single_number([4, 1, 2, 1, 2])  # 4

जब bits काम आते हैं

DP में subsets दिखाने के लिए bitmasks इस्तेमाल करें (जैसे Travelling Salesman), visited states को compact रखें, या booleans के छोटे set को गति के लिए एक integer से बदलें।