2 minute read

Integer with same weight - Elements of Programming Interviews (EPI)

Problem:

Let the weight of a nonnegative integer \(x\) be the number of bits set to 1 in its binary representation. Write a program which takes a nonnegative integer \(x\) as input and returns a number \(y\) which has the same weight as \(x\) such that their difference \(|y-x|\) is as small as possible. assume \(x\) will not be all 0s or all 1s in binary.

Solution:

A simple naive brute force solution would be to start from the neighbors of \(x\): check \(x-1\), \(x+1\) see if their weights are the same as \(x\) and keep going farther out \(x-2\), \(x+2\) and so on until we find a match.

If we think about it a little bit, we would start to look for the solution from the LSB and maybe try swapping it around with other bits. The thing to notice is that when swapping bits, the closest numbers we can form will be the result of swapping 2 neighboring bits. We can see this after some math or experimentation. If we choose 2 random bits to swap, \(k_1\) and \(k_2\). let \(k_1 > k_2\) so the resulting difference is going to be \(2^{k_1}-2^{k_2}\) to minimize this we would want \(k_1\) as small as possible and \(k_2\) as close to \(k_1\) as possible which would make them neighbors i.e \(k_2 = k_1 -1\). For this we would need to find 2 distinct neighboring bits such that \(k_1\) is minimized. So we can loop over all the bits from the right and swap the 2 rightmost consecutive bits that differ. This is the textbook’s solution with loop:

def closest_int_same_bit_count(x):
    NUM_UNSIGNED_BITS = 64
    for i in range(NUM_UNSIGNED_BITS - 1):
        if (x >> i) & 1 != (x >> (i + 1)) & 1:
            x ^= (1 << i) | (1 << (i + 1))  # swap bits
            return x

This is our solution without loops. We work with the lowest bit 0 and the lowest bit 1. We divide our problem into 3 cases which we check in order:

  1. The lowest 0 bit has a 1 neighbor to its right in which case we swap. 1101001100001111
  2. The lowest 0 bit has no 1 neighbor to its right but does have a 1 neighbor to its left in which case we swap. 1111000000000010
  3. The lowest 0 bit has no 1 neighbor in which case we simply extract the lowest 1 bit and swap it with the bit to its right. Since this case is only possible if we have trailing 0s in the binary representation like 1011100100000000.

This solution is in constant time and space and happens to answer the variant in the textbook too.

def closest_int_same_bit_count(x: int) -> int:
    """Function takes in 64-bit int and returns
    the closest int with the same weight (number
    of set bits)"""
    inverter = (1 << 64) - 1
    xi = x ^ inverter
    lsb_0 = xi & ~(xi - 1)  # least significant 0 in x.
    # if right of lsb_0 is swappable then swap (i.e shift 0 down)
    if lsb_0 >> 1 & x:
        return x ^ ((lsb_0 >> 1) | lsb_0)
    # if left of lsb_0 is swappable then swap (i.e shift 0 up)
    elif lsb_0 << 1 & x:
        return x ^ ((lsb_0 << 1) | lsb_0)
    # lowest 0 has no 1 as neighbor. swap lsb_1 to right.
    else:
        lsb_1 = x & ~(x - 1)
        return x ^ ((lsb_1 >> 1) | lsb_1)