1

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

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。还有什么比这更好的吗？

4

3 回答 3

3

Your first concern should be to have a correct and portable version. Compilers nowadays will then optimize such bit operations quite cleverly.

You should always take care that the mask you are using corresponds to the data type that you are testing. Using an int or unsigned might not be enough since you are interested in the bits of a uint64_t and shifting for more than there are bits is undefined behavior.

In your case you would probably use something like

(UINT64_C(1) << (n))

for the mask. If you want to do this in a more generic way you'd have to obtain a 1 of your base type by something like

(1 ? 1U : (X))

alltogether in a macro

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

and then the test could look like

#define BIT(X, N) !!((X) & MASK(X, N))
于 2013-08-09T08:02:43.717 回答
3

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

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

const uint8_t BitMask[] = { 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80 };

/* Find out if LSB is set */
if( hash & BitMask[0] ) { ... }

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

于 2013-08-09T08:07:15.440 回答
2

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

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

在此之后，oneBit将只设置 X 的最低位。
（例如，如果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
于 2013-08-09T16:41:00.027 回答