Determining combination of bits

[Bengt Richter]

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