Bitwise operation and list of numbers

Question

I am looking for a list of group of 8 numbers less than or equal to 128 (2^7) in which every pair of numbers differ in 4 bit positions only. For Example (a shorter version): Consider for a group of 4 numbers, considering numbers less than or equal to 8, which differ in 2 bit positions are 1, 2, 4, 8.

More generally is there any algorithm (pseudo code) which helps me to find the required group of n number (n is always even) each of which is less than 2^(n-1) and in which every pair of number differs by exactly n/2 bit positions. We can assume n<=64.

EDIT: Also, tell the values of even number for which it doesn't exist at all. For example for n=6, there is no such solution.

Draco · Accepted Answer

One group of 8 numbers less than 128 in which every pair of numbers differs in 4 bit positions only would be 0, 15, 51, 60, 85, 90, 102, 105. That is:

00000000 (0)
00001111 (15)
00110011 (51)
00111100 (60)
01010101 (85)
01011010 (90)
01100110 (102)
01101001 (105)

We take 00000000 (0) as the starting point.

Since the numbers must differ in 4 bit positions, we can flip the last 4 bits to find the next number in the group, 00001111 (15).

To find the next number, since it must differ from both 0 and 15 by 4 bits, and they already differ from each other by 4 bits, we can tell that we need to flip 2 bits in the first 4 bits and 2 bits in the last 4 bits of the next number. In the interest of finding the numbers in ascending order, we flip bits 3 and 4, and pick the last 4 bits to match the first 4 bits. That is, bits 1-4 are now 0011, and we set bits 5-8 to match, and we find the next smallest number in the group to be 00110011 (51).

Note: We are arbitrarily setting bits 5-8 to match bits 1-4 because it is the simplest way to make sure that each number still differs from each other number by only 4 bits. The first half of the number does not repeat aside from the one time we flip all the bits in the second half, so the second half will always be different from every other number by the correct number of bits as well. Other methods should work as well, as long as you can keep track of the patterns you have already used and don't repeat them.

Again, we can simply flip the last 4 bits to find the next number in the group, 00111100 (60).

Again flipping bits in each half of the number, we set bits 1-4 to 0101 for the next lowest number, and set bits 5-8 to match, for 01010101 (85).

By the same methods as described above, we can find the rest of the numbers in the group to be 01011010 (90), 01100110 (102), 01101001 (105).

EDIT: Looking at the first half of the numbers, we picked the first 4 bits to be 0000. Then, since we want 2 bits to be different in that half of the number, we went up to 0011, then 0101, then finally 0110. Each of these numbers is the next highest number with only two bits set to 1. Note that we can't go any higher because the next number would start with 1001, and 10010000 would already be 144, which is higher than the given limit of 128. For each of these starting halves, we also pick the second half to be the same as the first for one number, and then flip all these bits for the second number, to find two numbers for the group every time we find a viable starting half.

This method should work in a more generalized case as well, flipping n/2 bits at a time. If you want to find larger groups of numbers, you may want to write a program to perform the operations for you. However, I haven't had a chance to test thoroughly yet, but I believe that this may only work where n is a power of 2.

EDIT 2: The other possibility that I was considering is that it works when n is divisible by 4. However, the method used above may not quite work and require adjusting. I was having problems flipping the appropriate number of bits while making sure each pair of numbers only differed by the correct number of bits.

For example, for n=12, with the above method, some of the first numbers we find are:

000000000000 (0)
000000111111 (63)
000111000111 (455)
000111111000 (504)

Do not include:
001011001011 (715)  Differs from 455 by the incorrect number of bits
001011110100 (756)  Differs from 504 by the incorrect number of bits

The problem is, I don't think there are enough numbers for the group by just applying the above method. However, you may be able to find enough numbers if you start looking for ones where the bit differences are not evenly in each half of the number (that is, for example, 2 bits in the first half of the number and 4 bits in the second half), but I was having issues finding a consistent and reliable method to find more of these numbers, since they also have to be different from each of the other numbers by the correct number of bits.

Bitwise operation and list of numbers

Answers (2)

Related Questions