DZone Snippets: binary code

Format IPv4 address in octal binary format and vice versa (Ruby / Rails)

MichaelWhi (Michael Whittaker) — Fri, 28 Dec 2007 14:12:12 GMT

Format an IPv4 address like 192.168.1.1 in dotted binary format like 11000000.10101000.00000001.00000001
You also need this class: http://snippets.dzone.com/posts/show/2472
For Rails: Put this in your controller!



  # convert a dotted decimal IPv4 address to dotted binary format

  def ipv4_to_binary(ipv4addr)

    ia = ipv4addr.to_s.split('.')

    if ia.size != 4

      return "0.0.0.0"

    end

    output = ""

    i = 1

    for octett in ia

      output = output + octett.to_i.to_s(2).using("########","0",true)

      if i < 4

        output = output + "."

      end

      i += 1

    end

    return output

  end

  

  

  # convert a IPv4 adress in binary dotted format to a dotted IPv4 address

  def binary_to_ipv4(ipv4addr)

    ia = ipv4addr.to_s.split('.')

    if ia.size != 4

      return "0.0.0.0"

    end

    output = ""

    i = 1

    for octett in ia

      output = output + octett.to_s.to_i(2).to_s

      if i < 4

        output = output + "."

      end

      i += 1

    end

    return output

  end

Bitwise Operation: Quickly Convert Binary Bit to Integer and vice versa using Javascript Shell

agilekai (kai) — Wed, 07 Nov 2007 05:56:13 GMT

using JavaScript shell found at www.squarefree.com/shell/ , it's very easy to convert binary bit to integer and vice versa

convert integer to binary bit string



num = 1024

num.toString(2)

convert binary bit string to integer



parseInt('111', 2)

Print a binary number in C

scvalex (Alexandru Scvortov) — Tue, 30 Oct 2007 11:53:18 GMT

These are two functions that print the binary representation of an integer. The first simply prints it out, while the second only prints out the relevant digits (i.e. cuts the first x 0 digits) in groups of four.

Explanation here.



#include 



/* Print n as a binary number */

void printbitssimple(int n) {

	unsigned int i;

	i = 1<<(sizeof(n) * 8 - 1);



	while (i > 0) {

		if (n & i)

			printf("1");

		else

			printf("0");

		i >>= 1;

	}

}



/* Print n as a binary number */

void printbits(int n) {

	unsigned int i, step;



	if (0 == n) { /* For simplicity's sake, I treat 0 as a special case*/

		printf("0000");

		return;

	}



	i = 1<<(sizeof(n) * 8 - 1);



	step = -1; /* Only print the relevant digits */

	step >>= 4; /* In groups of 4 */

	while (step >= n) {

		i >>= 4;

		step >>= 4;

	}



	/* At this point, i is the smallest power of two larger or equal to n */

	while (i > 0) {

		if (n & i)

			printf("1");

		else

			printf("0");

		i >>= 1;

	}

}



int main(int argc, char *argv[]) {

	int i;

	for (i = 0; i < 16; ++i) {

		printf("%d = ", i);

		printbitssimple(i);

		printf("\n");

	}



	return 0;

}

Generate all subsets of a set

scvalex (Alexandru Scvortov) — Wed, 10 Oct 2007 14:43:25 GMT

This code generates all the subsets of {1, 2, ..., n} and prints them.

This also contains a very fast binary counter implementation.

See this for further explanations.



#include 



/* Applies the mask to a set like {1, 2, ..., n} and prints it */

void printv(int mask[], int n) {

	int i;

	printf("{ ");

	for (i = 0; i < n; ++i)

		if (mask[i])

			printf("%d ", i + 1); /*i+1 is part of the subset*/

	printf("\b }\n");

}



/* Generates the next mask*/

int next(int mask[], int n) {

	int i;

	for (i = 0; (i < n) && mask[i]; ++i)

		mask[i] = 0;



	if (i < n) {

		mask[i] = 1;

		return 1;

	}

	return 0;

}



int main(int argc, char *argv[]) {

	int n = 3;



	int mask[16]; /* Guess what this is */

	int i;

	for (i = 0; i < n; ++i)

		mask[i] = 0;



	/* Print the first set */

	printv(mask, n);



	/* Print all the others */

	while (next(mask, n))

		printv(mask, n);



	return 0;

}

Binary-to-text converter

Minimiscience (Guildorn Tanaleth) — Thu, 05 Jul 2007 02:37:06 GMT

Converts all 8-bit binary numbers in the standard input into text, though there's probably a better way to do this



#!/usr/bin/perl -wn

use strict;

s/\s//g;

print chr oct "0b$1" while /([01]{8})/g;

print "\n";

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

binarysearch.scm

mcandre (Andrew Pennebaker) — Mon, 19 Feb 2007 00:38:41 GMT

// Binary Search



; Andrew Pennebaker

; 18 Feb 2007

; License: GPL

; URL: http://snippets.dzone.com/posts/show/3535



(define binary-search

	(lambda (ls value low high)

		(let ((mid (floor (/ (+ low high) 2))))

			(cond

				((> low high) -1)

				((= (list-ref ls mid) value) mid)

				((> (list-ref ls mid) value) (binary-search ls value low (- mid 1)))

				((< (list-ref ls mid) value) (binary-search ls value (+ mid 1) high))))))

bindec.scm

mcandre (Andrew Pennebaker) — Thu, 08 Feb 2007 03:21:50 GMT

// Convert list of 1s and 0s back to base ten number.



; Andrew Pennebaker

; 5 Feb 2007

; License: GPL

; URL: http://snippets.dzone.com/posts/show/3479



(define bin->dec

	(lambda (b)

		(cond

			((integer? b) b)

			((= (length b) 0) 0)

			(else

				(+

					(* (expt 2 (- (length b) 1)) (car b))

					(bin->dec (cdr b)))))))

decbin.scm

mcandre (Andrew Pennebaker) — Thu, 08 Feb 2007 03:18:23 GMT

// Converts a base ten integer to a list of 1s and 0s



; Andrew Pennebaker

; 3 Feb 2007

; License: GPL

; URL: http://snippets.dzone.com/posts/show/3478



(define dec->bin

	(lambda (d)

		(cond

			((< d 1) (list 0))

			((= d 1) (list 1))

			((> d 1) (append

				(dec->bin (floor (/ d 2)))

				(list (if (= (modulo d 2) 0) 0 1)))))))