Count bits used in int
Solution 1
Easiest?
32 - Integer.numberOfLeadingZeros(value)
If you are looking for algorithms, the implementors of the Java API agree with your divide-and-conquer bitshifting approach:
public static int numberOfLeadingZeros(int i) {
if (i == 0)
return 32;
int n = 1;
if (i >>> 16 == 0) { n += 16; i <<= 16; }
if (i >>> 24 == 0) { n += 8; i <<= 8; }
if (i >>> 28 == 0) { n += 4; i <<= 4; }
if (i >>> 30 == 0) { n += 2; i <<= 2; }
n -= i >>> 31;
return n;
}
Edit: As a reminder to those who trust in the accuracy of floating point calculations, run the following test harness:
public static void main(String[] args) {
for (int i = 0; i < 64; i++) {
long x = 1L << i;
check(x);
check(x-1);
}
}
static void check(long x) {
int correct = 64 - Long.numberOfLeadingZeros(x);
int floated = (int) (1 + Math.floor(Math.log(x) / Math.log(2)));
if (floated != correct) {
System.out.println(Long.toString(x, 16) + " " + correct + " " + floated);
}
}
The first detected deviation is:
ffffffffffff 48 49
Solution 2
Unfortunately there is no Integer.bitLength()
method that would give you the answer directly.
An analogous method exists for BigInteger
, so you could use that one:
BigInteger.valueOf(value).bitLength()
Constructing the BigInteger
object will make it somewhat less efficient, but that will only matter if you do it many millions of times.
Solution 3
You want to compute the base 2 logarithm of the number - specifically:
1 + floor(log2(value))
Java has a Math.log method which uses base e, so you can do:
1 + Math.floor(Math.log(value) / Math.log(2))
Solution 4
Be careful what you ask for. One very fast technique is to do a table lookup:
int bittable [] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ... };
int numbits (int v)
{
return bittable [v];
}
where bittable
contains an entry for every int. Of course that has complications for negative values. A more practical way would be to count the bits in bitfields of the number
int bittable [16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
int numbits (int v)
{
int s = 0;
while (v != 0)
{
s += bittable [v & 15];
v >>= 4;
}
return s;
}
Solution 5
You really just want to find the position of the highest bit that is a 1. See this page, under the heading "Finding integer log base 2 of an integer (aka the position of the highest bit set)".
sigvardsen
Updated on June 04, 2022Comments
-
sigvardsen almost 2 years
If you have the binary number 10110 how can I get it to return 5? e.g a number that tells how many bits are used? There are some likewise examples listed below:
- 101 should return 3
- 000000011 should return 2
- 11100 should return 5
- 101010101 should return 9
How can this be obtained the easiest way in Java? I have come up with the following method but can i be done faster:
public static int getBitLength(int value) { if (value == 0) { return 0; } int l = 1; if (value >>> 16 > 0) { value >>= 16; l += 16; } if (value >>> 8 > 0) { value >>= 8; l += 8; } if (value >>> 4 > 0) { value >>= 4; l += 4; } if (value >>> 2 > 0) { value >>= 2; l += 2; } if (value >>> 1 > 0) { value >>= 1; l += 1; } return l; }