Find all x such that (x & (x+y)) == 0

Question

Given an unsigned 64-bit integer y, is there an efficient way to find all unsigned 64-bit integers x such that (x & (x + y)) == 0?

Some examples for small y:

• y=0: only possible solution x=0
• y=1: all solutions are of the form x=(1<<n)-1 for some n>=0
• y=2: all solutions are of the form x=(1<<n)-2 for some n>=1
• y=3: either x=(1<<n)-3, n>=2, or x=(1<<n)-2, n>=1

In general, the number of cases to consider depends on the number of runs of ones and zeros in the bit representation of y.

A solution to the problem could be an iterator function, that finds the next valid x, like the following:

uint64 next(uint64 x, uint64 y) {
    x++;
    while (x & (x+y)) x++;
    return x;
}

As the criterion (x & (x + y)) == 0 is rather simple, this might be a known problem for which a more efficient solution than the above is available.

Answer 1

For any given y, if x is a solution, then every suffix of x, including 0, is also a solution.

If you arrange the 64-bit integers into a tree such that each node's parent is a suffix formed by turning off the highest 1 bit, then the solutions will correspond to a subtree rooted at 0, and you can enumerate them by walking this tree.

Working from the root, then, if we have a solution x, then we need to find the new highest bits we could set that also produce valid solutions. Those are conveniently exactly the 1 bits in x+y that are greater than x. These can be efficiently enumerated, leading to an efficient recursive solution.

Here is an implementation in python. You can turn it into an iterator if you like:

def printSolutions(y, prevx=0, mask=0):
    print(prevx)
    bits = (prevx+y) & ~mask & ((1<<64)-1)
    while bits > 0:
        bit = bits & -bits
        bits -= bit
        x = prevx | bit
        printSolutions(y, x, bit | (bit-1))