DZone Snippets: bits code

Calculate 2 to the power of N

dubby (Dave) — Thu, 06 Sep 2007 10:21:15 GMT

// Calculate 2 to the power of N
// Returns "double" value







        private double TwoPowerN(int n)

        {

            int k;

            int i = 1;



            for (k=1; k <= n; k++)

            {

                    i = i * 2;   

            }

            return i

        }

BitField: A fast(ish), pure Ruby bit field "type"

peter (Peter Cooperx) — Mon, 02 Jul 2007 01:16:55 GMT

#        NAME: BitField

#      AUTHOR: Peter Cooper

#     LICENSE: MIT ( http://www.opensource.org/licenses/mit-license.php )

#   COPYRIGHT: (c) 2007 Peter Cooper (http://www.petercooper.co.uk/)

#     VERSION: v4

#     HISTORY: v4 (fixed bug where setting 0 bits to 0 caused a set to 1)

#              v3 (supports dynamic bitwidths for array elements.. now doing 32 bit widths default)

#              v2 (now uses 1 << y, rather than 2 ** y .. it's 21.8 times faster!)

#              v1 (first release)

#

# DESCRIPTION: Basic, pure Ruby bit field. Pretty fast (for what it is) and memory efficient.

#              I've written a pretty intensive test suite for it and it passes great. 

#              Works well for Bloom filters (the reason I wrote it).

#

#              Create a bit field 1000 bits wide

#                bf = BitField.new(1000)

#

#              Setting and reading bits

#                bf[100] = 1

#                bf[100]    .. => 1

#                bf[100] = 0

#

#              More

#                bf.to_s = "10101000101010101"  (example)

#                bf.total_set         .. => 10  (example - 10 bits are set to "1")



class BitField

  attr_reader :size

  include Enumerable

  

  ELEMENT_WIDTH = 32

  

  def initialize(size)

    @size = size

    @field = Array.new(((size - 1) / ELEMENT_WIDTH) + 1, 0)

  end

  

  # Set a bit (1/0)

  def []=(position, value)

    if value == 1

      @field[position / ELEMENT_WIDTH] |= 1 << (position % ELEMENT_WIDTH)

    elsif (@field[position / ELEMENT_WIDTH]) & (1 << (position % ELEMENT_WIDTH)) != 0

      @field[position / ELEMENT_WIDTH] ^= 1 << (position % ELEMENT_WIDTH)

    end

  end

  

  # Read a bit (1/0)

  def [](position)

    @field[position / ELEMENT_WIDTH] & 1 << (position % ELEMENT_WIDTH) > 0 ? 1 : 0

  end

  

  # Iterate over each bit

  def each(&block)

    @size.times { |position| yield self[position] }

  end

  

  # Returns the field as a string like "0101010100111100," etc.

  def to_s

    inject("") { |a, b| a + b.to_s }

  end

  

  # Returns the total number of bits that are set

  # (The technique used here is about 6 times faster than using each or inject direct on the bitfield)

  def total_set

    @field.inject(0) { |a, byte| a += byte & 1 and byte >>= 1 until byte == 0; a }

  end

end

Here's the tests if you want to run:



require "test/unit"

require "bitfield"



class TestLibraryFileName < Test::Unit::TestCase

  def setup

    @public_bf = BitField.new(1000)

  end

  

  def test_basic

    assert_equal 0, BitField.new(100)[0]

    assert_equal 0, BitField.new(100)[1]

  end

  

  def test_setting_and_unsetting

    @public_bf[100] = 1

    assert_equal 1, @public_bf[100]

    @public_bf[100] = 0

    assert_equal 0, @public_bf[100]

  end



  def test_random_setting_and_unsetting

    100.times do

      index = rand(1000)

      @public_bf[index] = 1

      assert_equal 1, @public_bf[index]

      @public_bf[index] = 0

      assert_equal 0, @public_bf[index]

    end

  end

  

  def test_multiple_setting

    1.upto(999) do |pos|

      2.times { @public_bf[pos] = 1 }

      assert_equal 1, @public_bf[pos]

    end

  end



  def test_multiple_unsetting

    1.upto(999) do |pos|

      2.times { @public_bf[pos] = 0 }

      assert_equal 0, @public_bf[pos]

    end

  end

  

  def test_size

    assert_equal 1000, @public_bf.size

  end

  

  def test_to_s

    bf = BitField.new(10)

    bf[1] = 1

    bf[5] = 1

    assert_equal "0100010000", bf.to_s

  end

  

  def test_total_set

    bf = BitField.new(10)

    bf[1] = 1

    bf[5] = 1

    assert_equal 2, bf.total_set

  end

end

Count number of set bits in an integer

peter (Peter Cooperx) — Mon, 02 Jul 2007 01:12:15 GMT



count = 0

count += byte & 1 and byte >>= 1 until byte == 0

Bit Counting and clever loop condition

nevadalife (nevada) — Sat, 23 Sep 2006 17:35:09 GMT



unsigned bit_count(unsigned x) {

    unsigned n;

    for (n = 0; x; n++)

        x &= x-1;

    return n;

}

Binary Data Parser //Javascript Class

jonasraoni (Jonas Raoni Soares Silva) — Fri, 09 Sep 2005 07:44:38 GMT

This is a prototyped class written to serialize and unserialize binary data, so you can read and write binary data files to exchange with programs written in languages like C and Pascal.

Currently the class is able to handle just the following types: signed integers (small 8 bits, short 16 bits, int 32 bits), unsigned integers (byte 8 bits, word 16 bits, dword 32 bits) and floating point (IEEE754 float 32 bits and double 64 bits).

The endianess of the binary values representation can also be configured with the class.

[UPDATED CODE AND HELP CAN BE FOUND HERE]

There's a php version right here.

Code



//+ Jonas Raoni Soares Silva

//@ http://jsfromhell.com/classes/binary-parser [v1.0]



BinaryParser = function( bigEndian, allowExceptions ){

	this.bigEndian = bigEndian;

	this.allowExceptions = allowExceptions;

};

with( { p: BinaryParser.prototype } ){

	with( {p: ( p.Buffer = function( bigEndian, buffer ){ this.bigEndian = bigEndian || 0; this.buffer = []; this.setBuffer( buffer ); } ).prototype } ){

		p.setBuffer = function( data ){

			if( data ){

				for( var l, i = l = data.length, b = this.buffer = new Array( l ); i; b[l - i] = data.charCodeAt( --i ) );

				this.bigEndian && b.reverse();

			}

		};

		p.hasNeededBits = function( neededBits ){

			return this.buffer.length >= -( -neededBits >> 3 );

		};

		p.checkBuffer = function( neededBits ){

			if( !this.hasNeededBits( neededBits ) )

				throw new Error( "checkBuffer::missing bytes" );

		};

		p.readBits = function( start, length ){

			//shl fix: Henri Torgemane ~1996 (compressed by Jonas Raoni)

			function shl( a, b ){

				for( ; b--; a = ( ( a %= 0x7fffffff + 1 ) & 0x40000000 ) == 0x40000000 ? a * 2 : ( a - 0x40000000 ) * 2 + 0x7fffffff + 1 );

				return a;

			}

			if( start < 0 || length <= 0 )

				return 0;

			this.checkBuffer( start + length );

			for( var offsetLeft, offsetRight = start % 8, curByte = this.buffer.length - ( start >> 3 ) - 1, lastByte = this.buffer.length + ( -( start + length ) >> 3 ), diff = curByte - lastByte, sum = ( ( this.buffer[ curByte ] >> offsetRight ) & ( ( 1 << ( diff ? 8 - offsetRight : length ) ) - 1 ) ) + ( diff && ( offsetLeft = ( start + length ) % 8 ) ? ( this.buffer[ lastByte++ ] & ( ( 1 << offsetLeft ) - 1 ) ) << ( diff-- << 3 ) - offsetRight : 0 ); diff; sum += shl( this.buffer[ lastByte++ ], ( diff-- << 3 ) - offsetRight ) );

			return sum;

		};

	}

	p.warn = function( msg ){

		if( this.allowExceptions )

			throw new Error( msg );

		return 1;

	};

	p.decodeFloat = function( data, precisionBits, exponentBits ){

		var b = new this.Buffer( this.bigEndian, data );

		b.checkBuffer( precisionBits + exponentBits + 1 );

		var bias = Math.pow( 2, exponentBits - 1 ) - 1, signal = b.readBits( precisionBits + exponentBits, 1 ), exponent = b.readBits( precisionBits, exponentBits ), significand = 0,

		divisor = 2, curByte = b.buffer.length + ( -precisionBits >> 3 ) - 1;

		do

			for( var byteValue = b.buffer[ ++curByte ], startBit = precisionBits % 8 || 8, mask = 1 << startBit; mask >>= 1; ( byteValue & mask ) && ( significand += 1 / divisor ), divisor *= 2 );

		while( precisionBits -= startBit );

		return exponent == ( bias << 1 ) + 1 ? significand ? NaN : signal ? -Infinity : +Infinity : ( 1 + signal * -2 ) * ( exponent || significand ? !exponent ? Math.pow( 2, -bias + 1 ) * significand : Math.pow( 2, exponent - bias ) * ( 1 + significand ) : 0 );

	};

	p.decodeInt = function( data, bits, signed ){

		var b = new this.Buffer( this.bigEndian, data ), x = b.readBits( 0, bits ), max = Math.pow( 2, bits );

		return signed && x >= max / 2 ? x - max : x;

	};

	p.encodeFloat = function( data, precisionBits, exponentBits ){

		var bias = Math.pow( 2, exponentBits - 1 ) - 1, minExp = -bias + 1, maxExp = bias, minUnnormExp = minExp - precisionBits,

		status = isNaN( n = parseFloat( data ) ) || n == -Infinity || n == +Infinity ? n : 0,

		exp = 0, len = 2 * bias + 1 + precisionBits + 3, bin = new Array( len ),

		signal = ( n = status !== 0 ? 0 : n ) < 0, n = Math.abs( n ), intPart = Math.floor( n ), floatPart = n - intPart,

		i, lastBit, rounded, j, result;

		for( i = len; i; bin[--i] = 0 );

		for( i = bias + 2; intPart && i; bin[--i] = intPart % 2, intPart = Math.floor( intPart / 2 ) );

		for( i = bias + 1; floatPart > 0 && i; ( bin[++i] = ( ( floatPart *= 2 ) >= 1 ) - 0 ) && --floatPart );

		for( i = -1; ++i < len && !bin[i]; );

		if( bin[( lastBit = precisionBits - 1 + ( i = ( exp = bias + 1 - i ) >= minExp && exp <= maxExp ? i + 1 : bias + 1 - ( exp = minExp - 1 ) ) ) + 1] ){

			if( !( rounded = bin[lastBit] ) )

				for( j = lastBit + 2; !rounded && j < len; rounded = bin[j++] );

			for( j = lastBit + 1; rounded && --j >= 0; ( bin[j] = !bin[j] - 0 ) && ( rounded = 0 ) );

		}

		for( i = i - 2 < 0 ? -1 : i - 3; ++i < len && !bin[i]; );

		if( ( exp = bias + 1 - i ) >= minExp && exp <= maxExp )

			++i;

		else if( exp < minExp ){

			exp != bias + 1 - len && exp < minUnnormExp && this.warn( "encodeFloat::float underflow" );

			i = bias + 1 - ( exp = minExp - 1 );

		}

		if( intPart || status !== 0 ){

			this.warn( intPart ? "encodeFloat::float overflow" : "encodeFloat::" + status );

			exp = maxExp + 1;

			i = bias + 2;

			if( status == -Infinity )

				signal = 1;

			else if( isNaN( status ) )

				bin[i] = 1;

		}

		for( n = Math.abs( exp + bias ), j = exponentBits + 1, result = ""; --j; result = ( n % 2 ) + result, n = n >>= 1 );

		for( n = 0, j = 0, i = ( result = ( signal ? "1" : "0" ) + result + bin.slice( i, i + precisionBits ).join( "" ) ).length, r = []; i; j = ( j + 1 ) % 8 ){

			n += ( 1 << j ) * result.charAt( --i );

			if( j == 7 ){

				r[r.length] = String.fromCharCode( n );

				n = 0;

			}

		}

		r[r.length] = n ? String.fromCharCode( n ) : "";

		return ( this.bigEndian ? r.reverse() : r ).join( "" );

	};

	p.encodeInt = function( data, bits, signed ){

		var max = Math.pow( 2, bits );

		( data >= max || data < -( max >> 1 ) ) && this.warn( "encodeInt::overflow" ) && ( data = 0 );

		data < 0 && ( data += max );

		for( var r = []; data; r[r.length] = String.fromCharCode( data % 256 ), data = Math.floor( data / 256 ) );

		for( bits = -( -bits >> 3 ) - r.length; bits--; r[r.length] = "\0" );

		return ( this.bigEndian ? r.reverse() : r ).join( "" );

	};

	p.toSmall    = function( data ){ return this.decodeInt( data,  8, true  ); };

	p.fromSmall  = function( data ){ return this.encodeInt( data,  8, true  ); };

	p.toByte     = function( data ){ return this.decodeInt( data,  8, false ); };

	p.fromByte   = function( data ){ return this.encodeInt( data,  8, false ); };

	p.toShort    = function( data ){ return this.decodeInt( data, 16, true  ); };

	p.fromShort  = function( data ){ return this.encodeInt( data, 16, true  ); };

	p.toWord     = function( data ){ return this.decodeInt( data, 16, false ); };

	p.fromWord   = function( data ){ return this.encodeInt( data, 16, false ); };

	p.toInt      = function( data ){ return this.decodeInt( data, 32, true  ); };

	p.fromInt    = function( data ){ return this.encodeInt( data, 32, true  ); };

	p.toDWord    = function( data ){ return this.decodeInt( data, 32, false ); };

	p.fromDWord  = function( data ){ return this.encodeInt( data, 32, false ); };

	p.toFloat    = function( data ){ return this.decodeFloat( data, 23, 8   ); };

	p.fromFloat  = function( data ){ return this.encodeFloat( data, 23, 8   ); };

	p.toDouble   = function( data ){ return this.decodeFloat( data, 52, 11  ); };

	p.fromDouble = function( data ){ return this.encodeFloat( data, 52, 11  ); };

}