Simple Recursive Generator Question

[Bengt Richter]

On Fri, 19 Dec 2003 14:49:10 -0800, David Eppstein <eppstein at ics.uci.edu> wrote:

>In article <brvshb$cdp$0 at 216.39.172.122>, bokr at oz.net (Bengt Richter) 
>wrote:
>
>> Here is one that works also for negative numbers (includes the least 
>> significant
>> of the arbitrarily extended sign bits):
>> 
>>  >>> def bitnos(self):
>>  ...     """Little-endian bit number generator"""
>>  ...     bits = long(self)
>>  ...     sign = bits<0
>>  ...     bitno = 0
>>  ...     while bits>0 or sign and bits!=-1L:
>>  ...         if bits&1: yield bitno
>>  ...         bitno += 1
>>  ...         bits >>= 1
>>  ...     if sign: yield bitno
>>  ...
>
>I'm not sure I would call that working -- what I'd expect for a negative 
>number is to generate an infinite sequence.
>
Hm, yeah, if you don't know the sign, there's obviously an ambiguity.
Maybe I should flag by making the last line

    if sign: yield -bitno.

With that change we can get the number back:

 >>> for i in range(-3,4)+[0x16,-0x16]:
 ...     print '%3s => %s' % (i, sum([p>=0 and 2**p or -2**-p for p in bitnos(i)]))
 ...
  -3 => -3
  -2 => -2
  -1 => 1
   0 => 0
   1 => 1
   2 => 2
   3 => 3
  22 => 22
 -22 => -22


The repr of my lbits.LBits class doesn't have that problem, since the msb
is always the lsb sign bit (except that I used '11b' for -1 for symmetry)

BTW, what would you think of having signed binary literals in python, so you
could write natively
 
 a = 010110b # not legal now
 b = 101010b # ditto

like the strings my LBits constructor accepts

 >>> a = LBits('010110b')
 >>> a
 010110b
 >>> b = LBits('101010b')
 >>> b
 101010b

 >>> a+b
 0b
 >>> a+b, a==-b
 (0b, True)
 >>> map(int, [a,b])
 [22, -22]

Sometimes it's nice to see bits, e.g., the bit isolation of your algo, shown step by step:

 >>> a
 010110b
 >>> a &~(a-1)
 010b
 >>> a ^= a &~(a-1)
 >>> a
 010100b
 >>> a &~(a-1)
 0100b
 >>> a ^= a &~(a-1)
 >>> a
 010000b
 >>> a &~(a-1)
 010000b
 >>> a ^= a &~(a-1)
 >>> a
 0b

Regards,
Bengt Richter