Home Original page

iterating bit-by-bit across int?

Paul Rubin http
Thu Oct 23 15:06:23 EDT 2003 
Matthew Wilson <mwilson at sarcastic-horse.com> writes:
> I'm playing around with genetic algorithms and I want to write a
> function that mutates an integer by iterating across the bits, and about
> 1 in 10 times, it should switch a zero to a one, or a one to a zero.
> 
> I'm not sure how many bits are inside a python integer.  The library
> reference says at least 32.

Long ints can have as many bits as you want.

> I'm thinking about writing a function that eats integers and poops out
> lists of bools; and then I can iterate through that, and change values
> in there.  But before I do that, does anyone have a better idea?

Just shift and mask.  Untested code:

    def bit_stream(n):
      p = 1
      while p < n:
        bit = (n & p) != 0
        if rand() % 10 == 0:
           bit = not bit
        p = p * 2
        yield bit

The above assumes you want to look at the bits sequentially, so it
doesn't try to change them inside the number, which would mean consing
up a new number every time a bit changes.  If you want to look at them
all at once, your idea of making a list of bools and flipping a subset
of them is reasonable.  An optimization for long ints would be use the
array module, convert your integer to an array, do a bunch of bit
flips in the array, and convert back.
More information about the Python-list mailing list