I’ve taken a stab at the constant time variant of this problem. Interestingly enough at 64-bits its not enough of a value add for it to be faster than the simpler iterative method, even when I inlined getAdjacentPolarBits. See GitHub gist for code:
Also there is some wording that I think might have been missed (at least in EPI Java). On page 30, there is a section that goes:
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 new one is 2^k1 - 2^k2.
Isn’t it a requirement that the bits be different? If you toggle such that you set or unset both k1 and k2, then absolute value of the difference is 2^k1 + 2^k2. So I think the passage should include that to make it more clear.
A little math leads to the correct approach. Suppose we flip the bit at index k1 and flip the bit at index k2, such that k1 > k2 and bit_string[k1] != bit_string[k2]. Then the absolute value of the difference between the original integer and new one is 2^k1 - 2^k2.