Gosper's Hack Algorithm

This post introduces Gosper’s Hack algorithm.

What is Gosper’s Hack Algorithm?

Hamming Weight is the number of bits set to 1 in a bit set. It is also called population count (popcount).

Gosper’s Hack is an algorithm that finds the next integer with the same Hamming Weight in O(1) time.

In other words, given an integer x, it finds the smallest integer y such that x < y and count_bit(x) == count_bit(y).

This algorithm was developed by the mathematician and computer scientist Bill Gosper and is used to solve combinatorial optimization problems.

Explanation

Suppose you are given a problem like: “Given an integer n, find all integers from 1 to n whose Hamming Weight is k.” How would you solve it?

Brute-Force

With brute force, you must count the set bits for every integer from 1 to n and compare it to k. That takes O(n log n), so as n grows, the runtime increases quickly. Not great for coding interviews.

def find_int_with_same_pop_counts(n: int, k: int) -> List[int]:
    answer = []

    for i in range(1, n + 1):
        j = i
        bits = 0
        while j > 0:
            bits += j & 1
            j >>= 1
        if bits == k:
            answer.append(i)

    return answer

Gosper’s Hack

With Gosper’s Hack, you do not need to scan all integers. You can generate exactly the values whose Hamming Weight is k in ascending order. How is that possible?

Calculation Summary

How do we find the smallest number that is larger than the current one while keeping the same Hamming Weight? Let us look at an example in binary.

The number must increase while keeping the number of 1-bits the same, so some 1-bit has to move to the left. Any 1-bit can be swapped with a 0-bit to its left to satisfy this condition.

101110 -> 110011, 110101, 110110, 111010, 111100...

Among those candidates, how do we get the smallest one? You may already see the pattern from the example.

To increase the number, at least one 1-bit must move left. To keep the result as small as possible, we swap the lowest-position 1-bit that has a 0 immediately to its left. Once that higher bit is set, any arrangement of the remaining 1-bits to the right will still produce a number larger than the original. Therefore, to minimize the result, we move the remaining 1-bits to the lowest positions.

101110 -> 110110 -> 110011

In summary, we compute the next number with the same Hamming weight by doing the following:

• Find the rightmost 1-bit that has a 0 to its left
• Add that bit value to flip the left 0-bit to 1 (via carry)
• Identify the 1-bits to the right of the flipped position
• Move those 1-bits all the way to the right

Bitwise Operations

To understand Gosper’s Hack, you should first understand three bitwise concepts.

Bitwise Operators

Bitwise operations use dedicated operators, and each operator (gate) has its own logical behavior.

Two’s Complement

Computers can implement arithmetic using addition circuits, so negative numbers are represented using two’s complement.

In general, a complement is a value that fills the gap to reach a target. In binary arithmetic, the target is 0. That is, the negative of a number is the value that produces 0 when added to the original.

How do we compute two’s complement? It is simple. For the 8-bit number 00000101, applying NOT (~) yields the ones’ complement 11111010. Adding 1 gives the two’s complement 11111011.

If you add the two’s complement (negative) back to the original, you get 00000101 + 11111011 = (1)00000000. In an 8-bit environment, the leftmost carry bit overflows and disappears, leaving 0. This is how subtraction can be implemented using only addition circuits: A - B = A + (-B) = A + (~B + 1).

Finding the Lowest Set Bit

Using the two’s complement property above, we can easily find the lowest set bit (the rightmost 1-bit).

 x     = 00000101
~x     = 11111010
~x + 1 = 11111011
x & -x = 00000001

The negative value (two’s complement) is computed by flipping all bits with NOT (~) and adding 1. In the two’s complement representation, all bits to the left of the rightmost 1-bit are inverted compared to the original, and all bits to the right become 0. Therefore, applying AND (&) with the original isolates exactly the value of the rightmost 1-bit.

With these concepts, Gosper’s Hack becomes straightforward.

Implementation

def find_int_with_same_pop_counts(n: int, k: int) -> List[int]:
    answer = []
    curr = (1 << k) - 1

    while curr <= n:
        answer.append(curr)

        lowest_bit = curr & -curr
        highest_bit = curr + lowest_bit
        changed_bits = curr ^ highest_bit
        changed_bits >>= 2
        trailing_ones = changed_bits // lowest_bit

        curr = highest_bit | trailing_ones

    return answer

This is an implementation of Gosper’s Hack. Below, we explain each line in terms of the summary above.

curr = (1 << k) - 1

This is the starting value. Shift 1 left by k and subtract 1 to create an integer consisting of exactly k 1-bits.

e.g. when k = 3, 1 << 3 = 1000, and 1000 - 1 = 0111.

while curr <= n:

This limits curr to be at most n.

lowest_bit = curr & -curr

This corresponds to “find the rightmost 1-bit”. As explained above, using two’s complement lets us isolate the value of the lowest set bit.

e.g. 100110 & 011010 = 000010.

highest_bit = curr + lowest_bit

This corresponds to “add that bit value to flip the left 0-bit to 1”. Adding 1 to the lowest-position 1-bit that has a 0 to its left propagates a carry until it reaches that 0-bit, effectively moving the bit one position to the left.

e.g. 100110 + 000010 = 101000.

Since the carry propagated through the lower bits, those bits become 0. At this point, highest_bit has the correct left part, but may have fewer than k set bits (i.e. count_bits(highest_bit) <= k).

changed_bits = curr ^ highest_bit

This corresponds to “identify the changed bits to the right”. XOR (^) keeps only the positions where the bits differ, so this produces a bit mask for the bits flipped during the carry process, including the 1-bits that were cleared.

e.g. 100110 ^ 101000 = 001110.

changed_bits >>= 2

This mask includes two bits that should not be moved (the flipped 0 and the leftmost 1 that remains), so shifting right by 2 discards them.

trailing_ones = changed_bits // lowest_bit

This corresponds to “move the remaining 1-bits to the far right”. Dividing by the lowest set bit removes the trailing zeros and right-aligns the remaining 1-bits. At this point, trailing_ones has the correct right part.

curr = highest_bit | trailing_ones

As described above, highest_bit has the correct left part, and trailing_ones has the correct right part. Combining them with OR (|) yields the next valid integer.

Time and Space Complexity

Each bitwise operation takes O(1), so generating the next combination takes O(1).

The number of combinations of choosing k bits from n is given by the binomial coefficient O(_nC_k). The algorithm loops exactly that many times, so the total time complexity is O(_nC_k).

It uses no recursion and no extra memory beyond a few variables, so the space complexity is O(1).

Applications

We learned another fast trick today. Nice. But where can we apply it beyond simple bit manipulation?

1. Enumerating all subsets of fixed size

You can apply it when you need all combinations of choosing k elements from n, as long as the combinations fit within an integer bitmask.

Gosper’s Hack enumerates all patterns with exactly k 1-bits. If you map each bit position to an element index, each integer becomes a combination.

2. Bitmask DP optimization

You can apply it when you only want to transition from states that have progressed exactly k steps among n total states.

A typical bitmask DP iterates all integers from 0 to 2^n − 1 and checks the number of set bits. Using Gosper’s Hack, you can iterate only the integers with exactly k bits set, skipping unnecessary states.

Practice Problems

LeetCode 401. Binary Watch

Find all combinations in a binary representation with k bits. You can apply Gosper’s Hack directly.

LeetCode 77. Combinations

Find all combinations of choosing k numbers from 1 to n. This is good practice for the fixed-size subset enumeration application.

LeetCode 1879. Minimum XOR Sum of Two Arrays

Reorder one array to minimize the XOR sum. This is a good place to practice the bitmask DP optimization application, but keep in mind that it is rated Hard.