Converting Decimal to Binary in R

February 9, 2012 § Leave a comment

A common task, say in conducting probability simulations, often involves enumerating every possible outcome of a set. It is often useful to use a binary representation of the size of our set to do this. A flexible way to get this representation is in matrix form, which will then allow the usual matrix operations. Here I present one such algorithm and given an implementation in R. The algorithm is iterative. It works on vectors of any length including 1 (a number). And, the algorithm returns an m x n matrix where m is the length of the longest binary digit and n is the length of the vector of numbers you give it.

To get m, the length of the longest binary digit, we use the logarithm (base 2):
m(x) = 1 + \lfloor log_{2}(X) \rfloor

For example, we know that
2 \rightarrow [1,0]

in binary, so
m(2) = 2.

Again,
10 \rightarrow [1,0,1,0], m(10) = 4.

I think the easiest way to explain what we’re going to do here is just walk through some pseudo-code:

Algorithm AS-BINARY
Input: A non-empty list of numbers
Output: A matrix representation of the binary form of each number in x
	b ← 2	// base
	m ← 1 + floor(logb(x))
	n ← length(x)
	R ← matrix(m x n)
	for i from m to 1
		R[i,] ← x mode b	// Ri, is entire row i; operations happen vector-wise
		if i > 1
			x ← integer(x/b)

In R we have:

as.binary <- function (x) { 
  base = 2 
  ndigits = 1 + floor(log(max(x), base)) 
  r = 1) 
    for (i in ndigits:1) { 
        r[i, ]  1) 
          x <- x%/%base 
    } 
  class(r) <- "binaryInt" 
  attr(r, "base") <- base 
  return(r) 
}

Let’s do a couple of examples:

Converting the number 10 to binary (1010)

x <- as.binary(10); x
#	     [,1]
#	[1,]    1
#	[2,]    0
#	[3,]    1
#	[4,]    0
#	attr(,"class")
#	[1] "binaryInt"
#	attr(,"base")
#	[1] 2

Converting each of the numbers in the vector (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) to binary (1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010)

x <- as.binary(1:10); x
#	     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
#	[1,]    0    0    0    0    0    0    0    1    1     1
#	[2,]    0    0    0    1    1    1    1    0    0     0
#	[3,]    0    1    1    0    0    1    1    0    0     1
#	[4,]    1    0    1    0    1    0    1    0    1     0
#	attr(,"class")
#	[1] "binaryInt"
#	attr(,"base")
#	[1] 2

Since it performs the operations vector-wise the entire algorithm is earth-shatteringly fast! Next time I will show how this function can be used as the workhorse in an “all-subsets” regression. That is, when we want to try out every possible model specification on some data.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

What’s this?

You are currently reading Converting Decimal to Binary in R at 196sigma.

meta

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: