立即获取整数中最左边活动位的索引[重复]

Question

如何从左到右而不是从右到左扫描整数（二进制）？我知道我可以从左边开始尝试每一位，然后记录最左边的位，但是有没有更快的方法？是否有一个内置函数可以立即找到整数中最左边的有效位（即 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

将指向该确切的数字 （顺便说一句，我正在尝试实现重复平方，并且我的代码中需要这个）。

任何帮助将不胜感激！

Answer 1

寻找最高设定位属于寻找第一族，与寻找最低设定位有关。大多数现代架构都有一条快速找到最高设置位的指令。在 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)

Answer 2

如果您对实际最快的答案感兴趣（至少在桌面上），这里是：使用 Intel Compiler 和 Clang（也许还有 Visual Studio 和 GCC）支持的

_bit_scan_reverse

内在函数。

#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);

。

Answer 3

Java 在 Integer 类中有一个名为 HighestOneBit(int value) 的方法，该方法返回一个最多具有单个 1 位的 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);
}

Answer 4

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

__builtin_clz

。如果您执行片段

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

这将从最左边的位开始并向右移动。希望这有帮助！ __builtin_clz的实现

Answer 5

使用这个：

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))

也是编译时常量。然后编译器可以对其应用最大优化。