closest_int_same_weight.md

Find a Closest Integer with the Same Weight

The weight of a nonnegative integer is the number of 1-bits it has. Given a nonnegative integer x, find an integer y with the same weight.

Example

74 in binary = 1001010
The weight of 74 is 3.
The closest integer would be 73.
73 in binary = 1001001
The weight of 73 is also 3.

Solution

def closest_int_same_bit_count(x):
    for i in range(63):
        bit_i = x >> i & 1
        bit_j = x >> i + 1 & 1
        if bit_i != bit_j:
            x ^= 1 << i
            x ^= 1 << i + 1
            return x

Explanation

1. Loop through all the bits, starting at the least significant bit — stop when the i-th bit and the bit to its left (j-th bit) differ
2. Swap the i-th and j-th bit, which preserves the weight

Code Dissection

1. Iterate through all 64 bits

   for i in range(63):

2. Extract the i-th bit, which starts at the least significant bit

   bit_i = x >> i & 1

3. Extract the j-th bit, which is the bit to the left of the i-th bit

   bit_j = x >> i + 1 & 1

4. Check if the i-th bit and j-th bit differ

   if bit_i != bit_j:

5. Flip the i-th bit and j-th bit, which will make x a different integer while preserving the same weight

   x ^= 1 << i
   x ^= 1 << i + 1

6. Return the closest integer with the same weight

   return x

Useful References

• Python Wiki - Bitwise Operators
• tutorialspoint - Bitwise Operators Example