Determining combination of bits

[Nick Craig-Wood]

Sounds a lot like a homework assignment
Indeed!

but I'll give you some "hints".

1) Use bit shifting operator (>>) and boolean &
operator to isolate each bit in the integer.

Shifting isn't necessary - D.keys() contains a list of all possible
(for this problem) binary numbers.

2) It will be either zero or one. Build up a
list of these which will represent the power
of two that each one bit represents.

Whenever you think "build up a list" you should be thinking list
comprehension. A conditional add to a list should make you think of
the if clause of a list comprehension.

D={1:'one',2:'two',4:'three',8:'four',16:'five'}
def f(n): return [D for i in D.keys() if XXXXX] ....
f(9) ['four', 'one']
f(22) ['two', 'three', 'five']
f(25)

['four', 'one', 'five']

I've left XXXXX as an excercise - see 1) above for a hint ;-)

 

[Bengt Richter]

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...
... 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.
{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.,
... 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

 

[Dennis Lee Bieber]

The dictionary was filled with arbitrary values, not
{ x : 2^x } values like you might have thought.

Well, you had stated "powers of two"... If all you wanted is a
bit mapping you could probably drop the dictionary and just use a list
of the values, indexed by the bit position, and my first attempt
logic...

It is actually more like {1:123, 2:664, 4:323, 8:990, 16:221... etc}

CheckBoxes = [ "FirstChoice",
"SecondChoice",
"ThirdChoice",
"FourthChoice",
"FifthChoice",
"SixthChoice" ]


for num in [22, 25, 9]:
bit = 0
while num:
if num & 1:
print CheckBoxes[bit],
bit = bit + 1
num = num >> 1
print

SecondChoice ThirdChoice FifthChoice
FirstChoice FourthChoice FifthChoice
FirstChoice FourthChoice

where "num" is the sum of the checkbox index values (or whatever
selection mechanism is used), assuming /they/ were set up in 2^(n+1)
scheme (n = bit position, starting with 0)...

--

 

[Peter Abel]

Say I have a dictionary like the following

{1:'one',2:'two',4:'three',8:'four',16:'five', etc...}

Dont know exactly what your dictionary should represent.
Since 2**0 = 1
2**1 = 2
2**2 = 4
etc.
So I would have expected something like:
{1:'zero',2:'one',4:'two',8:'three',16:'four',32:'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?

Solution No. XXXXXXXX:
.... number=n
.... if n<=0:
.... return 'n must be greater 0'
.... keys=[]
.... i=1
.... while n:
.... if n&1:
.... keys.append(i)
.... n=n>>1
.... i*=2
.... keys.reverse()
.... l=map(str,keys)
.... print '%d = %s' % (number,'+'.join(l))
.... return keys
.... 22 = 16+4+2
[16, 4, 2]25 = 16+8+1
[16, 8, 1]255 = 128+64+32+16+8+4+2+1
[128, 64, 32, 16, 8, 4, 2, 1]
Sorry I have only Python 2.2. and though I'm a one-liner-fan my
solution should be clear.

Regards Peter

 

[Scott David Daniels]

> Perhaps it's "valid", but in 25+ years of doing hardware and
low-level software this is the first time I've ever heard the
phrase "least significant bit" refer to anything other than the
"rightmost" bit (the one with a weighting of 1).

I tried to say, 'least significant one bit' (or 'on bit), but may
missed it in at least a sentence or two.

--Scott David Daniels
(e-mail address removed)

 

[Scott David Daniels]

Ones complement turns ALL 0 bits to 1, and ALL 1 bits to 0.

Right. In particular, all of the lowest order zeroes turn to 1s,
the one directly before them turns to zero. Those bits are the only
bits where I care what the value is, all others are simply inverted
(and it doesn't matter what values they have).

00000000
1C 11111111 ones complement has a "negative zero"
+1 00000000 twos complement "overflows" back to single zero

Correct, and this isoloates the least significant one bit for this value
as well (inasmuch as it doesn't exist).

--Scott David Daniels
(e-mail address removed)