确定是否在整数数据类型中设置位的最快方法

我有一个方法，根据某些特定的算法计算哈希值。

uint8_t cal_hash(uint64_t _in_data) { uint8_t hash; // algorithm // bit at hash[0] = XOR of some specific bits in _in_data // repeat above statement for other indexed bits of hash return hash; } 

我想知道什么是最有效的访问方式，并在整数数据类型中设置相应的位。 我已经尝试过类似的东西

 (((x) & (1<<(n)))?1:0) 

确定任何索引处的位是1还是0。 有什么比这更好的？

Answer 1

我认为这是一个速度与内存类型的问题。 （更新了MrSmith42s的建议）：

如果你真的想要速度，我会为每个比特定义一个掩码进行比较。 也许是这样的：

 const uint8_t BitMask[] = { 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80 }; /* Find out if LSB is set */ if( hash & BitMask[0] ) { ... } 

移位的问题在于它每个移位使用一个指令，而固定掩码在比较之前只有一个存储器访问。

Answer 2

您首先要关注的是拥有正确且可移植的版本。 现在，编译器将非常巧妙地优化这种位操作。

您应该始终注意您使用的掩码与您正在测试的数据类型相对应。 使用int或unsigned可能是不够的，因为你对uint64_t的位感兴趣并且移位超过位是未定义的行为。

在你的情况下，你可能会使用类似的东西

 (UINT64_C(1) << (n)) 

为了面具。 如果您想以更通用的方式执行此操作，则必须通过类似的方式获得1个基本类型

 (1 ? 1U : (X)) 

完全在宏观中

 #define MASK(X, N) ((1 ? 1U : (X)) << (N)) 

然后测试看起来像

 #define BIT(X, N) !!((X) & MASK(X, N)) 

Answer 3

要查找快速设置的位，请尝试以下操作：

 int oneBit = x & ~(x-1); 

在此之后， oneBit将只有X set的最低位。
（例如，如果x是1011 0100 ，oneBit将是0000 0100 ，例如，只是最低位）

之后，您可以关闭最低位：

 x &= x-1; 

（例如：如果x为1011 0100 ，则新x应为1011 0000 ）

然后，您可以重复第一个操作以查找已设置的下一个最低位。

这有一个很大的好处，你不会花时间“测试”一点，只是发现它的零。
它可以直接找到设置的那些位，并跳过零位。

以下示例代码显示了它的运行情况：

 int main(void) { int x = 180; // 1011 0100 while (x) { printf("Low Bit is: %d\n", x & ~(x-1)); x &= (x-1); } } 

输出：

 Low Bit is: 4 // eg. 0000 0100 Low Bit is: 16 // eg. 0001 0000 Low Bit is: 32 // eg. 0010 0000 Low Bit is: 128 // eg. 1000 0000