找到具有相同权重O(1)的最接近的整数

Question

我正在解决这个问题:

整数的二进制表示中的1的计数称为该数字的权重.以下算法查找具有相同权重的最接近的整数.例如,对于123(0111 1011)2,最接近的整数是125(0111 1101)2.

O(n)的解决方案,其中n是输入数字的宽度,是通过交换不同的第一对连续位的位置.

有人可以在O(1)运行时和空间中给我一些解决方法吗？

谢谢

Answer 1

正如ajayv已经评论过的那样,在O(1)中无法真正完成,因为答案总是取决于输入的位数.但是,如果我们将O(1)解释为意味着我们将一些原始整数数据作为输入,并且我们对该整数执行的所有逻辑和算术运算都是O(1)(在位上没有循环),问题可以在恒定的时间内解决.当然,如果我们从32位整数更改为64位整数,则运算时间会增加,因为算术运算在硬件上需要更长的时间.

一种可能的解决方案是使用以下功能.第一个让你只在那里的最低设置位的数x设置

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

第二个是未设置的最低位

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

如果你在纸上做了很少的例子,你会看到它们是如何工作的.

现在,您可以使用这两个函数找到需要更改的位,然后使用您已描述的算法.

一个c ++实现(不检查没有答案的情况)

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;
}

Answer 2

为了以O(1) 的时间复杂度解决这个问题，可以认为有两种主要情况：

1) 当LSB为“0”时：

在这种情况下，第一个“1”必须向右移动一个位置。

Input : "10001000" 

Out ::: "10000100" 

2) 当LSB为“1”时：

在这种情况下，第一个“0”必须设置为“1”，第一个“1”必须设置为“0”。

Input : "10000111" 

Out ::: "10001110" 

Java 中的下一个方法代表一种解决方案。

Input : "10001000" 

Out ::: "10000100"