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]

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.

 

[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:
'0xfffeccc'

Skip

 

[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

 

[Brian Kelley]

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.sourceforge.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(genome, num_bits)
print toLSBBinary(bitmask, num_bits)
print toLSBBinary(new_genome, num_bits)


Here's the output of the above

110110010001001010000000101010100010010011
100000101110100000000000000000000000010000
010110111111101010000000101010100010000011

Andrew
(e-mail address removed)

 

[John Ladasky]

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]

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]

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)

'0x800000000000000000000000000FAB4L'


Regards, Jan

 

[Anton Vredegoor]

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 = a*(prob**i)*(1-prob)**(n_bits-i)
print "Probability of the number of bits set:\n"
for i,c in enumerate(chances):
print "%i: %e" %(i,c)

if __name__=='__main__':
test()

 

[Peter Hansen]

This creates a new problem which is interesting in itself. How to
create this integer?

I would think the simplest approach is (similar to a suggestion
already made about the original problem) to predefine a set of bitmasks,
each with only one bit set, then simply select one or more at random
and add (or OR) them together, then XOR the result with the original.

You could either iterate over the list of bitmasks, checking a
random result at each step to decide whether to include that bitmask,
or you could just random.shuffle() the list, then select a random
number of entries from the start of the list. Using the new sum()
(or a filter() with operator.add) would make the whole thing as
simple as a couple of function calls:

genome = 12345678
numMutations = random.randint(0, 4)
mutant = genome ^ sum(random.shuffle(bitmasks)[:numMutations])

# done!!

The algorithm used to select the number of mutations to make could
of course be more sophisticated than the above...

-Peter

 

[Tim Roberts]

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

Oh come on, that's just silly. If that were true, I could not type this at
a Python prompt because it would cause an overflow:

i = -1L

-1L, in fact, has exactly the same number of bits as 1L and, probably,
1048576L.

 

[Brian Kelley]

Oh come on, that's just silly. If that were true, I could not type this at
a Python prompt because it would cause an overflow:

i = -1L

try

i = -1L
while i:
i = i >> 1

and then repeat the statement My only point is that you have to be
careful with long ints.