algorithm - 找到最接近的具有相同权重 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;
}