Simple Recursive Generator Question

Bengt Richter bokr at oz.net
Fri Dec 19 23:02:19 CET 2003


On 19 Dec 2003 11:13:39 -0800, jcb at iteris.com (MetalOne) wrote:

>I am trying to write a generator function that yields the index position
>of each set bit in a mask.
>e.g. 
>for x in bitIndexGenerator(0x16): #10110
>    print x
>--> 1 2 4
>
>
>This is what I have, but it does not work.
>Changing yield to print, shows that the recursion works correctly.
>
>def bitIndexGenerator(mask, index=0):
>    if mask == 0: return
>    elif mask & 0x1: yield index
>    bitIndexGenerator(mask >> 1, index+1)
>
>What am I missing?

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'll use a subclass of long I recently posted (with missing ~ operator in first version, but
fix followup posted) to show bits) The above is a mod of the bit list generator from the latter.

 >>> from lbits import LBits
 >>>
 >>> for i in range(-3,4)+[0x16, -0x16]:
 ...     print '%3s %8r %s' %(i, LBits(i), [bit for bit in bitnos(i)])
 ...
  -3     101b [0, 2]
  -2     110b [1]
  -1      11b [0]
   0       0b []
   1      01b [0]
   2     010b [1]
   3     011b [0, 1]
  22  010110b [1, 2, 4]
 -22  101010b [1, 3, 5]

Regards,
Bengt Richter




More information about the Python-list mailing list