Find the closest integer with same weight O(1)

Question

I am solving this problem:

The count of ones in binary representation of integer number is called the weight of that number. The following algorithm finds the closest integer with the same weight. For example, for 123 (0111 1011)₂, the closest integer number is 125 (0111 1101)₂.

The solution for O(n) where n is the width of the input number is by swapping the positions of the first pair of consecutive bits that differ.

Could someone give me some hints for solving in it in O(1) runtime and space ?

Thanks

Answer 1

As already commented by ajayv this cannot really be done in O(1) as the answer always depends on the number of bits the input has. However, if we interpret the O(1) to mean that we have as an input some primitive integer data and all the logic and arithmetic operations we perform on that integer are O(1) (no loops over the bits), the problem can be solved in constant time. Of course, if we changed from 32bit integer to 64bit integer the running time would increase as the arithmetic operations would take longer on hardware.

One possible solution is to use following functions. The first gives you a number where only the lowest set bit of x is set

int lowestBitSet(int x){
  ( x & ~(x-1) ) 
}

and the second the lowest bit not set

int lowestBitNotSet(int x){
  return ~x & (x+1);
}

If you work few examples of these on paper you see how they work.

Now you can find the bits you need to change using these two functions and then use the algorithm you already described.

A c++ implementation (not checking for cases where there are no answer)

unsigned int closestInt(unsigned int x){
  unsigned int ns=lowestBitNotSet(x);
  unsigned int s=lowestBitSet(x);
  if (ns>s){
    x|=ns;
    x^=ns>>1;
  }
  else{
    x^=s;
    x|=s>>1;
  }
  return x;
}