Bit Manipulation

Count how many 1s appear in the binary form of a number.

Start here in Foundations →

In plain English: Count how many 1s appear in the binary form of a number.

n & (n-1) clears the lowest set bit each time — loop until n is zero and count the iterations.

def count_bits(n):
    count = 0
    while n:
        n &= n - 1  # clear lowest set bit
        count += 1
    return count

# Test: count_bits(11) == 3  (1011 in binary)
# Test: count_bits(128) == 1  (10000000)
# Test: count_bits(0) == 0

In plain English: Determine if a number is an exact power of 2 (like 1, 2, 4, 8, 16, ...).

A power of 2 has exactly one set bit. n & (n-1) clears it, leaving 0 — if not a power of 2, other bits remain.

def is_power_of_two(n):
    # exactly one set bit means power of 2; n-1 flips it and all lower bits
    return n > 0 and (n & (n - 1)) == 0

# Test: is_power_of_two(16) == True
# Test: is_power_of_two(18) == False
# Test: is_power_of_two(1) == True

In plain English: Find the number that appears only once in an array where every other number appears exactly twice.

XOR is its own inverse: a ^ a = 0 and a ^ 0 = a. XORing all elements cancels pairs, leaving the unique element.

def single_number(nums):
    result = 0
    for x in nums:
        result ^= x  # pairs cancel: a ^ a = 0
    return result

# Test: single_number([2,2,1]) == 1
# Test: single_number([4,1,2,1,2]) == 4

In plain English: Flip the binary representation of a 32-bit number so the first bit becomes the last and vice versa.

Extract the lowest bit of n, place it at the correct reversed position in the result by shifting left, then shift n right. Repeat 32 times.

def reverse_bits(n):
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)  # shift result left, add lowest bit of n
        n >>= 1
    return result

# Test: reverse_bits(0b00000010100101000001111010011100) == 964176192
# Test: reverse_bits(0) == 0

In plain English: AND all integers from m to n together. Find the result without looping through every number.

Any bit that flips between m and n will become 0 in the AND. Shift both right until they match — the common prefix is the answer, shifted back.

def range_bitwise_and(m, n):
    shift = 0
    while m != n:
        m >>= 1
        n >>= 1
        shift += 1  # count how many bits differ
    return m << shift  # common prefix, shifted back

# Test: range_bitwise_and(5, 7) == 4   (101 & 110 & 111 = 100)
# Test: range_bitwise_and(0, 0) == 0
# Test: range_bitwise_and(1, 2147483647) == 0

In plain English: Count how many bits are different between two numbers.

XOR produces 1 at every position where the bits differ — then count the set bits in the XOR result.

def hamming_distance(x, y):
    xor = x ^ y  # 1s mark where bits differ
    count = 0
    while xor:
        xor &= xor - 1  # clear lowest set bit
        count += 1
    return count

# Test: hamming_distance(1, 4) == 2  (001 vs 100)
# Test: hamming_distance(3, 1) == 1  (11 vs 01)

Count the number of 1-bits in an integer.

Signals

• 'Count 1-bits' → Brian Kernighan's trick: n & (n-1) clears lowest set bit
• Loop until n is 0, count iterations

Check if n is a power of two.

Signals

• Power of 2 has exactly one set bit: 1, 10, 100, 1000...
• n & (n-1) == 0 iff exactly one bit is set

Every element appears twice except one. Find it.

Signals

• 'Appears twice except one' + 'O(1) space' → XOR cancellation
• a ^ a = 0, a ^ 0 = a. XOR all elements; pairs cancel, unique survives.

Reverse the bits of a 32-bit unsigned integer.

Signals

• 'Reverse bits' → extract from right, place from left
• Shift n right to read bits, shift result left to place them

Count positions where corresponding bits of two integers differ.

Signals

• 'Bits that differ' → XOR produces 1 where bits differ
• Then count set bits in the XOR result

Return the bitwise AND of all numbers in range [m, n].

Signals

• Any bit that flips between m and n becomes 0 in the AND
• Keep shifting both right until they match — the common prefix is the answer

XOR marks differing bits, then Brian Kernighan's trick counts them in O(k) where k is the number of set bits.

xor = x ^ y
count = 0
while xor:
    xor &= xor - 1  # clear lowest set bit
    count += 1

Recursive node counting teaches divide-and-conquer tree thinking.

def count(node):
    if not node: return 0
    return 1 + count(node.left) + count(node.right)

Loop over all nodes, DFS/BFS from unvisited ones, increment count each time. Works on adjacency list or matrix.

visited = set()
count = 0
for node in range(n):
    if node not in visited:
        count += 1
        stack = [node]
        while stack:
            cur = stack.pop()
            if cur in visited: continue
            visited.add(cur)
            stack.extend(graph[cur])

Iterative binary exponentiation handles negative exponents. Same as pow(x, n).

def power(x, n):
    res = 1
    if n < 0: x, n = 1/x, -n
    while n:
        if n & 1: res *= x
        x *= x
        n >>= 1
    return res

XOR cancellation finds the element appearing an odd number of times. O(n) time, O(1) space — no hash map needed.

result = 0
for x in nums:
    result ^= x
# pairs cancel: a ^ a = 0, only unique remains

The generic expand-right / shrink-left template handles all variable-length window problems.

l = 0
for r in range(len(s)):
    # add s[r]
    while invalid():
        # remove s[l]
        l += 1

Flood-fill DFS: mark visited by changing '1' to '0'. Each DFS call covers one island. Count DFS starts.

def numIslands(grid):
    m, n = len(grid), len(grid[0])
    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
            return
        grid[i][j] = '0'  # mark visited
        dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)

    count = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
    return count