CODEWITHSUNDEEP
binaryinteger
user1647008
user1647008

Reputation: 343

How many bits do you need to store a positive integer?

How many bits would you need to store a positive integer for example in the billions? Would you have to use the log2 N to find this out?

Upvotes: 19

Views: 39154

Answers (3)

bradwilder31415
bradwilder31415

Reputation: 434

Since I've seen the answer reported incorrectly so many times, I thought I would post the correct answer.

The number of bits needed to represent the positive integer n is

bits = floor( log2(n) + 1 )

where log2 means log base 2.

Upvotes: 40

mjgpy3
mjgpy3

Reputation: 8947

Just to add to the previous answer, you can figure out how many bits are needed to represent a number N mathematically using any log-base. For instance, say I want to know how many bits are necessary to represent the number 12345 but my calculator only knows ln (natural log).

So,

2^b = 12345

Taking the ln of both sides.

ln(2^b) = ln(12345)

Of course the log of a number to an exponent is that exponent times the log of only the base, So,

b*ln(2) = ln(12345)

Divide both sided by ln(2),

b = ln(12345) / ln(2)

And of course, as is stated in the other answer you will need to round this result up because to represent some number you need 2^b to be equal or greater than that number.

So,

b = ceil(ln(12345) / ln(2))

Where ceil(f) rounds f up to the nearest integer.

Using the above process, you can find the number of bits needed for any number N, using any log-base logb, i.e.,

b = ceil(logb(N) / logb(2))

Upvotes: 7

LeeNeverGup
LeeNeverGup

Reputation: 1114

Yes. the maximal number stored in k bits is 2^k-1, since there is 2^k options for the bits, and one of them is zero.
Therefore, the number of bits required to store a number N is log2(N), but since there is no half bit, you need to round it up to the cloest integer above.

Note: if you need to include negative numbers, there must be one more bit for the sign.

Upvotes: 10

Related Questions