Generate all unordered pairs of bit strings with Hamming distance at most 2

Question

I'm looking for an efficient way to generate all unordered pairs of bit strings (represented as integers) that have Hamming distance at most 2. In this answer, it is shown how this is quite efficiently done for pairs having Hamming distance 1.

In other words, the answer above gives us all edges of the hypercube graph. Phrased in these terms, I'm looking for an efficient way to generate the edges of the square of a hypercube.

Is there some nice known fast method, perhaps similarly based on bit tricks?

Answer 1

There's an easy modification to Nate Kohl's answer.

int n = 3;
// examine all vertices from 0...2^n-1
unsigned long long max = 1ULL << n;  
for (unsigned long long vertex = 0; vertex < max; ++vertex) {
  std::cout << vertex << ':';
  // print all vertices that differ from vertex by one bit
  unsigned long long mask = 1;
  for (int shift_amt = 0; shift_amt < n; ++shift_amt) {
    std::cout << ' ' << (vertex ^ (mask << shift_amt));
  }
  for (int shift_amt1 = 0; shift_amt1 < n; ++shift_amt1) {
    for (int shift_amt2 = 0; shift_amt2 < shift_amt1; ++shift_amt2) {
      std::cout << ' ' << (vertex ^ (mask << shift_amt1) ^ (mask << shift_amt2));
    }
  }
  std::cout << '\n';
}