Bit Manipulation — Master Recap and Interview 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-cancellation
n ^ 0                   # == n: XOR identity element
(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 = [float('inf')] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
    i = bin(mask).count('1')   # number of assigned items so far
    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
# Total iterations across all masks: O(3^n)

# For k=3 appearances: use ones/twos bitmasks
ones, twos = 0, 0
for n in nums:
    ones = (ones ^ n) & ~twos   # update ones using old twos
    twos = (twos ^ n) & ~ones   # update twos using new ones
# ones holds bits seen exactly once mod 3

# Python
bin(n).count('1')
 
# C/C++
__builtin_popcount(n)
 
# Java
Integer.bitCount(n)
 
# JavaScript
n.toString(2).split('').filter(x => x === '1').length