Bit Manipulation: XOR Tricks and Bitmasking

AND  (&): 1 only if both bits are 1
OR   (|): 1 if either bit is 1
XOR  (^): 1 if bits differ
NOT  (~): flip all bits
SHL  (<<): multiply by 2^k
SHR  (>>): divide by 2^k (floor)

# Get k-th bit (0-indexed from right)
def get_bit(n, k): return (n >> k) & 1

# Set k-th bit
def set_bit(n, k): return n | (1 << k)

# Clear k-th bit
def clear_bit(n, k): return n & ~(1 << k)

# Toggle k-th bit
def toggle_bit(n, k): return n ^ (1 << k)

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

# Count set bits (Brian Kernighan)
def popcount(n):
    count = 0
    while n:
        n &= n - 1  # remove lowest set bit
        count += 1
    return count

# Lowest set bit
def lsb(n): return n & (-n)

# Remove lowest set bit
def remove_lsb(n): return n & (n-1)

# XOR tricks
# a ^ a = 0
# a ^ 0 = a
# XOR is commutative and associative

# Find single element in array where all others appear twice
def single_number(nums):
    result = 0
    for n in nums:
        result ^= n
    return result

# Find two singles where all others appear twice
def two_singles(nums):
    xor = 0
    for n in nums: xor ^= n
    # xor = a ^ b; find any set bit
    diff_bit = xor & (-xor)
    a = 0
    for n in nums:
        if n & diff_bit:
            a ^= n
    return a, xor ^ a

#include <bits/stdc++.h>
using namespace std;

// Count set bits efficiently
int popcount(int n) { return __builtin_popcount(n); }
int popcount64(long long n) { return __builtin_popcountll(n); }

// Iterate all subsets of mask
void enumSubsets(int mask) {
    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
        // process sub
    }
}

// Iterate all subsets of size k of n elements
void enumKSubsets(int n, int k) {
    int sub = (1 << k) - 1;
    while (sub < (1 << n)) {
        // process sub
        int c = sub & (-sub);
        int r = sub + c;
        sub = (((r ^ sub) >> 2) / c) | r;  // Gosper's hack
    }
}

// XOR swap (no temp variable)
void xor_swap(int& a, int& b) { a ^= b; b ^= a; a ^= b; }

def tsp(dist):
    n = len(dist)
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at node 0, visited = {0}

    for mask in range(1 << n):
        for u in range(n):
            if not (mask >> u & 1): continue
            if dp[mask][u] == INF: continue
            for v in range(n):
                if mask >> v & 1: continue
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])

    full = (1 << n) - 1
    return min(dp[full][u] + dist[u][0] for u in range(n))