Clarification on 5.4 Solution

#1

The solution to the Closest Integer with Same Weight problem suggests that “This approach works because we want to change bits that are as far to the right as possible.” However, the previous example, (in the case where 1110 is not closer in weight than 1011 to 111) contradicts this (1011 has the fourth and third rightmost bit changed, whereas 1110 has the fourth and first rightmost bit changed).

Can anyone give a more specific justification for why the solution (swapping the first set of consecutive bits that differ) is correct?

I’m reading version 1.5.1 btw

0 Likes
#2

If your question is to why the closest is achieved by taking the rightmost elements, a possible way to go about it is with a little math I guess.

Take the original int to be n, and two potential solutions n’ (rightmost swap) and n’’ (arbitrary swap)
n: 00101110 = 46
n’: 001011[01] = 45
n’’: 001[10]110 = 54

You can rewrite n’ as
n’=n-2^i+2^(i-1)
n’-n = -2^(i-1) , where i is the 0-based index of the leftmost switched element (=1 in our example, we switched the bit 1 and 0), so n’-n = -1, which is indeed 45-46.

More generally, the distance between the original and a potential solution when switching two consecutive bits is |n’-n| = 2^(i-1), taking n’’ as an example , the switch is done on i=4 then we have the distance between n and n’’: |n-n’’|=2^3=8, which is |46-54|.

So, because the distance is increasing wrt i, and because we want to minimize this distance, we chose the least i.
Hope it makes sense…

0 Likes
#3

Hey Ron,

Let me briefly explain why the algorithm works. Basically we want to difference value with the same weight, it means we should swap bits with different values—one 0 and one 1.

Since we want to have the closest one, it is important to know that the two bits are close will provide smallest difference. However, if you swap two bits who are different but close to the MSB, the difference is huge. For example, if the input in binary format is like 10000000000001. Swapping the first two bits (10) close to the MSB will generate an identical weight number but it is not the closest; because swapping the two bits (01) will have an identical weight number with much smaller difference. As a result, we want to swapping the two bits that are different and also closes to the right.

0 Likes
#4

A little math leads to the correct approach. Suppose we flip the bit at index $k1$ and flip the bit at index $k2$, $k1 > k2$. Then the absolute value of the difference between the original integer and the new one is $2^{k1} - 2^{k2}$. To minimize this, we should make $k1$ as small as possible and $k2$ as close to $k1$.

Since we must preserve the weight, the bit at index $k1$ has to be different from the bit in $k2$, otherwise the flips lead to an integer with different weight. This means the smallest $k1$ can be is the rightmost bit that’s different from the LSB, and $k2$ must the the very next bit.

In summary, the correct approach is to swap the two rightmost consecutive bits that differ.

I think this is clearer than the handwaving explanation (“make the change in the rightmost part of the input”).

Thanks for pointing this out, we will updated text in next release,

cheers,
adnan

0 Likes