最重要的设置位的未设置位数？

Question

假设64位整数0x000000000000FFFF表示为

00000000 00000000  00000000 00000000
00000000 00000000 >11111111 11111111

如何找到最重要的设置位(标有>的那个)左侧的未设置位数？

Answer 1

在直接C(长整数,我的设置为64位),取自类似的Java实现:(在更多关于汉明重量的阅读后更新)

更多解释:顶部只是将所有位置于最重要的1的右侧,然后否定它.(即,最重要的1的"左"的所有0现在都是1,其他一切都是0).

然后我使用汉明重量实现来计算位数.

unsigned long long i = 0x0000000000000000LLU;

i |= i >> 1;
i |= i >> 2;
i |= i >> 4;
i |= i >> 8;
i |= i >> 16;
i |= i >> 32;
// Highest bit in input and all lower bits are now set. Invert to set the bits to count.
i=~i;

i -= (i >> 1) & 0x5555555555555555LLU; // each 2 bits now contains a count
i = (i & 0x3333333333333333LLU) + ((i >> 2) & 0x3333333333333333LLU); // each 4 bits now contains a count
i = (i + (i >> 4)) & 0x0f0f0f0f0f0f0f0fLLU; // each 8 bits now contains a count 
i *= 0x0101010101010101LLU; // add each byte to all the bytes above it
i >>= 56; // the number of bits

printf("Leading 0's = %lld\n", i);

我很想知道这是多么有效率.虽然测试了几个值,它似乎工作.

Answer 2

// clear all bits except the lowest set bit
x &= -x;     

// if x==0, add 0, otherwise add x - 1. 
// This sets all bits below the one set above to 1.
x+= (-(x==0))&(x - 1);

return 64 - count_bits_set(x);

您可以在哪里count_bits_set找到最快的位数计数版本。有关各种位计数技术，请参阅https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel 。