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? 10 1889
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
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
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
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?
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
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):
... """Littleendian 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
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):
... """Littleendian 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
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): ... """Littleendian 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 &~(a1)
010b a ^= a &~(a1) a
010100b a &~(a1)
0100b a ^= a &~(a1) a
010000b a &~(a1)
010000b a ^= a &~(a1) a
0b
Regards,
Bengt Richter
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
JohannesNiemeyerWeg 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/ This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Paul Chiusano 
last post by:
I've been playing around with generators and have run into a
difficulty. Suppose I've defined a Node class like so:
class Node:
def __init__(self, data=None, left=None, right=None):...

by: Carlos Ribeiro 
last post by:
Hello all,
Here I am using some deeply nested, treelike data structures. In some
situations I need to traverse the tree; the oldstyle way to do it is
to write a recursive method on the node...

by: Steve Goldman 
last post by:
Hi,
I am trying to come up with a way to develop all nlength permutations of a
given list of values. The short function below seems to work, but I can't
help thinking there's a better way. ...

by: aurora 
last post by:
I love generator and I use it a lot. Lately I've been writing some
recursive generator to traverse tree structures. After taking closer look
I have some concern on its performance.
Let's take...

by: James Stroud 
last post by:
This was my answer to the thread "new in programing":
def do_something(*args):
print args
def do_deeply(first, depth, lim, doit=True, *args):
if depth < lim:
do_deeply(first+1, depth+1, lim,...

by: Bob Cummings 
last post by:
Not sure if this is the correct place or not. Anyhow in school we were
taught that when trying to calculate the efficiency of an algorithm to
focus on something called FLOPs or Floating Point...

by: Fabian Steiner 
last post by:
Hello!
I have got a Python "Device" Object which has got a attribute (list)
called children which my contain several other "Device" objects. I
implemented it this way in order to achieve a kind...

by: lllomh 
last post by:
Define the method first
this.state = {
buttonBackgroundColor: 'green',
isBlinking: false, // A new status is added to identify whether the button is blinking or not
}
autoStart=()=>{

by: isladogs 
last post by:
The next Access Europe meeting will be on Wednesday 4 Oct 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM)
The start time is equivalent to 19:00 (7PM) in Central...

by: giovanniandrean 
last post by:
The energy model is structured as follows and uses excel sheets to give input data:
1Utility.py contains all the functions needed to calculate the variables and other minor things (mentions...

by: NeoPa 
last post by:
Hello everyone.
I find myself stuck trying to find the VBA way to get Access to create a PDF of the currentlyselected (and open) object (Form or Report).
I know it can be done by selecting :...

by: NeoPa 
last post by:
Introduction
For this article I'll be using a very simple database which has Form (clsForm) & Report (clsReport) classes that simply handle making the calling Form invisible until the Form, or all...

by: nia12 
last post by:
Hi there,
I am very new to Access so apologies if any of this is obvious/not clear.
I am creating a data collection tool for health care employees to complete. It consists of a number of...

by: NeoPa 
last post by:
Introduction
For this article I'll be focusing on the Report (clsReport) class. This simply handles making the calling Form invisible until all of the Reports opened by it have been closed, when it...

by: isladogs 
last post by:
The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, Mike...

by: GKJR 
last post by:
Does anyone have a recommendation to build a standalone application to replace an Access database? I have my bookkeeping software I developed in Access that I would like to make available to other...
 