Find closest integer with the same weight

I am trying to solve this problem:

Write a program which takes as input a nonnegative integer x and returns a number y which is not equal to x, but has the same weight (same number of bits set to 1) as x and their difference is as small as possible.

This is my solution:

def closest_int_same_bit_count(x):
    k2 = (x^(x >> 1))
    k2 &= ~(k2-1)
    return x^(k2 << 1 | k2)

I know there are other posts with similar questions, I just want to know if this solution is correct.

  • It is a positive signed integer, or an unsigned integer?

    – 

  • @vakvakvak unsigned

    – 

It is correct, but there is a simpler option:

def closest_int_same_bit_count(x):
    y = -x & (x + 1)
    return x ^ (y | (y >> 1))

Leave a Comment