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

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

使用这个：

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

它是如何工作的？

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

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

Answer 2

iBug的回答很有意思，没想到会这样。如果你在做大量的计算，你想多次找到最左边的数字，我会在 c++11 中推荐 __builtin_clz。如果您执行代码段

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

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

Answer 3

如果您对实际最快的答案感兴趣（至少在桌面上），这里是：使用英特尔编译器和 Clang 支持的 _bit_scan_reverse 内在函数（可能是 Visual Studio 和 GCC以及）。

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

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

Documentation

如果您担心可移植性（因为您应该使用像这样的所有专有扩展），只需包含一个回退函数并使用预处理器 select 您需要的实现：

#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 returns 是 n=0 的未指定值。如果这是一个问题，您可以在 bit_scan_reverse: return n == 0 ? 0 : _bit_scan_reverse(n); 中的代码中添加一个三元组。

Answer 4

Java 在 Integer class 中有一个名为 highestOneBit(int value) 的方法，其中 returns 一个 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 5

这叫做Find first set and most modern architectures have an instruction to do that quickly. In C++20 it can be done with std::countl_zero in the <bit> header

int left_most_bit_pos = sizeof(myInt)*CHAR_BIT - std::countl_zero(myInt);
int left_most_bit = myInt & (1 << left_most_bit_pos)

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

Getting the index of the leftmost active bit in an integer instantly

c++

bit-manipulation

built-in

bit

findfirst