Determining combination of bits

[Grant Edwards]

Re: Determining combination of bits

On 2004-11-08, Josiah Carlson <jcarlson@uci.e du> wrote:
[color=blue][color=green]
>> 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.[/color]
>
> From what I remember of high school chemistry (7 years ago), we used to
> talk about 'significant figures' quite often. If the teacher asked for
> some number to 5 significant figures, it had better have them...
>
> sig_fig(8373725 6,5) -> 83737000
> sig_fig(1,5) -> 1.0000
>
> etc.
>
> Now, in the case of 'least significant bit of n', that can be
> interpreted as either n&1, or the rightmost bit that is significant
> (nonzero).
>
> The n&-n produces the rightmost bit that is nonzero, which is certainly
> a valid interpretation of 'least significant bit of n'.[/color]

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

--
Grant Edwards grante Yow! When you get your
at PH.D. will you get able to
visi.com work at BURGER KING?

[news.west.cox.net]

Re: Determining combination of bits


"Scott David Daniels" <Scott.Daniels@ Acm.Org> wrote in message
news:418ff674$1 @nntp0.pdx.net. ..[color=blue]
> Sean Berry wrote:[color=green]
>> Just to set everyone's mind at ease... I haven't had a homework
>> assignment for about four years now.[/color]
> OK, then here's a great little bit of education:
>[/color]

Better than the education I got at UCSB...
[color=blue]
> 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
>[/color]

Perfect. This not only does exactly what I wanted... but I have just
started to learn about generators, and this does great.

Thank you very much for the help everyone.



[color=blue]
> -Scott David Daniels
> Scott.Daniels@A cm.Org[/color]

[Dennis Lee Bieber]

Re: Determining combination of bits

On Mon, 8 Nov 2004 12:33:48 -0800, "Sean Berry"
<sean@buildingo nline.com> declaimed the following in comp.lang.pytho n:
[color=blue]
> 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.
>[/color]
I'd just save the raw number, and build the list of choices by
ANDing against the number.

[color=blue]
> I expect the values will get no bigger than 2^32 = 4294967296. Is this
> getting too big???
>[/color]
Well, it will go to Long int in Python as I recall... 2^31 is
largest signed int...


My first cut though, was:

-=-=-=-=-=-=-=-=-

# powers of two in integer value

val = int(raw_input(" Enter the integer to be evaluated> "))
val = abs(val)
sval = val

pwrs = []
bit = 0

while val:
if val & 1:
pwrs.append(bit )
val = val >> 1
bit = bit + 1

pwrs.reverse()

print sval, "=",

sequence = 0
for p in pwrs:
if sequence:
print "+",
else:
sequence = 1
print 2**p,

print

-=-=-=-=-=-=-=-=-=-
22 = 16 + 4 + 2
25 = 16 + 8 + 1
9 = 8 + 1

Note: 2^1 = 2, so your dictionary is already in error...

Now -- on the concept of rebuilding a list of choices....

CheckBoxes = { "FirstChoic e" : 1,
"SecondChoi ce" : 2,
"ThirdChoic e" : 4,
"FourthChoi ce": 8,
"FifthChoic e" : 16,
"SixthChoic e" : 32 }


for num in [22, 25, 9]:
for k,i in CheckBoxes.item s():
if num & i:
print k,
print


FifthChoice SecondChoice ThirdChoice
FirstChoice FifthChoice FourthChoice
FirstChoice FourthChoice


--[color=blue]
> =============== =============== =============== =============== == <
> wlfraed@ix.netc om.com | Wulfraed Dennis Lee Bieber KD6MOG <
> wulfraed@dm.net | Bestiaria Support Staff <
> =============== =============== =============== =============== == <
> Home Page: <http://www.dm.net/~wulfraed/> <
> Overflow Page: <http://wlfraed.home.ne tcom.com/> <[/color]

[Dennis Lee Bieber]

Re: Determining combination of bits

On Mon, 08 Nov 2004 15:33:01 -0800, Scott David Daniels
<Scott.Daniels@ Acm.Org> declaimed the following in comp.lang.pytho n:

[color=blue]
> (OCA) and increment (INA)". Note that a ones complement turns all of
> the least significant zeros to ones, and the least significant one to
> a zero. When you increment that the carry propagates back to the 0 for[/color]

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

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

--[color=blue]
> =============== =============== =============== =============== == <
> wlfraed@ix.netc om.com | Wulfraed Dennis Lee Bieber KD6MOG <
> wulfraed@dm.net | Bestiaria Support Staff <
> =============== =============== =============== =============== == <
> Home Page: <http://www.dm.net/~wulfraed/> <
> Overflow Page: <http://wlfraed.home.ne tcom.com/> <[/color]

[news.west.cox.net]

Re: Determining combination of bits

> Note: 2^1 = 2, so your dictionary is already in error...[color=blue]
>[/color]

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

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

[Nick Craig-Wood]

Re: Determining combination of bits

Larry Bates <lbates@syscono nline.com> wrote:[color=blue]
> Sounds a lot like a homework assignment[/color]

Indeed!
[color=blue]
> but I'll give you some "hints".
>
> 1) Use bit shifting operator (>>) and boolean &
> operator to isolate each bit in the integer.[/color]

Shifting isn't necessary - D.keys() contains a list of all possible
(for this problem) binary numbers.
[color=blue]
> 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.[/color]

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.
[color=blue][color=green][color=darkred]
>>> D={1:'one',2:'t wo',4:'three',8 :'four',16:'fiv e'}
>>> def f(n): return [D[i] for i in D.keys() if XXXXX][/color][/color][/color]
....[color=blue][color=green][color=darkred]
>>> f(9)[/color][/color][/color]
['four', 'one'][color=blue][color=green][color=darkred]
>>> f(22)[/color][/color][/color]
['two', 'three', 'five'][color=blue][color=green][color=darkred]
>>> f(25)[/color][/color][/color]
['four', 'one', 'five']

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

--
Nick Craig-Wood <nick@craig-wood.com> -- http://www.craig-wood.com/nick

[Bengt Richter]

Re: Determining combination of bits

On Mon, 8 Nov 2004 11:48:22 -0800, "Sean Berry" <sean@buildingo nline.com> wrote:
[color=blue]
>Say I have a dictionary like the following
>
>{1:'one',2:'tw o',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?
>[/color]
Since it's not homework, and I seem to have read your question a little
differently from the others, maybe this will be useful...
[color=blue][color=green][color=darkred]
>>> bitdict = {1:'one',2:'two ',4:'three',8:' four',16:'five' }
>>> def bitnames(n):[/color][/color][/color]
... return [t[1] for t in sorted([kv for kv in bitdict.items() if n&kv[0]])][::-1]
...[color=blue][color=green][color=darkred]
>>> bitnames(11)[/color][/color][/color]
['four', 'two', 'one'][color=blue][color=green][color=darkred]
>>> bitnames(15)[/color][/color][/color]
['four', 'three', 'two', 'one'][color=blue][color=green][color=darkred]
>>> bitnames(31)[/color][/color][/color]
['five', 'four', 'three', 'two', 'one'][color=blue][color=green][color=darkred]
>>> bitnames(9)[/color][/color][/color]
['four', 'one'][color=blue][color=green][color=darkred]
>>> bitnames(20)[/color][/color][/color]
['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.
[color=blue][color=green][color=darkred]
>>> namelist = 'one two three four five'.split()
>>> bitdict = dict((2**i,name ) for i,name in enumerate(namel ist))
>>> bitdict[/color][/color][/color]
{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.,
[color=blue][color=green][color=darkred]
>>> def bitnames2(n):[/color][/color][/color]
... return [name for i, name in enumerate(namel ist) if n&2**i][::-1]
...[color=blue][color=green][color=darkred]
>>> bitnames2(11)[/color][/color][/color]
['four', 'two', 'one'][color=blue][color=green][color=darkred]
>>> bitnames2(9)[/color][/color][/color]
['four', 'one'][color=blue][color=green][color=darkred]
>>> bitnames2(31)[/color][/color][/color]
['five', 'four', 'three', 'two', 'one']

HTH

Regards,
Bengt Richter

[Dennis Lee Bieber]

Re: Determining combination of bits

On Mon, 8 Nov 2004 21:18:36 -0800, "news.west.cox. net"
<sean.berry2@co x.net> declaimed the following in comp.lang.pytho n:
[color=blue][color=green]
> > Note: 2^1 = 2, so your dictionary is already in error...
> >[/color]
>
> The dictionary was filled with arbitrary values, not
> { x : 2^x } values like you might have thought.[/color]

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...
[color=blue]
>
> It is actually more like {1:123, 2:664, 4:323, 8:990, 16:221... etc}
>
>[/color]

CheckBoxes = [ "FirstChoic e",
"SecondChoi ce",
"ThirdChoic e",
"FourthChoi ce",
"FifthChoic e",
"SixthChoic e" ]


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

--[color=blue]
> =============== =============== =============== =============== == <
> wlfraed@ix.netc om.com | Wulfraed Dennis Lee Bieber KD6MOG <
> wulfraed@dm.net | Bestiaria Support Staff <
> =============== =============== =============== =============== == <
> Home Page: <http://www.dm.net/~wulfraed/> <
> Overflow Page: <http://wlfraed.home.ne tcom.com/> <[/color]

[Peter Abel]

Re: Determining combination of bits

"Sean Berry" <sean@buildingo nline.com> wrote in message news:<x3Qjd.121 786$hj.41260@fe d1read07>...[color=blue]
> Say I have a dictionary like the following
>
> {1:'one',2:'two ',4:'three',8:' four',16:'five' , etc...}[/color]

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:'on e',4:'two',8:'t hree',16:'four' ,32:'five', etc...}

[color=blue]
>
> 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?[/color]

Solution No. XXXXXXXX:
[color=blue][color=green]
>> def fn(n):[/color][/color]
.... 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,'+'.joi n(l))
.... return keys
....[color=blue][color=green][color=darkred]
>>> print fn(22)[/color][/color][/color]
22 = 16+4+2
[16, 4, 2][color=blue][color=green][color=darkred]
>>> print fn(25)[/color][/color][/color]
25 = 16+8+1
[16, 8, 1][color=blue][color=green][color=darkred]
>>> print fn(255)[/color][/color][/color]
255 = 128+64+32+16+8+ 4+2+1
[128, 64, 32, 16, 8, 4, 2, 1][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

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]

Re: Determining combination of bits

Grant Edwards wrote:[color=blue]
> 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).
>[/color]
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
Scott.Daniels@A cm.Org

[Scott David Daniels]

Re: Determining combination of bits

Dennis Lee Bieber wrote:[color=blue]
> On Mon, 08 Nov 2004 15:33:01 -0800, Scott David Daniels
> <Scott.Daniels@ Acm.Org> declaimed the following in comp.lang.pytho n:[color=green]
>>(OCA) and increment (INA)". Note that a ones complement turns all of
>>the least significant zeros to ones, and the least significant one to
>>a zero. When you increment that the carry propagates back to the 0 for[/color]
> Ones complement turns ALL 0 bits to 1, and ALL 1 bits to 0.[/color]
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).
[color=blue]
> 00000000
> 1C 11111111 ones complement has a "negative zero"
> +1 00000000 twos complement "overflows" back to single zero[/color]

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

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