cbinarybit-manipulationlong-integer

How to remove trailing zeros from a binary number


I have an integer of type long long that I want to convert to a new integer after removing the trailing zeros of that integer that are present in its binary representation.


Solution

  • Here is a brute force approach:

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

    Here is a direct approach for unsigned numbers, but the division might be more costly than the above iteration:

    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 suggested this simplification:

    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;
    }
    

    Which can be simplified as a single expression:

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

    To avoid the division, you could count the number of bits in v ^ (v - 1) with an efficient method and shift v right by one less than this number. This would work for 0 as well so you would get branchless code.

    You can find other methods in the fascinating word of Bit Twiddling Hacks.