iterating bit-by-bit across int?

Discussion in 'Python' started by Matthew Wilson, Oct 23, 2003.

  1. 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?
     
    Matthew Wilson, Oct 23, 2003
    #1
    1. Advertising

  2. Matthew Wilson

    Paul Rubin Guest

    Matthew Wilson <> 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.
     
    Paul Rubin, Oct 23, 2003
    #2
    1. Advertising

  3. 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
     
    Skip Montanaro, Oct 23, 2003
    #3
  4. > 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
     
    Diez B. Roggisch, Oct 23, 2003
    #4
  5. Matthew Wilson

    Brian Kelley Guest

    Paul Rubin wrote:
    > Matthew Wilson <> 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.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.
     
    Brian Kelley, Oct 23, 2003
    #5
  6. Matthew Wilson

    Andrew Dalke Guest

    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
     
    Andrew Dalke, Oct 23, 2003
    #6
  7. Matthew Wilson

    John Ladasky Guest

    Matthew Wilson <> wrote in message news:<>...
    > 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
     
    John Ladasky, Oct 23, 2003
    #7
  8. Matthew Wilson

    Paul Watson Guest

    "Diez B. Roggisch" <> wrote in message
    news:bn9acd$4s6$06$-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"
     
    Paul Watson, Oct 24, 2003
    #8
  9. Matthew Wilson

    Jan Decaluwe Guest

    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)

    '0x800000000000000000000000000FAB4L'


    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
     
    Jan Decaluwe, Oct 24, 2003
    #9
  10. (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 = 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()
     
    Anton Vredegoor, Oct 24, 2003
    #10
  11. Matthew Wilson

    Peter Hansen Guest

    Anton Vredegoor wrote:
    >
    > (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?


    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
     
    Peter Hansen, Oct 24, 2003
    #11
  12. Matthew Wilson

    Tim Roberts Guest

    Brian Kelley <> wrote:

    >Paul Rubin wrote:
    >>
    >> Long ints can have as many bits as you want.

    >
    >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.
    --
    - Tim Roberts,
    Providenza & Boekelheide, Inc.
     
    Tim Roberts, Oct 25, 2003
    #12
  13. Matthew Wilson

    Brian Kelley Guest

    Tim Roberts wrote:

    > Brian Kelley <> wrote:
    >
    >
    >>Paul Rubin wrote:
    >>
    >>>Long ints can have as many bits as you want.

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


    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.
     
    Brian Kelley, Oct 25, 2003
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Schnoffos
    Replies:
    2
    Views:
    1,236
    Martien Verbruggen
    Jun 27, 2003
  2. Hal Styli
    Replies:
    14
    Views:
    1,680
    Old Wolf
    Jan 20, 2004
  3. arun
    Replies:
    8
    Views:
    465
    Dave Thompson
    Jul 31, 2006
  4. Fore
    Replies:
    29
    Views:
    15,395
    Rashad
    Sep 21, 2008
  5. carl
    Replies:
    5
    Views:
    2,424
    James Kanze
    Nov 25, 2009
Loading...

Share This Page