如何从二进制数中删除结尾的零

Question

我有一个long long类型的整数，在删除二进制表示形式中存在的该整数的尾随零后，我想将其转换为新的整数。任何帮助，将不胜感激。

Answer 1

这里是蛮力方法：

long long remove_trailing_zeroes(long long v) {
    while (v && !(v & 1))
        v /= 2;
    return v;
}

这里是无符号数字的直接方法，但是除法可能比上面的迭代更昂贵：

unsigned long long remove_trailing_zeroes(unsigned long long v) {
    if (v) {
        // v and (v - 1) differ only in the trailing 0 bits plus 1
        // shifting v ^ (v - 1) right by 1 and adding 1 gives the power of 2
        // by which to divide v to remove all trailing 0 bits
        v /= (((v ^ (v - 1)) >> 1) + 1);
    }
    return v;
}

为了避免除法，您可以使用一种有效的方法来计算v ^ (v - 1)中的位数，然后将v右移一位。这也适用于0，因此您将获得无分支代码。

您可以在Bit Twiddling Hacks的迷人字词中找到其他方法>