222

7
+2  Q:

## Number of zero bits in integer except leading zeros

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`.

+1  A:

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.

yes but given number 5 //101 here is 1 zero and not 30
@davit-datuashvili: So you want to count zeros apart form leading zeros?
`5 = 000...000101`. The thing you want is number of last (most significant) bit which is set plus one and minus amount of bits which is set.
This doesn't handle negative numbers. Perhaps >>> 1 instead of /= 2 is a btewen choice.
@Peter Lawrey: Fixed, thanks.
A:

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

+1  A:

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);
}
``````
The '32-x' isn't what the OP wants. The bits that are being counted aren't all 32, it's only up to the last set bit. (He just didn't explain it well in the original question)
A:

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.

A:

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);
}
}
``````
+1  A:
+1  A:

Take a look at the API documentation of Integer:

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