如何从二进制数中删除尾随零 [英] How to remove trailing zeros from a binary number

问题描述

我有一个类型为Long Long的整数，在删除该整数的二进制表示形式中存在的尾随零后，我要将其转换为新的整数。

推荐答案

以下是一种暴力方法：

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

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

unsigned long long remove_trailing_zeroes(unsigned long long v) {
    if (v != 0) {
        // 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;
}

Harold建议简化：

unsigned long long remove_trailing_zeroes(unsigned long long v) {
    if (v != 0) {
        // `-v`, which is `(~v + 1)` has all bits flipped except the least
        // significant 1 bit.
        // dividing v by `-v & v` shifts all trailing zero bits out,
        v /= -v & v;
    }
    return v;
}

可以简化为单个表达式：

unsigned long long remove_trailing_zeroes(unsigned long long v) {
    return v ? v / (-v & v) : v;
}

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

你可以在Bit Twiddling Hacks

这个迷人的词中找到其他方法

这篇关于如何从二进制数中删除尾随零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！