[Coding test] 7. Bit

bit knowledge

So integers in python have a certain range. For 64 bit signed integer, we know bit 63 is the MSB.

1) positive - If bit 63 is 0, the number is positive (or zero). The maximum positive 64-bit integer is 0111...1111 (all bits 1 from 0 to 62, and bit 63 is 0), which equals 2^63−1.

2) negative - if bit 63 is 1, the number is negative. The smallest (most negative) 64-bit integer is 1000...0000 (bit 63 is 1, all other bits 0), which equals −2
63

OR

https://velog.io/@whitehousechef/Leetcode-898.-Bitwise-ORs-of-Subarrays
The number of distinct OR results is bounded by the number of different bit patterns that can exist after the OR operation.

v impt example

https://velog.io/@whitehousechef/Leetcode-2411.-Smallest-Subarrays-With-Maximum-Bitwise-OR

XOR

1^0 = 1
1^1 = 0
so if num^num, the result is 0. But if num^0, result is num.

check if bit i is set (value is 1)

# if ur iterating i from 0 to a certain bit like 63
# Check if bit i is set
if num & (1 << i):
if (num>>i) & 1:

either way is ok. left shift 1 by ith bits and comparing num's ith bit with 1 is the same as right shifting num by ith bit and comparing with 1.

set bit i

ans |= (1 << i)

MUST PUT BRACKETS around bit operations

so far u saw that all bit operations have brackets like (1<<i). If we dont put its wrong like

https://velog.io/@whitehousechef/Leetcode-2311.-Longest-Binary-Subsequence-Less-Than-or-Equal-to-K

if MSB (leftmost) bit is 1

Then it is a negative number which case we need to minus this current number (unsigned number) with the most negatiev number.

        # 1 << 63 creates a mask with only the 63rd bit set.
        if (ans & (1 << 63)) != 0:
            # If the 63rd bit is 1, subtract 2^64 to get the correct negative value.
            # This effectively converts the unsigned 64-bit interpretation to signed.
            ans -= (1 << 64)

Clear bit i

mask &= ~(1 << i)

Toggle bit i

mask ^= (1 << i)

Count set bits

bin(mask).count('1')

Iterate through all subsets

for mask in range(1 << n):

Iterate through submasks of mask

submask = mask
while submask > 0:
    # process submask
    submask = (submask - 1) & mask

example q

# 1. TRAVELING SALESMAN PROBLEM (TSP)
# Find minimum cost to visit all cities exactly once and return to start
def tsp(graph):
    n = len(graph)
    # dp[mask][i] = min cost to visit cities in mask, ending at city i
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0  # Start at city 0
    
    for mask in range(1 << n):
        for u in range(n):
            if not (mask & (1 << u)):  # u not in current set
                continue
            for v in range(n):
                if mask & (1 << v):  # v already visited
                    continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + graph[u][v])
    
    # Return to start city
    result = float('inf')
    full_mask = (1 << n) - 1
    for i in range(1, n):
        result = min

reverse bits

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

print(reverse_bits(4, 3))  # 1

32-bit multiplication with only 16-bit multiplication allowed

there is some maths.

u know when we do 1234*5678, we can split the multiplication like = (1200 + 34) × (5600 + 78)

so this 32 bit number can be slit into 16 bit parts like
A = [A_high | A_low]
where A_low = lower 16 bits → like the "last 4 digits"

A_high = upper 16 bits → like the "first 4 digits"

so for example if A = 123456789,
A_low = 52501 (like remainder after dividing by 65536)
A_high = 1883 (like quotient when dividing by 65536)

so the multiplication expansion is (65536 is 2^16)

A = A_high * 65536 + A_low
B = B_high * 65536 + B_low

A * B = (A_low * B_low)
      + (A_low * B_high * 65536)
      + (A_high * B_low * 65536)
      + (A_high * B_high * 65536^2)

so without bits is like

def multiply_32bit(a, b):
    base = 65536  # this is 2^16
    
    # Split numbers into high and low
    a_low = a % base
    a_high = a // base
    b_low = b % base
    b_high = b // base
    
    # Multiply pieces
    low_low = a_low * b_low
    cross   = a_low * b_high + a_high * b_low
    high_high = a_high * b_high
    
    # Recombine
    return low_low + (cross * base) + (high_high * base * base)

with bits where mask is hexadeciaml (base-16 of 16 1s). So its effectively 16 bit mask

def multiply_32bit_bitwise(a, b):
    mask = 0xFFFF  # 16-bit mask
    
    # Split numbers
    a_low  = a & mask
    a_high = a >> 16
    b_low  = b & mask
    b_high = b >> 16
    
    # Multiply pieces
    low_low    = a_low * b_low
    cross      = a_low * b_high + a_high * b_low
    high_high  = a_high * b_high
    
    # Recombine using bit shifts
    return low_low + (cross << 16) + (high_high << 32)