I am looking for a fast way to generate k non-negative integers smaller than 2^64, of which, in base 2, the minimal Hamming distance between any two of the numbers is as high as possible.
For example, if I were looking for k=4 numbers and they should be smaller than 2^4 they could be:
0000
0011
1100
1111
And the minimal Hamming distance would be 2.
Is there a fast algorithm to generate those numbers for a given k? I will have k's in the order of 10^4.
Alternatively an algorithm generating a set of numbers, which have all pairwise an Hamming distance greater than a given value would work fine too.
Here's a fairly trivial way. Find the smallest number of bits = b that can express k different numbers. E.g. for k=4 use b = 2 bits. Divide 64 bits up into chunks of size 2. For each chunk, give each number to be generated a different number among the 2^b >= k available.
E.g. for k=4 numbers the b bits are 00, 01, 10, 11 and here are 4 possibilities:
0000
0101
1010
1111
If you have c chunks, then each number is different from each other number in at least one bit of each of c chunks, so the minimum guaranteed hamming separation is c.
You could also permute the selection of numbers within each chunk, which would produce more random looking examples such as
0011
0101
1000
1110