ga_bitstring.c

http://gaul.sourceforge.net/ 这里大部分人讨论的是在Matlab里实现GA的toolbox.以上为一个GA的C语言的软件包.如果你想利用GA做优化算法,非常有用.而且有

/**********************************************************************
  ga_bitstring.c
 **********************************************************************

  ga_bitstring - GAUL's low-level bitstring routines.
  Copyright ©2001-2003, Stewart Adcock <[e-mail]>
  All rights reserved.

  The latest version of this program should be available at:
  http://gaul.sourceforge.net/

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.  Alternatively, if your project
  is incompatible with the GPL, I will probably agree to requests
  for permission to use the terms of any other license.

  This program is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY WHATSOEVER.

  A full copy of the GNU General Public License should be in the file
  "COPYING" provided with this distribution; if not, see:
  http://www.gnu.org/

 **********************************************************************

  Synopsis:     Low-level bitstring handling functions.

		Note that there is a lack of sanity checking in here
		for efficiency reasons.  Parameter safety should be
		confirmed in the wrapper functions.

  To do:	Mappings.

  FIXME:	Performance of gray encoding/decoding is dreadful now
  		that it uses malloc/free.  There is also a bug in these
		routines.

 **********************************************************************/

#include "gaul/ga_bitstring.h"

/**********************************************************************
  ga_bit_new()
  synopsis:	Create a new bitstring.
  parameters:	int	length	Number of bits.
  return:	byte	*ptr	Newly allocated bitstring.
  last updated:	30/06/01
 **********************************************************************/

byte *ga_bit_new( int length )
  {
  byte *ptr;

  if ( !(ptr = (byte *) s_malloc( ga_bit_sizeof( length ) )) )
    die("Unable to allocate bitstring.");

  return ptr;
  }


/**********************************************************************
  ga_bit_free()
  synopsis:	Deallocates a bitstring.
  parameters:	byte	*bstr	Bitstring to deallocate.
  return:	none
  last updated:	30/06/01
 **********************************************************************/

void ga_bit_free( byte *bstr )
  {
  s_free( bstr );

  return;
  }


/**********************************************************************
  ga_bit_set()
  synopsis:	Sets a single bit in a bitstring.
  parameters:	byte	*bstr	Bitstring.
		int	n	Bit index.
  return:	none
  last updated:	30/06/01
 **********************************************************************/

void ga_bit_set( byte *bstr, int n )
  {
  bstr[n/BYTEBITS] |= 1 << ( n%BYTEBITS );

  return;
  }


/**********************************************************************
  ga_bit_clear()
  synopsis:	Unsets a single bit in a bitstring.
  parameters:	byte	*bstr	Bitstring.
		int	n	Bit index.
  return:	none
  last updated:	07 Sep 2003
 **********************************************************************/

void ga_bit_clear( byte *bstr, int n )
  {
  bstr[n/BYTEBITS] &= ~(1 << ( n%BYTEBITS ));

  return;
  }


/**********************************************************************
  ga_bit_invert()
  synopsis:	Toggles a single bit in a bitstring.
  parameters:	byte	*bstr	Bitstring.
		int	n	Bit index.
  return:	none
  last updated:	07 Sep 2003
 **********************************************************************/

void ga_bit_invert( byte *bstr, int n )
  {
  bstr[n/BYTEBITS] ^= 1 << (n % BYTEBITS);

  return;
  }


/**********************************************************************
  ga_bit_get()
  synopsis:	Returns the state of a single bit in a bitstring.
  parameters:	byte	*bstr	Bitstring.
		int	n	Bit index.
  return:	boolean	val	The bit's state.
  last updated:	30/06/01
 **********************************************************************/

boolean ga_bit_get( byte *bstr, int n )
  {
  return (boolean) ( (bstr[n/BYTEBITS] & (1 << (n % BYTEBITS))) != 0 );
  }


/**********************************************************************
  ga_bit_randomize()
  synopsis:	Randomly sets the state of a single bit in a bitstring.
  parameters:	byte	*bstr	Bitstring.
		int	n	Bit index.
  return:	none
  last updated:	30/06/01
 **********************************************************************/

void ga_bit_randomize( byte *bstr, int n )
  {
  if ( random_boolean() )
    ga_bit_set( bstr, n );
  else
    ga_bit_clear( bstr, n );

  return;
  }


/**********************************************************************
  ga_bit_copy()
  synopsis:	Copies a set of bits in a bitstring.
		If dest and src are the same, overlapping sequences
		of bits are safely handled.
 
		FIXME: Should use memcpy, when appropriate.
  parameters:	byte	*dest	Destination bitstring.
		byte	*src	Source bitstring
		int	ndest	Initial bit index of destination bits.
		int	nsrc	Initial bit index of source bits.
		int	length	Number of bits to copy.
  return:	none
  last updated:	29 Jun 2003
 **********************************************************************/

void ga_bit_copy( byte *dest, byte *src, int ndest, int nsrc, int length )
  {
  int i;

  if (dest != src || ndest < nsrc)
    {
    for ( i=0; i < length; ++i )
      {
      if ( ga_bit_get(src, nsrc+i) )
        ga_bit_set( dest, ndest+i );
      else
        ga_bit_clear( dest, ndest+i );
      }
    }
  else
    {
    for ( i = length-1 ; i >= 0; --i )
      {
      if ( ga_bit_get(src, nsrc+i) )
        ga_bit_set( dest, ndest+i );
      else
        ga_bit_clear( dest, ndest+i );
      }
    }

  return;
  }


/**********************************************************************
  ga_bit_sizeof()
  synopsis:	Return the size required for the given number of
		bits, rounded up if needed.
  parameters:	int	length	Number of bits.
  return:	none
  last updated:	30/06/01
 **********************************************************************/

size_t ga_bit_sizeof( int length )
  {
/* Note that sizeof(byte) should always be 1. */
  return sizeof(byte) * (length+BYTEBITS-1) / BYTEBITS;
  }


/**********************************************************************
  ga_bit_clone()
  synopsis:	Copies a complete bitstring.
  parameters:	byte	*dest	Destination bitstring.
		byte	*src	Source bitstring
		int	length	Number of bits in bitstrings.
  return:	none
  last updated:	30/06/01
 **********************************************************************/

byte *ga_bit_clone( byte *dest, byte *src, int length )
  {
  if (!dest) dest=ga_bit_new( length );

  memcpy( dest, src, ga_bit_sizeof( length ) );

  return dest;
  }


/**********************************************************************
  ga_bit_decode_binary_uint()
  synopsis:	Convert a binary-encoded bitstring into an unsigned int
		starting at a given offset. 
  parameters:
  return:
  last updated: 08 Jan 2003
 **********************************************************************/

unsigned int ga_bit_decode_binary_uint( byte *bstr, int n, int length )
  {
  int		i;
  unsigned int	value=0;	/* Decoded value. */

  for ( i=n; i < n+length; i++ )
    {
    value <<= 1;
    value |= ga_bit_get(bstr, i);
    }

  return value;
  }


/**********************************************************************
  ga_bit_encode_binary_uint()
  synopsis:	Convert an unsigned int into a binary-encoded bitstring
		starting at a given offset. 
  parameters:
  return:
  last updated: 08 Jan 2003
 **********************************************************************/

void ga_bit_encode_binary_uint( byte *bstr, int n, int length, unsigned int value )
  {
  int i;

  /* Set bits in _reverse_ order. */
  for ( i = n+length-1; i >= n; i-- )
    {
    if ( value & 1 )
      ga_bit_set( bstr, i );
    else
      ga_bit_clear( bstr, i );

    value >>= 1;
    }

  return;
  }


/**********************************************************************
  ga_bit_decode_binary_int()
  synopsis:	Convert a binary-encoded bitstring into a signed int
		starting at a given offset. 
  parameters:
  return:
  last updated: 08 Jan 2003
 **********************************************************************/

int ga_bit_decode_binary_int( byte *bstr, int n, int length )
  {
  if ( ga_bit_get( bstr, n ) )
    return (int) -ga_bit_decode_binary_uint( bstr, n+1, length-1 );
  else
    return (int) ga_bit_decode_binary_uint( bstr, n+1, length-1 );
  }


/**********************************************************************
  ga_bit_encode_binary_int()
  synopsis:	Convert a signed int into a binary-encoded bitstring
		starting at a given offset. 
  parameters:
  return:
  last updated: 08 Jan 2003
 **********************************************************************/

void ga_bit_encode_binary_int( byte *bstr, int n, int length, int value )
  {
  if ( value < 0 )
    {
    ga_bit_set( bstr, n );
    value = -value;
    }
  else
    {
    ga_bit_clear( bstr, n );
    }

  ga_bit_encode_binary_uint( bstr, n+1, length-1, (unsigned int) value );

  return;
  }


/**********************************************************************
  gray_to_binary()
  synopsis:	Convert a Gray-encoded bitstring into a binary-encoded