c++ - 如何找到数字的反对数(以 2 为底)？

Question

我使用 for 循环查找给定数字的反对数。

int g = 0, m, diff = 10;
for(j = 0; g <= diff; j++)
{
    g = pow(2, j);
}
m = j - 2;
cout << m;

它给出 2 的幂，其中 g 是刚好小于 diff 的数。

我尝试了对数的基数变化定理来找到像这样的数字的反对数:

m = log(diff) / log(2);

没有 for 循环，但在这种情况下，只要有一个数字是 2 的倍数(例如 8)，它就会给出 2 作为答案，而不是 3。

并且在程序中使用 for 循环这样做超出了时间限制。

是否有更短且可靠的方法来做到这一点？

Answer 1

这是一个没有循环的有趣解决方案:

function antilog(int input) {
  int pow2 = input - 1;
  pow2 |= pow2 >> 16; // turn on all bits < MSB
  pow2 |= pow2 >> 8;
  pow2 |= pow2 >> 4;
  pow2 |= pow2 >> 2;
  pow2 |= pow2 >> 1;
  pow2++; // get least pow2 >= input
  return  // construct binary offset of pow2 bit
      ((pow2 & 0xffff0000) != 0) << 4
    | ((pow2 & 0xff00ff00) != 0) << 3
    | ((pow2 & 0xf0f0f0f0) != 0) << 2
    | ((pow2 & 0xcccccccc) != 0) << 1
    | ((pow2 & 0xaaaaaaaa) != 0);
}

后半部分改编自bit twiddling hacks的部分内容. (了解来源，可能有一些其他功能比执行您所要求的更快。

除了解决方案，应该注意的是，导致您的解决方案缓慢的原因是重复调用 pow。 ，这是一个相对昂贵的功能。因为您正在进行整数运算(而且乘以 2，这是每台计算机最喜欢的数字)，所以将您的循环编写如下更有效:

int g=1,m,diff=10;
for(j = 0; g <= diff && g <<= 1; j++) /* empty */;
m=j-2;
cout<<m;

这真是太棒了。 int g=1将 g 初始化为它在代码第一次执行您编写的循环体时所采用的值。循环条件 g <= diff && g <<= 1评估为 g <= diff . (请注意，如果 diff >= 1 << (8 * sizeof(int) - 2) 是一个问题，我们可以将两个的最大幂存储在一个 int 中)。空语句只是让我们有一个格式良好的 for 语句，编译器(大部分)不会提示。