Determining combination of bits

[Sean Berry]

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?

[Steven Bethard]

Sean Berry <sean <at> buildingonline. com> writes:

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

This sounds suspiciously like a homework, so I'm just going to give a hint here:

import math
math.log(22, 2) 4.4594316186372 973 2**int(math.log (22, 2)) 16 2**int(math.log (22 - 16, 2)) 4 2**int(math.log (22 - 16 - 4 - 2, 2)) 2

Hope this is helpful.

Steve

[Larry Bates]

You didn't say anything about how large the
numbers might get. If they stay small (e.g. <thousands)
you could just look them up directly from a dictionary.
If they can get arbitrarily large you must use bit
shifing and boolean & (and).

Sounds a lot like a homework assignment, but I'll
give you some "hints".

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

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.

Larry Bates

Sean Berry 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?

[Terry Reedy]

"Sean Berry" <se**@buildingo nline.com> wrote in message
news:x3Qjd.1217 86$hj.41260@fed 1read07...

and I am given some numbers, say 22, 25, and 9. I want to determine the
keys, powers of 2, that comprise the number.
How do I get these keys?

if n%2: print 'has a positive one bit'

n//2 == n>>1 deletes that bit

keep track of divisions/shifts and stop when n == 0

Terry J. Reedy

[Sean Berry]

Just to set everyone's mind at ease... I haven't had a homework assignment
for about four years now.

I am using two database tables. One will have some options and a code
(power of 2).

Then, someone will check off checkboxes and submit. The number will be
added and saved in a cookie. Then, later, I want to be able to redisplay
their choices by reading the value from the cookie.

I expect the values will get no bigger than 2^32 = 4294967296. Is this
getting too big???

"Terry Reedy" <tj*****@udel.e du> wrote in message
news:ma******** *************** *************** @python.org...

"Sean Berry" <se**@buildingo nline.com> wrote in message
news:x3Qjd.1217 86$hj.41260@fed 1read07...

and I am given some numbers, say 22, 25, and 9. I want to determine the
keys, powers of 2, that comprise the number.
How do I get these keys?

if n%2: print 'has a positive one bit'

n//2 == n>>1 deletes that bit

keep track of divisions/shifts and stop when n == 0

Terry J. Reedy

[Steven Bethard]

Sean Berry <sean <at> buildingonline. com> writes:

I am using two database tables. One will have some options and a code
(power of 2).

Then, someone will check off checkboxes and submit. The number will be
added and saved in a cookie. Then, later, I want to be able to redisplay
their choices by reading the value from the cookie.

You might look at the number_in_base thread:

http://groups.google.com/groups?thre...%40news.oz.net

This gives a solution something like:

def number_in_base( n, b=10, digits='0123456 789ABCDEF'): .... return '-'[:n<0]+''.join(revers ed(list(
.... digits[r]
.... for q in [abs(n)]
.... for q, r in iter(lambda: divmod(q, b), (0, 0))))) or digits[0]
.... digits = number_in_base( 22, 2)
[power_of_2

.... for power_of_2, digit
.... in zip(reversed([2**x for x in range(len(digit s))]), digits)
.... if digit == '1']
[16, 4, 2]
Steve

[Scott David Daniels]

Sean Berry wrote:

Just to set everyone's mind at ease... I haven't had a homework assignment
for about four years now.

OK, then here's a great little bit of education:

n & -n == least significant bit of n

So, for example:

def bits(n):
assert n >= 0 # This is an infinite loop if n < 0
while n:
lsb = n & -b
yield lsb
n ^= lsb

-Scott David Daniels
Sc***********@A cm.Org

[Mitja]

Scott David Daniels wrote:

Sean Berry wrote:

Just to set everyone's mind at ease... I haven't had a
homework assignment for about four years now.

OK, then here's a great little bit of education:

n & -n == least significant bit of n

A lapse of mind?

n = 6
n & (-n)

2

You probably meant n&1 or perhaps n%2.

[Diez B. Roggisch]

> A lapse of mind?

n = 6
n & (-n)

2

You probably meant n&1 or perhaps n%2.

No, the exact right thing: 6 is binary

110

with the least significant bit beeing

10

thus the decimal value of 2.

Albeit I have to admit that I didn't know the trick.
--
Regards,

Diez B. Roggisch

[Grant Edwards]

On 2004-11-08, Diez B. Roggisch <de*********@we b.de> wrote:

A lapse of mind?

> n = 6
> n & (-n)

2

You probably meant n&1 or perhaps n%2.

No, the exact right thing: 6 is binary

110

with the least significant bit beeing

10

The least significant bit of 110 is this one here -----+
^ |
| |
+-----------------------+

It's a 0 (zero).

What I think you're trying to say is something like the value
of the rightmost 1.

--
Grant Edwards grante Yow! The PINK SOCKS were
at ORIGINALLY from 1952!! But
visi.com they went to MARS around
1953!!