在C/C++中除去二進制數中的前導零0

Question

給定一個整數，如何去除二進制表示中的前導零？

我正在使用按位運算符來操作它的二進制表示。我試圖看看一個整數是否是二進制表示中的迴文。我知道有不同的解決方案，但我想比較第一位和最後一位，第二位和最後一位，等等。所以，我想知道如何去掉這個int的前導0。

Answer 1

您可以使用BitScanForward和BitScanReverse（確切名稱因編譯器而異），以便從任何一方有效地修剪（以及跳過處理）零。

Answer 2

您可以通過找到設置的第一位log base 2 of the number：

/* from Bit Twiddling Hacks */ 
static const unsigned int MultiplyDeBruijnBitPosition[32] = 
{ 
    0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 
    8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 
}; 

uint32_t pos = value; 
pos |= pos >> 1; 
pos |= pos >> 2; 
pos |= pos >> 4; 
pos |= pos >> 8; 
pos |= pos >> 16; 
pos = MultiplyDeBruijnBitPosition[(uint32_t)(pos * 0x07C4ACDDU) >> 27]; 

或者，如果你需要一個面具，只適應finding the next power of 2：

/* adapted from Bit Twiddling Hacks */ 
uint32_t mask = value - 1; 
mask |= mask >> 1; 
mask |= mask >> 2; 
mask |= mask >> 4; 
mask |= mask >> 8; 
mask |= mask >> 16; 

Answer 3

這裏張貼在How to check if the binary representation of an integer is a palindrome?

答案

您首先使用此功能反轉位：

/* flip n */ 
unsigned int flip(unsigned int n) 
{ 
    int i, newInt = 0; 
    for (i=0; i<WORDSIZE; ++i) 
    { 
     newInt += (n & 0x0001); 
     newInt <<= 1; 
     n >>= 1; 
    } 
    return newInt; 
} 

然後取出尾隨零：

int flipped = flip(n); 
/* shift to remove trailing zeroes */ 
while (!(flipped & 0x0001)) 
    flipped >>= 1; 

要獲得關於檢查，看看是否int是迴文評論，只是與原來比較的移位翻轉版本：

return n == flipped; 

Answer 4

如果你不介意使用字符串和性能是不是可以做到這一點的一個問題：

#include <bitset> 
    #include <string> 
    using namespace std; 

    // your number 
    int N; 
    ... 

    // convert to a 32 bit length binary string 
    string bitstr = bitset<32>(N).to_string(); 

    // get the substring 
    int index = 0; 
    string strippedstr; 
    for(unsigned int i = 0; i < bitstr.length(); ++i) { 
     if(bitstr[i] == '1') { 
      index = i; 
      break; 
     } 
    } 
    strippedstr = bitstr.substr(index); 
    ...