bit_manipulation.py

#Basic Tricks
Check if a number is odd/even
if ((n & 1) == 1) → odd
if ((n & 1) == 0) → even

Check if k-th bit is set
if ((n & (1 << k)) != 0) → k-th bit is 1

Set the k-th bit
n | (1 << k)

Clear the k-th bit
n & ~(1 << k)

Toggle (flip) the k-th bit
n ^ (1 << k)

Count set bits (Brian Kernighan’s Algo)
while(n > 0){
n = n & (n-1);
count++;
}

#Common Patterns
Swapping without temp variable
a = a ^ b;
b = a ^ b;
a = a ^ b;

Find the single number (all others appear twice)
int ans = 0;
for (int num : arr) ans ^= num;

Check power of 2
(n > 0) && (n & (n-1)) == 0

Extract the rightmost set bit
n & (-n)

Turn off the rightmost set bit
n & (n-1)

##Advanced Tricks
Subsets using bitmasks
for (int mask = 0; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
// i-th element is in the subset
}
}
}

XOR properties
x ^ x = 0
x ^ 0 = x

XOR is commutative & associative
Bitwise AND range (LC 201)
Keep shifting until m == n:

while(m < n){
n = n & (n-1);
}
return n;

BM 2: You are given an unsigned integer n. Return the number of 1 bits in its binary representation.
You may assume n is a non-negative integer which fits within 32-bits.

#Solution
def hammingWeight(self, n: int) -> int:
    count = 0
    for i in range(32):
        if n & (1 << i) > 0:
            count += 1
    return count 

def hammingWeight(self, n: int) -> int:
    c = 0
    while n:
        c += 1 if n & 1 else 0
        n >>= 1
    return c

BM 3: Given an integer n, count the number of 1's in the binary representation of every number in the range [0, n].
Return an array output where output[i] is the number of 1's in the binary representation of i.
#Solution
def countBits(self, n: int) -> List[int]:
    offset = 1
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        if offset * 2 == i:
            offset *= 2

        dp[i] = 1 + dp[i - offset]
    return dp