位操作：该位被设置？ [英] Bit twiddling: which bit is set?

问题描述

我有完全相同1位集的64位无符号整数。我想一个值分配给每个可能的64个值的（在这种情况下，奇素数，所以为0x1对应于3，0X2对应于5，...，0x8000000000000000相当于313）。

I have a 64-bit unsigned integer with exactly 1 bit set. I'd like to assign a value to each of the possible 64 values (in this case, the odd primes, so 0x1 corresponds to 3, 0x2 corresponds to 5, ..., 0x8000000000000000 corresponds to 313).

这似乎是最好的办法是转换1 - > 0，2 - > 1，4 - > 2，8 - > 3，...，2 ^ 63 - > 63，并期待在价值观数组。但即便是如此，我不知道什么是最快的方式得到的二进制指数是。并有可能更快/更好的方式仍。

It seems like the best way would be to convert 1 -> 0, 2 -> 1, 4 -> 2, 8 -> 3, ..., 2^63 -> 63 and look up the values in an array. But even if that's so, I'm not sure what the fastest way to get at the binary exponent is. And there may be faster/better ways still.

此操作将被用于10 ¹⁴ 10 ¹⁶ 倍，所以性能是一个严重的问题。

This operation will be used 10¹⁴ to 10¹⁶ times, so performance is a serious issue.

推荐答案

如果性能是一个严重的问题，那么就应该使用内联函数/内建CPU使用的具体说明，如发现这里的海湾合作​​委员会的：

If performance is a serious issue, then you should use intrinsics/builtins to use CPU specific instructions such as the ones found here for gcc:

<一个href=\"http://gcc.gnu.org/onlinedocs/gcc-4.5.0/gcc/Other-Builtins.html\">http://gcc.gnu.org/onlinedocs/gcc-4.5.0/gcc/Other-Builtins.html

- 内置功能： INT __builtin_ffs（unsigned int类型X）
返回一加x的最小显著1位的索引，如果x为零，返回零。

— Built-in Function: int __builtin_ffs (unsigned int x) Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

- 内置功能： INT __builtin_clz（unsigned int类型X）
返回主导x中0位开始，最显著比特位置的数目。如果x为0，则结果是不确定的。

— Built-in Function: int __builtin_clz (unsigned int x) Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

- 内置功能： INT __builtin_ctz（unsigned int类型X）
返回以x尾随0位，开始于至少显著比特位置的数目。如果x为0，则结果是不确定的。

— Built-in Function: int __builtin_ctz (unsigned int x) Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.

像这样的事情有很多的O核心（1）算法，如这就需要找到一个位数组，标志着第一个非空队列调度内核

Things like this are the core of many O(1) algorithms such as kernel schedulers which need to find the first non-empty queue signified by an array of bits.

注意：我列出了 unsigned int类型版本，但海湾合作委员会也有无符号长长的版本。

NOTE: I've listed the unsigned int versions, but gcc also has unsigned long long versions as well.

这篇关于位操作：该位被设置？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！