Number of zero bits in integers other than leading zeros

Question

If I have an integer in Java, how do I calculate how many bits are equal to zero except the leading zeros?

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

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

Answer 1

To count minor 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 fast enough if your inputs are usually small, but if your input is usually larger, it might be faster to use one of the bit-hack algorithms on this page .

Answer 2

Take a look at the Integer API documentation:

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

Answer 3

Count the total number of “bits” in your number, and then subtract the number of units from the total number of bits.

Answer 4

This is what I would do.

 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 5

Using some of the 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

Since the 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 assessed equality; try the same thing in C or C ++, and the compiler can make you look stupid if you catch fire.