Never been to DZone Snippets before?

Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

« Newer Snippets
Older Snippets »
Showing 1-5 of 5 total  RSS 

Calculate 2 to the power of N

// 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
        }
to math bits bytes power by dubby on Sep 06, 2007

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

#        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
to ruby binary bits bit bloom by peter on Jul 01, 2007 3 Comments

Count number of set bits in an integer

count = 0
count += byte & 1 and byte >>= 1 until byte == 0
to ruby binary bits count bitwise by peter on Jul 01, 2007

Bit Counting and clever loop condition

unsigned bit_count(unsigned x) {
    unsigned n;
    for (n = 0; x; n++)
        x &= x-1;
    return n;
}
to c bits count algorithm by nevadalife on Sep 23, 2006

Binary Data Parser //Javascript Class



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  ); };
}
to javascript binary parser hexadecimal ieee754 integer bits bytes ieee float double jonas jsfromhell raoni by jonasraoni on Sep 09, 2005
« Newer Snippets
Older Snippets »
Showing 1-5 of 5 total  RSS