4

给定一个整数，如何从其二进制表示中去除前导零？

我正在使用按位运算符来操作它的二进制表示。我想看看一个整数在其二进制表示中是否是回文。我知道那里有不同的解决方案，但我想比较第一位和最后一位，第二位和最后一位，等等。所以，我想知道如何去掉这个 int 的前导 0。

4

4 回答 4

2

您可以使用BitScanForwardand BitScanReverse（确切的名称因编译器而异）从任一侧有效地修剪（好吧，跳过处理）零。

于 2012-04-27T02:09:54.063 回答
1

您可以通过查找数字的对数基数 2来查找设置的第一位：

/* 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];

或者，如果您需要一个面具，只需适应寻找 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;
于 2012-04-27T02:55:28.067 回答
1

如果您不介意使用字符串并且性能不是问题，您可以这样做：

    #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);
   ...
于 2016-06-29T19:02:41.087 回答
0

这是在如何检查整数的二进制表示是否是回文中发布的答案？

您首先使用此函数反转位：

/* 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;
于 2012-04-27T21:09:02.680 回答