计算 4 的每个幂的倍数

Question

给定一个数 n，我需要有效地求出该数是小于给定数的 4 的所有次方的倍数。

例如：

16 是 4 和 16 的倍数，所以结果是 2。
64 是 4、16 和 64 的倍数，因此结果为 3。
256 是 4、16、64 和 256 的倍数，因此结果为 4。
14 不是 4 的任何次方的倍数，因此结果为 0。
35 不是 4 的任何次方的倍数，所以结果为 0。

按位运算是首选，这是一个非常紧密的循环，因此它处于需要高效的瓶颈内。目前我的代码是显而易见的答案，但我不得不相信有更多的数学方法可以用更少的步骤计算出结果：

power = 4;
while (power < n) {
    result += !(n & (power - 1));
    power *= 4;
}

Answer 1

数学会一直除以 4，直到结果不能再被 4 整除。

如果你真的想用按位运算来做，技术here可以用来计算尾随零位的数量（即一个值被2整除的次数） .可以调整这些以计算尾随位对（即被 4 的幂而不是 2 整除）。

请注意，您将需要使用 unsigned 值以避免某些未定义或未指定行为的情况。

我不同意你关于按位运算将提供更有效解决方案的断言。没有经过测试就不是给定的，尤其是对于现代编译器。

Answer 2

你可以使用对数。快速 Google 搜索 "fast log2 c++" 提出了一长串想法。那么你的答案是 log2(x)/2，如果你只想要 4 的精确幂的答案，你必须找到一些方法来确保你的结果是一个整数。

如果您正在为 x86 处理器编程，您可以使用 BitScanForward 和 BitScanReverse 找到设置位，并用它来计算 log2。以下代码在 Visual Studio 中有效，对于 GCC 或其他，还有其他方法可以进行内联汇编。

uint32_t exact_power_of_4_scan(uint32_t num)
{
  unsigned long reverse;
  unsigned long forward;

  if (!_BitScanReverse(&reverse, num)) return 0;
  _BitScanForward(&forward, num);

  if (reverse != forward) return 0; // makes sure only a single bit is set
  if (reverse & 0x1) return 0; // only want every other power of 2
  return reverse / 2;
}

如果您需要 portable 解决方案，table 查找可能是可行的方法，但更复杂。

uint8_t not_single_bit[256] = {
  1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1,
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
};

uint8_t log2_table[256] = {
  0, 0, 1, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0,
  4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

uint32_t exact_power_of_2(uint32_t num)
{
  auto a = not_single_bit[num & 0xff];
  auto b = not_single_bit[(num >> 8) & 0xff];
  auto c = not_single_bit[(num >> 16) & 0xff];
  auto d = not_single_bit[(num >> 24) & 0xff];

  if (a + b + c + d != 3) {
    return 0;
  }

  if (!a) {
    return log2_table[num & 0xff];
  }
  if (!b) {
    return log2_table[(num >> 8) & 0xff] + 8;
  }
  if (!c) {
    return log2_table[(num >> 16) & 0xff] + 16;
  }

  return log2_table[(num >> 24) & 0xff] + 24;
}

uint32_t exact_power_of_4(uint32_t num)
{
  auto ret = exact_power_of_2(num);

  if (ret & 0x1) return 0;
  return ret / 2;
}

都是线性算法。第一个可能会击败 num 的几乎任何值的循环，但我还没有测试过它。第二个可能只适用于较大的 nums。

计算 4 的每个幂的倍数

Count number of multiples against every power of 4

c++

bit-manipulation

bitwise-operators