# Determining combination of bits

Bengt Richter bokr at oz.net
Tue Nov 9 10:33:31 CET 2004

```On Mon, 8 Nov 2004 11:48:22 -0800, "Sean Berry" <sean at buildingonline.com> wrote:

>Say I have a dictionary like the following
>
>{1:'one',2:'two',4:'three',8:'four',16:'five', etc...}
>
>and I am given some numbers, say 22, 25, and 9.  I want to determine the
>keys, powers of 2, that comprise the number.
>
>Ex.  22 = 16+4+2
>       25 = 16+8+1
>       9   = 8+1
>...etc...
>
>How do I get these keys?
>
Since it's not homework, and I seem to have read your question a little
differently from the others, maybe this will be useful...

>>> bitdict = {1:'one',2:'two',4:'three',8:'four',16:'five'}
>>> def bitnames(n):
...     return [t[1] for t in sorted([kv for kv in bitdict.items() if n&kv[0]])][::-1]
...
>>> bitnames(11)
['four', 'two', 'one']
>>> bitnames(15)
['four', 'three', 'two', 'one']
>>> bitnames(31)
['five', 'four', 'three', 'two', 'one']
>>> bitnames(9)
['four', 'one']
>>> bitnames(20)
['five', 'three']

If you don't care about the order, you can leave out the sorting and reversal.

I gather you want to put in something other than  strings 'one','two', etc. as bit definitions,
otherwise you could define your dict from names in a single list, which makes the numbers less
typo-prone (since you're not typing them ;-) e.g.

>>> namelist = 'one two three four five'.split()
>>> bitdict = dict((2**i,name) for i,name in enumerate(namelist))
>>> bitdict
{8: 'four', 1: 'one', 2: 'two', 4: 'three', 16: 'five'}

This uses python 2.4b1 BTW, so you will have to change sorted and put [] around the
dict generator expression argument above.

You could also use the list instead of a dict, since you know you have an ordered
compact set of values corresponding to the bits, and since the order is still there
you don't need to sort. E.g.,

>>> def bitnames2(n):
...     return [name for i, name in enumerate(namelist) if n&2**i][::-1]
...
>>> bitnames2(11)
['four', 'two', 'one']
>>> bitnames2(9)
['four', 'one']
>>> bitnames2(31)
['five', 'four', 'three', 'two', 'one']

HTH

Regards,
Bengt Richter

```