How many intersections will two binary numbers have for a certain hamming distance?

143 Views Asked by At

Numerically, say I have two numbers: 00000 and 11000

Then I find out each of their HD=2 values:

For 00000 the list is:

5C2 possibilities

For 11000 the list is:

5C2 possibilities

My questions is how do I know the number of intersected binary numbers?

In this case, they are 6 [01001, 01010, 01100, ... 10100]

1

There are 1 best solutions below

22
On

Form the XOR of the two numbers. There can only be intersections if it has $0$, $2$ or $4$ ones. If it has $0$ ones, we need to modify both strings at the same two arbitrary bits, so the number of intersections is $\binom n2$, where $n$ is the length of the strings. If it has $4$ ones, we can choose $2$ bits at which to modify the one string and then modify the other string at the other two, so there are $\binom42=6$ intersections. If it has $2$ ones (as in your case), we can choose one of the two at which to modify the one string, modify the other string at the other, and then choose one more bit at which to modify both, so here we have $2(n-2)$ intersections (which in your case also comes out to $6$).