iterating bit-by-bit across int?

[Matthew Wilson]

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.

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?

[Paul Rubin]

Matthew Wilson <mw*****@sarcas tic-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.

[Diez B. Roggisch]

> 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?

For speed, you should use shift and boolean ops - like this:

def mutate(seq, n=32, prob=0.05):
for bit in xrange(n):
if random.random() <= prob:
seq ^= 1 << bit
return seq

Regards,

Diez

[Skip Montanaro]

Matthew> I'm playing around with genetic algorithms and I want to write
Matthew> a function that mutates an integer by iterating across the
Matthew> bits, and about 1 in 10 times, it should switch a zero to a
Matthew> one, or a one to a zero.

Just use Python's bitwise ops, for example:

x = 0x0FFFCCCC
hex(x) '0xfffcccc' hex(x | (1 << 13))

'0xfffeccc'

Skip

[Brian Kelley]

Paul Rubin wrote:

Matthew Wilson <mw*****@sarcas tic-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.

Such as -1L which has an infinite number of bits.

I have used a list of integers as my defacto standard for representing a
stream of bits. On my windows box this is slower than using a long
integer but with psyco running (psyco.sourcefo rge.net) it is faster than
the long integer implementation.

It also is faster to bail out on a comparison, for example

if (a&b)!= 0:

can be optimized to fail on the first integer failure, it doesn't have
to complete the operation as it would with a long integer.

This is useful when seeing if a bit string is contained inside another
bit string.

[Andrew Dalke]

Matthew Wilson:

I'm not sure how many bits are inside a python integer. The library
reference says at least 32.
Platform dependent. Could be 64 on 64 bit machines.
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?

Python isn't good for that sort of low-level bit twiddling.

Here's another possibility. Use a long int as your genome,
then make a new long int which describes the bits which
need to be inverted, then apply an xor between them.

import random

def toLSBBinary(x, num_bits):
letters = []
for i in range(num_bits) :
if x & (1L << i):
letters.append( "1")
else:
letters.append( "0")
return "".join(letters )

genome = 3454579853467L
num_bits = 42

bitmask = 0
for i in range(num_bits) :
if random.random() < 0.1:
bitmask += 1L<<i

# genome bit, bitmask -> new value for genome
# if the bitmask is 0, don't change anything
# if it is 1, invert the value
# 0 0 -> 0
# 1 0 -> 1
# 0 1 -> 1
# 1 1 -> 0
# This is an xor
new_genome = (genome ^ bitmask)

print toLSBBinary(gen ome, num_bits)
print toLSBBinary(bit mask, num_bits)
print toLSBBinary(new _genome, num_bits)
Here's the output of the above

110110010001001 010000000101010 100010010011
100000101110100 000000000000000 000000010000
010110111111101 010000000101010 100010000011

Andrew
da***@dalkescie ntific.com

[John Ladasky]

Matthew Wilson <mw*****@sarcas tic-horse.com> wrote in message news:<sl******* *************@f rank.homelinux. net>...

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.
It can vary from system to system, and is designed to accomodate
growth. Use sys.maxint to find out how large an integer is on your
system.
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?

Using your approach, you would first need to disassemble the integer,
then reassemble it. You can cut this bitwise cranking in half.
Define an integer, in which 10% of the bits is a "1". Then do an
exclusive-or operation between this integer and the one you wish to
mutate.

http://www.python.org/cgi-bin/moinmoin/BitwiseOperators

--
John J. Ladasky Jr., Ph.D.
Department of Biology
Johns Hopkins University
Baltimore MD 21218
USA
Earth

[Paul Watson]

"Diez B. Roggisch" <de************ @web.de> wrote in message
news:bn******** *****@news.t-online.com...

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?

For speed, you should use shift and boolean ops - like this:

def mutate(seq, n=32, prob=0.05):
for bit in xrange(n):
if random.random() <= prob:
seq ^= 1 << bit
return seq

Regards,

Diez

And you might want to make a list of precalculated masks using the shift
operator for even more speed.

#! /usr/bin/env python

import sys

print sys.maxint

i = sys.maxint
bitcount = 0

while (i != 0):
i >>= 1
bitcount += 1

print "i = %d" % (i)
print "bitcount = %d" % (bitcount)

masklist = []
for i in range(bitcount) :
masklist.append (1 << i)
masklist.append (sys.maxint + 1)

for i in masklist:
print hex(i)

thelist = [0x7F, 0x5A5A5A5A]

for i in thelist:
for mask in masklist:
if ((i & mask) <> 0):
# do True thing
print "True"
else:
# do False thing
print "False"

[Jan Decaluwe]

Matthew Wilson wrote:

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.

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?

You may be interested in the 'intbv' class that is part of my 'myhdl'
package for hardware design (link: see signature).

An intbv behaves like a Python long with an indefinite number of bits.
However, it is a mutable type that can also be used as a bitvector
through an indexing and slicing interface. Warning: slicing ranges are
downward as is common in hardware design but uncommon in Python.

Demo:

from myhdl import intbv
n = intbv(0xDE)
n[:8] = 0xFA
hex(n) '0xFADEL' n[8:] = 0xB4
hex(n) '0xFAB4L' for bit in n[12:8]: .... print bit
....
1
0
1
0 n[123] intbv(0L) n[123] = 1
hex(n)

'0x800000000000 000000000000000 FAB4L'
Regards, Jan

--
Jan Decaluwe - Resources bvba - http://jandecaluwe.com
Losbergenlaan 16, B-3010 Leuven, Belgium
Bored with EDA the way it is? Check this:
http://jandecaluwe.com/Tools/MyHDL/Overview.html

[Anton Vredegoor]

la*****@my-deja.com (John Ladasky) wrote:

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?

Using your approach, you would first need to disassemble the integer,
then reassemble it. You can cut this bitwise cranking in half.
Define an integer, in which 10% of the bits is a "1". Then do an
exclusive-or operation between this integer and the one you wish to
mutate.

This creates a new problem which is interesting in itself. How to
create this integer? One idea is to first choose *how many* bits are
"1" and next randomly choose from one of the possible placements of
these bits inside an integer. Below I'm computing the probability
distribution for the number of bits that are set.

Anton

def noverk(n, k):
result = 1l
for i in range(k):
result = result *(n - i) / (i + 1)
return result

def test():
prob = 1/10.0
n_bits = 32
chances = [0.0 for i in range(n_bits+1)]
for i in range(n_bits+1) :
a = noverk(n_bits,i )
chances[i] = a*(prob**i)*(1-prob)**(n_bits-i)
print "Probabilit y of the number of bits set:\n"
for i,c in enumerate(chanc es):
print "%i: %e" %(i,c)

if __name__=='__ma in__':
test()