What is the algorithm for finding the number of binary digits required to represent a positive decimal integer?

Answer 1

Algorithm bit_count is:

Input: an integer n, such that n >= 0

Output: the minimum number of binary digits (bits) required to represent n

let count := 0;

repeat {

n := n / 2; // integer division: ignore any remainder

count := count + 1;

} until n = 0;

return count;

This works because each binary digit represents an increasing power of 2, starting from 2^0. Thus if we repeatedly divide a value by 2 until the result is 0, the total number of divisions tells us the minimum number of bits required to represent the value.

Take the value 42 as an example:

42 / 2 = 21

21 / 2 = 10 (r 1)

10 / 2 = 5

5 / 2 = 2 (r 1)

2 / 2 = 1

1 / 2 = 0 (r 1)

That's 6 divisions in total so we need at least 6 binary digits to represent 42 in binary. Given that 42 is 101010 in binary, this is correct.

Let's try 31:

31 / 2 = 15 (r 1)

15 / 2 = 7 (r 1)

7 / 2 = 3 (r 1)

3 / 2 = 1 (r 1)

1 / 2 = 0 (r 1)

5 divisions so 5 bits. 31 in binary is 11111, so that's also correct. 11111 is also the maximum value we can represent with just 5 bits so it follows that 32 would need 6 bits:

32 / 2 = 16

16 / 2 = 8

8 / 2 = 4

4 / 2 = 2

2 / 2 = 1

1 / 2 = 0 (r 1)

QED