Python find max number of combinations in binary

Question

Hi I'm trying to figure out a function where given a length n of a list [x1, x2... xn], how many digits would be needed for a base 2 number system to assign a unique code to each value in the list.

For example, one digit can hold two unique values:

x1 0
x2 1

two digits can hold four:

x1 00
x2 01
x3 10
x4 11

etc. I'm trying to write a python function calcBitDigits(myListLength) that takes this list length and returns the number of digits needed. calcBitDigits(2) = 1, calcBitDigits(4) = 2, calcBitDigits(3) = 2, etc.

Answer 1

>>> for i in range(10):
...    print i, i.bit_length()
0 0
1 1
2 2
3 2
4 3
5 3
6 3
7 3
8 4
9 4

I'm not clear on exactly what it is you want, but it appears you want to subtract 1 from what bit_length() returns - or maybe not ;-)

On third thought ;-), maybe you really want this:

def calcBitDigits(n):
    return (n-1).bit_length()

At least that gives the result you said you wanted in each of the examples you gave.

Note: for an integer n > 0, n.bit_length() is the number of bits needed to represent n in binary. (n-1).bit_length() is really a faster way of computing int(math.ceil(math.log(n, 2))).

Clarification: I understand the original question now ;-) Here's how to think about the answer: if you have n items, then you can assign them unique codes using the n integers in 0 through n-1 inclusive. How many bits does that take? The number of bits needed to express n-1 (the largest of the codes) in binary. I hope that makes the answer obvious instead of mysterious ;-)

As comments pointed out, the argument gets strained for n=1. It's a quirk then that (0).bit_length() == 0. So watch out for that one!

Answer 2

Use the following -

import math
int(math.ceil(math.log(x,2)))

where x is the list length.

Edit:

For x = 1, we need to have a separate case that would return 1. Thanks @thefourtheye for pointing this out.