Number of zero bits in integer except leading zeros

Question

If I have an integer in Java how do I count how many bits are zero except for leading zeros?

We know that integers in Java have 32 bits but counting the number of set bits in the number and then subtracting from 32 does not give me what I want because this will also include the leading zeros.

As an example, the number 5 has one zero bit because in binary it is 101.

Answer 1

To count non-leading zeros in Java you can use this algorithm:

public static int countNonleadingZeroBits(int i)
{
    int result = 0;
    while (i != 0)
    {
        if (i & 1 == 0)
        {
            result += 1;
        }
        i >>>= 1;
    } 
    return result;
}

This algorithm will be reasonably fast if your inputs are typically small, but if your input is typically a larger number it may be faster to use a variation on one of the bit hack algorithms on this page.

Answer 2

Count the total number of "bits" in your number, and then subtract the number of ones from the total number of bits.

Answer 3

This what I would have done.

public static int countBitsSet(int num) {
    int count = num & 1; // start with the first bit.
    while((num >>>= 1) != 0) // shift the bits and check there are some left.
        count += num & 1; // count the next bit if its there.
    return count;
}

public static int countBitsNotSet(int num) {
    return 32 - countBitsSet(num);
}

Answer 4

Since evaluation order in Java is defined, we can do this:

public static int countZero(int n) {
    for (int i=1,t=0 ;; i<<=1) {
        if (n==0) return t;
        if (n==(n&=~i)) t++;
    }
}

Note that this relies on the LHS of an equality being evaluated first; try the same thing in C or C++ and the compiler is free to make you look foolish by setting your printer on fire.

Answer 5

Using some built-in functions:

public static int zeroBits(int i)
{
    if (i == 0) {
        return 0;
    }
    else {
        int highestBit = (int) (Math.log10(Integer.highestOneBit(i)) / 
                Math.log10(2)) + 1;
        return highestBit - Integer.bitCount(i);
    }
}

Answer 6

See: http://java.sun.com/javase/6/docs/api/java/lang/Integer.html#bitCount(int) and http://java.sun.com/javase/6/docs/api/java/lang/Integer.html#numberOfLeadingZeros(int)

Answer 7

Take a look at the API documentation of Integer:

32 - Integer.numberOfLeadingZeros(n) - Integer.bitCount(n)