最重要設置位剩餘的未設置位數？

Question

假設64位整數0x000000000000FFFF這將表示爲

00000000 00000000 00000000 00000000 
00000000 00000000 >11111111 11111111 

如何找到未設置位的數量，以最顯著設置位的左邊（標有一個與>）？

Answer 1

// 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。

Answer 2

我不知道我是否正確理解問題。我認爲你有一個64位的值，並希望找到其中的前導零的數量。

一種方法是找到最重要的位，並簡單地從63中減去它的位置（假設最低位是位0）。您可以通過測試是否從一個循環內的所有64位設置位來找出最重要的位。

另一種方式可能是在gcc中使用（非標準）__builtin_clz。

Answer 3

相同的思路user470379's，但減計數...
假設所有的64位都沒有設置。當值大於0不停變動值權和遞減未設置位數：

/* untested */ 
int countunsetbits(uint64_t val) { 
    int x = 64; 
    while (val) { x--; val >>= 1; } 
    return x; 
} 

Answer 4

如果你正在處理的無符號整數，你可以這樣做：

#include <math.h> 
int numunset(uint64_t number) 
{ 
    int nbits = sizeof(uint64_t)*8; 
    if(number == 0) 
     return nbits; 
    int first_set = floor(log2(number)); 
    return nbits - first_set - 1; 
} 

我不知道它如何在性能上比較循環和計數已經提供的方法，因爲log2（）可能很昂貴。

編輯：

這可能會導致一些問題，高價值的整數，因爲log2()功能鑄造double和可能出現的一些數字問題。您可以使用log2l()函數與long double一起使用。更好的解決方案是使用this question中的整數log2()函數。

Answer 5

嘗試

int countBits(int value) 
{ 
    int result = sizeof(value) * CHAR_BITS; // should be 64 

    while(value != 0) 
    { 
     --result; 
     value = value >> 1; // Remove bottom bits until all 1 are gone. 
    } 
    return result; 
} 

Answer 6

在直C（久長是64位在我的設置），從類似的Java實現，採取：（更新多一點閱讀後的漢明權重）

多一點解釋：最上面的部分只是將最重要的1的所有位設置在右邊，然後否定它。 （即，最重要的1的'左'的所有0現在都是1，並且其他的都是0）。

然後我使用Hamming Weight實現來計數位。

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 7

我同意二進制搜索的想法。但有兩點是很重要的位置：

1. 有效回答你的問題的範圍是從0到64 包容。換句話說 - 可能有不同的問題答案。我認爲（幾乎可以肯定）所有發佈「二進制搜索」解決方案的人都錯過了這一點，因此他們在MSB位開啓時會得到錯誤的答案，無論是零還是數字。
2. 如果速度很關鍵 - 您可能想要避免循環。有一種使用模板來實現這一點的優雅方法。

以下模板東西正確任何無符號類型的變量發現MSB。

// helper 
template <int bits, typename T> 
bool IsBitReached(T x) 
{ 
    const T cmp = T(1) << (bits ? (bits-1) : 0); 
    return (x >= cmp); 
} 

template <int bits, typename T> 
int FindMsbInternal(T x) 
{ 
    if (!bits) 
     return 0; 

    int ret; 
    if (IsBitReached<bits>(x)) 
    { 
     ret = bits; 
     x >>= bits; 
    } else 
     ret = 0; 

    return ret + FindMsbInternal<bits/2, T>(x); 
} 

// Main routine 
template <typename T> 
int FindMsb(T x) 
{ 
    const int bits = sizeof(T) * 8; 
    if (IsBitReached<bits>(x)) 
     return bits; 

    return FindMsbInternal<bits/2>(x); 
} 

Answer 8

在這裏，你走了，很瑣碎的更新，因爲你需要其他尺寸...基於

int bits_left(unsigned long long value) 
{ 
    static unsigned long long mask = 0x8000000000000000; 
    int c = 64; 
    // doh 
    if (value == 0) 
    return c; 

    // check byte by byte to see what has been set 
    if (value & 0xFF00000000000000) 
    c = 0; 
    else if (value & 0x00FF000000000000) 
    c = 8; 
    else if (value & 0x0000FF0000000000) 
    c = 16; 
    else if (value & 0x000000FF00000000) 
    c = 24; 
    else if (value & 0x00000000FF000000) 
    c = 32; 
    else if (value & 0x0000000000FF0000) 
    c = 40; 
    else if (value & 0x000000000000FF00) 
    c = 48; 
    else if (value & 0x00000000000000FF) 
    c = 56; 

    // skip 
    value <<= c; 

    while(!(value & mask)) 
    { 
    value <<= 1; 
    c++; 
    } 

    return c; 
} 

Answer 9

：http://www.hackersdelight.org/HDcode/nlz.c.txt

template<typename T> int clz(T v) {int n=sizeof(T)*8;int c=n;while (n){n>>=1;if (v>>n) c-=n,v>>=n;}return c-v;} 

如果你想要一個版本允許你保持你的午餐下來，在這裏你去：

int clz(uint64_t v) { 
    int n=64,c=64; 
    while (n) { 
     n>>=1; 
     if (v>>n) c-=n,v>>=n; 
    } 
    return c-v; 
} 

正如您所看到的，您可以通過仔細分析彙編程序來節省這些週期，但這裏的策略並不可怕。 while循環將運行Lg [64] = 6次;每次它都會將問題轉換爲計算一半大小整數的前導位數。 while循環中的if語句提出這樣的問題：「我可以用一半的比特來表示這個整數」，或者類似地，「如果我把這個減半，我失去了它嗎？」。在if（）有效載荷完成後，我們的數字總是位於最低的n位。 在最後階段，v是0或1，這樣就可以正確完成計算。

Answer 10

使用日誌基地2，讓你最顯著的數字是1

log(2) = 1, meaning 0b10 -> 1 
log(4) = 2, 5-7 => 2.xx, or 0b100 -> 2 
log(8) = 3, 9-15 => 3.xx, 0b1000 -> 3 
log(16) = 4 you get the idea 

等等... 的數字日誌結果成爲分數之間。因此，將該值賦值給一個int將爲您提供最重要的數字。

一旦你得到這個數字，說b，簡單的64 - n將是答案。

function get_pos_msd(int n){ 
    return int(log2(n)) 
} 

last_zero = 64 - get_pos_msd(n)