Speeding up the generation all bit strings with Hamming distance one
To start with, here is a trivial optimization you can perform: in the most inner loop, you store u, then have k = u - 1, then compare k + 1 to u, which corresponds to comparing k to u - 1. Basically your inner loop performs unneeded work; just set directly u to (i ^ j) - 1 and you will save some work. Here is the most inner loop once changed:

const int u = (i ^ j) - 1;

// https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
int k = u;
k |= k &gt;&gt; 1;
k |= k &gt;&gt; 2;
k |= k &gt;&gt; 4;
k |= k &gt;&gt; 8;
k |= k &gt;&gt; 16;

if (k == u)
{
    edges.emplace_back(j);
    edges.emplace_back(i);
}


It timed it on my computer and it was consistently a bit faster, which means that the compiler wasn't able to make this simple transformation.



On the other hand, we can notice an interesting pattern with your original code: k + 1 can only be equal to u when u is a power of \$2\$. Checking whether a number is a power of \$2\$ or (or \$0\$, but the formula you use already has a special case of \$0\$) is easily done: a power of \$2\$ has exactly one bit set, so you only have to check whether removing a set bit from an integer returns \$0\$ to check whether an integer is \$0\$ or a power of \$2\$. This comparison is so cheap that you can perform it first and perform your current check only when it is true:

const int u = (i ^ j);

if (not (u &amp; (u - 1))) // check whether u is 0 or a power of 2
{
    int k = u - 1;
    k |= k &gt;&gt; 1;
    k |= k &gt;&gt; 2;
    k |= k &gt;&gt; 4;
    k |= k &gt;&gt; 8;
    k |= k &gt;&gt; 16;

    if (k + 1 == u)
    {
        edges.emplace_back(j);
        edges.emplace_back(i);
    }
}


Now, correct me if I'm wrong, but if u is a power of two, you don't actually need to check anything else after (you don't need to round up to a power of \$2\$ since you know it's already one). You can simply remove all the k stuff. I mean, it was a wild guess, but the result were exactly the same on my computer. You can just check that u is a power of \$2\$ then emplace_back your values directly.