3

我怎样才能找到最大的两个小于没有循环的数字的幂？例子：

5 output = 4.
11 output = 8.
100 output = 64.
4

6 回答 6

12

用 int 做的一个有点摆弄的方法是：

// given an int number (which would be the upper value of the range)
number |= number >> 1;
number |= number >> 2;
number |= number >> 4;
number |= number >> 8;
number |= number >> 16;
return (number >> 1) + 1;

这个想法是将 01010 之类的东西变成 01111，移位一次得到 00111，然后加一得到 01000 的结果。

要了解其工作原理，请考虑输入为 0 或非零。如果它是 0，那么结果是 0+1，因为所有的移位和 oring 只会导致 0（2 的 0 次方是 1，2 的最低幂，输入 0 的答案）。

对于非零数字，位中的某处是该值的最高有效设置位。我们想要的答案是该位没有跟踪它的所有次要有效位。所以专注于那一点，因为那是我们真正关心的。当我们对第一个右移 1 进行按位或运算时，我们确保设置的最高有效位仍然被设置，并且比它低 1 的位也被设置，因为 0100 | 0010 = 0110。接下来我们将其与自身进行 OR，但这次移动了 2。这确保我们有 MSB 加上 3 个尾随位。我们一直这样做，直到达到 int 中的位数限制。下面是一个完整的 32 位值示例的分步说明：

01000000110100111000000011010011

01000000000100000000000010000010 |
00100000000010000000000001000001 = 01100000000110000000000011000011 (num |= num >> 1)

01100000000110000000000011000011 |
00011000000001100000000000110000 = 01111000000111100000000011110011 (num |= num >> 2)

01111000000111100000000011110011 |
00000111100000011110000000001111 = 01111111100111111110000011111111 (num |= num >> 4)

01111111100111111110000011111111 |
00000000011111111001111111100000 = 01111111111111111111111111111111 (num |= num >> 8)

01111111111111111111111111111111 |
00000000000000000111111111111111 = 01111111111111111111111111111111 (num |= num >> 16)

现在剩下要做的就是将最终值右移一位，然后加一以将所有这些 1 变为 0，除了将我们所需答案的位设置为 1 的最高有效进位。

于 2013-01-25T17:51:37.807 回答
10

假设您想要小于 x 的 2 的最大幂，您可以从

Ans=pow(2,floor(log(x)/log(2)));
于 2013-01-25T17:52:15.017 回答
1

如果 n 是范围的最大数 

return int(math.log(n, 2));
于 2013-01-25T18:05:42.777 回答
0

您可以采用基于 2 的数字的对数，这将为您提供权力，或者，如果它是一个整数，则获取最高位集的位置（但这可能需要一个循环）。

我有一段时间没有做过 C++，但在 C# 中它会是：

        double val = 129;
        int power = (int)(Math.Log10(val) / Math.Log10(2));

使用 log n (X) = log y (X) / log y (n)的规则

于 2013-01-25T18:01:04.113 回答
0 
// This only works if i >= 0, and it may overestimate by one power of 2
// if i is slightly less than a large power of 2. Fixing these issues is
// not difficult, so it's left as an exercise.
long largest_power_of_two(long i) {
  int exp;
  frexp(double(i), &exp);
  return long(ldexp(0.5, exp));
}

frexp并且ldexp只是摆弄比特，所以那里甚至没有隐藏循环（可能在微架构层除外）。

于 2013-01-25T20:18:21.147 回答
0

如果可用，您可以使用特殊的 CPU 指令，例如 x86 BSR。

如果您可以在没有循环的情况下对数字进行位还原（也许，使用查找表或其他特殊的 CPU 指令），那么您可以还原数字，找到设置为 1 的最低有效位，重置其他位并将其还原。

unsigned IsolateLeastSignificantOne(unsigned n)
{
  return n & -n;
}

n = BitRevert(IsolateLeastSignificantOne(BitRevert(n)));

有关小技巧和其他有用的信息，请参阅此文档。

于 2013-01-26T04:33:54.067 回答