471,336 Members | 1,239 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,336 software developers and data experts.

Simple Recursive Generator Question

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?
Jul 18 '05 #1
10 1800
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?


The bitIndexGenerator(mask>>1, index+1) just returns a new generator which
is immediately discarded. For a generator to do anything, you must invoke
its next() method, and one way to do it is a for loop, e. g (not mask<0
proof):
def big(mask, index=0): .... if mask != 0:
.... if mask & 1:
.... yield index
.... for result in big(mask>>1, index+1):
.... yield result
.... for x in big(0x16):

.... print x,
....
1 2 4

Peter
Jul 18 '05 #2
MetalOne wrote in message
<92**************************@posting.google.com>. ..
What am I missing?


The difference between a generator and a generator function.
def gen_func(): yield None .... gen_func() # what does this return?


Also, this isn't a recursive problem. Use a loop.
--
Francis Avila

Jul 18 '05 #3
In article <92**************************@posting.google.com >,
jc*@iteris.com (MetalOne) wrote:
def bitIndexGenerator(mask, index=0):
if mask == 0: return
elif mask & 0x1: yield index
bitIndexGenerator(mask >> 1, index+1)


The actual answer to your question is that when you recursively call a
generator, its return value (the iterator of its results) needs to be
used not ignored.

But the reason I'm posting is to suggest an alternative approach:
bitIndices = dict([(1L<<i,i) for i in range(32)])

def bitIndexGenerator(mask):
while mask:
bit = mask &~ (mask - 1)
yield bitIndices[bit]
mask &=~ bit

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Jul 18 '05 #4
MetalOne wrote:
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?


Everything needs to be yielded from the outermost generator, like

def bitIndexGenerator(mask, index=0):
if mask == 0: return
elif mask & 0x1: yield index
for i in bitIndexGenerator(mask >> 1, index+1):
yield i

However, this is ugly ;-), and kind of defeats the purpose of
generators. Why do you want to use recursion like this?

Jul 18 '05 #5

jcb> This is what I have, but it does not work.

jcb> def bitIndexGenerator(mask, index=0):
jcb> if mask == 0: return
jcb> elif mask & 0x1: yield index
jcb> bitIndexGenerator(mask >> 1, index+1)

Try:

def bitIndexGenerator(mask, index=0):
if mask == 0:
return
elif mask & 0x1:
yield index
for index in bitIndexGenerator(mask >> 1, index+1):
yield index

Skip

Jul 18 '05 #6
On 19 Dec 2003 11:13:39 -0800, jc*@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
Jul 18 '05 #7
In article <br**********@216.39.172.122>, bo**@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.

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Jul 18 '05 #8
Thanks.
Jul 18 '05 #9
On Fri, 19 Dec 2003 14:49:10 -0800, David Eppstein <ep******@ics.uci.edu> wrote:
In article <br**********@216.39.172.122>, bo**@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
Jul 18 '05 #10
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?


Your recursive generator is yielding to itself,
but not taking its result. Recursion does not
make sense with generators, since they can yield
only one level up.

The above would work pretty fine with a Stackless
tasklet.

Here is a recursion solution, but be warned, this
is really really inefficient, since it has quadratic
behavior due to the repeated recursion activation:

def bitIndexGenerator(mask, index=0):
if mask == 0: return
elif mask & 0x1: yield index
for each in bitIndexGenerator(mask >> 1, index+1):
yield each

An interative version is easy and adequate here.

def bitIndexGenerator(mask):
index = 0
while mask:
if mask & 0x1: yield index
mask >>= 1
index += 1

--
Christian Tismer :^) <mailto:ti****@tismer.com>
Mission Impossible 5oftware : Have a break! Take a ride on Python's
Johannes-Niemeyer-Weg 9a : *Starship* http://starship.python.net/
14109 Berlin : PGP key -> http://wwwkeys.pgp.net/
work +49 30 89 09 53 34 home +49 30 802 86 56 mobile +49 173 24 18 776
PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04
whom do you want to sponsor today? http://www.stackless.com/
Jul 18 '05 #11

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

8 posts views Thread by Paul Chiusano | last post: by
19 posts views Thread by Carlos Ribeiro | last post: by
10 posts views Thread by Steve Goldman | last post: by
7 posts views Thread by aurora | last post: by
2 posts views Thread by James Stroud | last post: by
18 posts views Thread by Bob Cummings | last post: by
14 posts views Thread by Fabian Steiner | last post: by
reply views Thread by rosydwin | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.