Bit Manipulation — Master Recap & Cheatsheet

n & (n-1)        # Remove lowest set bit (Brian Kernighan)
n & (-n)         # Isolate lowest set bit
n | (n-1)        # Set all bits below lowest 1
~n + 1           # Two's complement (negation)
n ^ n == 0       # XOR self = 0 (cancel duplicates)
n ^ 0 == n       # XOR with 0 = identity
x ^ y == 0 iff x==y  # Equality check via XOR
(n >> i) & 1     # Get bit i
n | (1 << i)     # Set bit i
n & ~(1 << i)    # Clear bit i
n ^ (1 << i)     # Toggle bit i
n & (n-1) == 0 and n > 0  # Power of 2 check

dp = [inf] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
    i = bin(mask).count('1')  # number of assigned items
    for j in range(n):
        if not (mask & (1 << j)):  # j not yet used
            new_mask = mask | (1 << j)
            dp[new_mask] = min(dp[new_mask], dp[mask] + cost(i, j))

sub = mask
while sub:
    process(sub)
    sub = (sub - 1) & mask  # next smaller subset of mask

# Python
bin(n).count('1')

# C/C++
__builtin_popcount(n)

# Java
Integer.bitCount(n)

# JavaScript
n.toString(2).split('').filter(x=>x==='1').length