Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find out number of bits needed to represent a positive integer in binary?

This is probably pretty basic, but to save me an hour or so of grief can anyone tell me how you can work out the number of bits required to represent a given positive integer in Java?

e.g. I get a decimal 11, (1011). I need to get the answer, 4.

I figured if I could work out how to set all the bits other than the most significant bit to 0, and then >>> it, I'd get my answer. But... I can't.

like image 688
joinJpegs Avatar asked Mar 25 '09 02:03

joinJpegs


People also ask

How do you calculate the number of bits needed to represent a positive integer?

Number of Bits in a Specific Decimal IntegerA positive integer n has b bits when 2b-1 ≤ n ≤ 2b – 1. For example: 29 has 5 bits because 16 ≤ 29 ≤ 31, or 24 ≤ 29 ≤ 25 – 1. 123 has 7 bits because 64 ≤ 123 ≤ 127, or 26 ≤ 123 ≤ 27 – 1.

How many bits are required to represent a binary number?

Answer: In general, N bits (binary digits) are required to represent unique integer values. Eight bits are required to represent 256 unique values. Those values range in binary from 00000000 through 11111111, or 0 through 255 in decimal.

How many bits does it take to represent an integer?

Whole numbers (integers) are usually represented with 4 bytes, or 32 bits. In the past, symbols (e.g., letters, digits) were represented with one byte (8 bits), with each symbol being mapped to a number between 0-255.


1 Answers

Well, the answer is pretty simple. If you have an int value:

int log2(int value) {     return Integer.SIZE-Integer.numberOfLeadingZeros(value); } 

The same exists for Long...

[Edit] If shaving milliseconds is an issue here, Integer.numberOfLeadingZeros(int) is reasonably efficient, but still does 15 operations... Expanding a reasonable amount of memory (300 bytes, static) you could shave that to between 1 and 8 operations, depending on the range of your integers.

like image 134
Varkhan Avatar answered Sep 22 '22 02:09

Varkhan