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]

Re: iterating bit-by-bit across int?

Matthew Wilson <mwilson@sarcas tic-horse.com> writes:[color=blue]
> 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.[/color]

Long ints can have as many bits as you want.
[color=blue]
> 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?[/color]

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]

Re: iterating bit-by-bit across int?

> I'm thinking about writing a function that eats integers and poops out[color=blue]
> 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?[/color]

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]

Re: iterating bit-by-bit across int?


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:
[color=blue][color=green][color=darkred]
>>> x = 0x0FFFCCCC
>>> hex(x)[/color][/color][/color]
'0xfffcccc'[color=blue][color=green][color=darkred]
>>> hex(x | (1 << 13))[/color][/color][/color]
'0xfffeccc'

Skip

[Brian Kelley]

Re: iterating bit-by-bit across int?

Paul Rubin wrote:[color=blue]
> Matthew Wilson <mwilson@sarcas tic-horse.com> writes:
>[color=green]
>>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.[/color]
>
>
> Long ints can have as many bits as you want.[/color]

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]

Re: iterating bit-by-bit across int?

Matthew Wilson:[color=blue]
> I'm not sure how many bits are inside a python integer. The library
> reference says at least 32.[/color]

Platform dependent. Could be 64 on 64 bit machines.
[color=blue]
> 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?[/color]

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
dalke@dalkescie ntific.com

[John Ladasky]

Re: iterating bit-by-bit across int?

Matthew Wilson <mwilson@sarcas tic-horse.com> wrote in message news:<slrnbpgah 9.22u.mwilson@f rank.homelinux. net>...[color=blue]
> 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.[/color]

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.
[color=blue]
> 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?[/color]

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]

Re: iterating bit-by-bit across int?

"Diez B. Roggisch" <deets_noospaam @web.de> wrote in message
news:bn9acd$4s6 $06$1@news.t-online.com...[color=blue][color=green]
> > 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?[/color]
>
> 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[/color]

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]

Re: iterating bit-by-bit across int?

Matthew Wilson wrote:[color=blue]
> 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?[/color]

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:
[color=blue][color=green][color=darkred]
>>> from myhdl import intbv
>>> n = intbv(0xDE)
>>> n[:8] = 0xFA
>>> hex(n)[/color][/color][/color]
'0xFADEL'[color=blue][color=green][color=darkred]
>>> n[8:] = 0xB4
>>> hex(n)[/color][/color][/color]
'0xFAB4L'[color=blue][color=green][color=darkred]
>>> for bit in n[12:8]:[/color][/color][/color]
.... print bit
....
1
0
1
0[color=blue][color=green][color=darkred]
>>> n[123][/color][/color][/color]
intbv(0L)[color=blue][color=green][color=darkred]
>>> n[123] = 1
>>> hex(n)[/color][/color][/color]
'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]

Re: iterating bit-by-bit across int?

ladasky@my-deja.com (John Ladasky) wrote:
[color=blue][color=green]
>> 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?[/color]
>
>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.[/color]

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()

[Peter Hansen]

Re: iterating bit-by-bit across int?

Anton Vredegoor wrote:[color=blue]
>
> ladasky@my-deja.com (John Ladasky) wrote:
>[color=green][color=darkred]
> >> 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?[/color]
> >
> >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.[/color]
>
> This creates a new problem which is interesting in itself. How to
> create this integer?[/color]

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.shuf fle(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]

Re: iterating bit-by-bit across int?

Brian Kelley <bkelley@wi.mit .edu> wrote:
[color=blue]
>Paul Rubin wrote:[color=green]
>>
>> Long ints can have as many bits as you want.[/color]
>
>Such as -1L which has an infinite number of bits.[/color]

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.
--
- Tim Roberts, timr@probo.com
Providenza & Boekelheide, Inc.

[Brian Kelley]

Re: iterating bit-by-bit across int?

Tim Roberts wrote:
[color=blue]
> Brian Kelley <bkelley@wi.mit .edu> wrote:
>
>[color=green]
>>Paul Rubin wrote:
>>[color=darkred]
>>>Long ints can have as many bits as you want.[/color]
>>
>>Such as -1L which has an infinite number of bits.[/color]
>
>
> 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
>[/color]

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.