0

如何从左到右而不是从右到左扫描整数（二进制）？我知道我可以从左边开始尝试每一位，然后记录最左边的位，但是有更快的方法吗？是否有一个内置函数可以立即找到整数中最左边的活动位（即 1）？

我知道从右到左，我可以做类似的事情

int myInt = 1234;
for(int i = 0; i < 32; i++) {
  int curr_bit = myInt & (1 << i);
  // do something with curr_bit
}

但是，我想从最左边的可用位开始，我想要它的数字“x”，以便1 << x指向那个确切的数字（作为旁注，我正在尝试实现重复平方，我需要这个在我的代码）。

任何帮助将不胜感激！

4

5 回答 5

4

如果您对实际最快的答案感兴趣（至少在台式机上），这里是：使用_bit_scan_reverseIntel Compiler 和 Clang 支持的内在函数（也可能是 Visual Studio 和 GCC）。

#include "immintrin.h"
int main() { printf("%i", _bit_scan_reverse(9)); }

结果：（3因为1<<3 = 8是 中设置的最高位9）。

文档

如果您担心可移植性（因为您应该使用像这样的所有专有扩展），只需包含一个后备功能并使用预处理器来选择您需要的实现：

#ifdef __SSE__ // All SSE processors support bsf/bsr
#include "immintrin.h"
static inline int bit_scan_reverse(int n) { return _bit_scan_reverse(n); }
#else
// Fallback implementation here
#endif

请注意，_bit_scan_reverse 返回一个未指定的值n=0。如果这是一个问题，您可以在bit_scan_reverse:中的代码中添加一个三元组return n == 0 ? 0 : _bit_scan_reverse(n);。

于 2017-12-09T04:51:17.037 回答
2

这被称为查找第一组，大多数现代架构都有快速执行此操作的指令。在 C++20 中，它可以std::countl_zero在<bit>标题中完成

int left_most_bit_pos = sizeof(myInt)*CHAR_BIT - std::countl_zero(myInt);
int left_most_bit = myInt & (1 << left_most_bit_pos)
于 2021-04-16T03:36:49.573 回答
0

Java 在 Integer 类中有一个方法称为 highestOneBit(int value)，它返回一个 int 值，最多只有一位，位于指定 int 值中设置的最高有效位（最左边）的位置。它是这样实现的：

int highestOneBit(int value)
{
    value |= (value >>  1);
    value |= (value >>  2);
    value |= (value >>  4);
    value |= (value >>  8);
    value |= (value >> 16);
    return value - (value >> 1);
}
于 2017-12-09T05:24:52.257 回答
-1

用这个：

int left_most_bit = myInt & (1 << (sizeof myInt * CHAR_BIT - 1));

它是如何工作的？

  • sizeof myInt返回变量的大小（myInt以字节为单位）
  • CHAR_BIT是一个（可能）依赖于平台的宏，它告诉您一个字节中有多少位，通常为 8
  • 左移 1 得到最左边的位。

在 O(1) 时间内工作得很好，因为sizeof myInt和CHAR_BIT都是编译时常量，所以整个表达式(1 << (sizeof myInt * CHAR_BIT - 1))也是编译时常量。然后编译器可以对其应用最大优化。

于 2017-12-09T04:40:41.010 回答
-1

iBug 的回答很有趣，我从来没有想过这样做。如果您要进行大量计算，并且想要多次找到最左边的数字，我会__builtin_clz在 c++11 中推荐。如果您执行片段

for(int i = 31 - __builtin_clz; i >= 0; i--) {
    int left_most_bit = myInt & (1 << i);
}

这将从 left_most_bit 开始并向右移动。希望这可以帮助！ __builtin_clz 的实现

于 2017-12-09T04:48:38.253 回答