## Convert integer to bit array and vice versa?

Discussion of Common Lisp

### Convert integer to bit array and vice versa?

Sorry about the newbie question, but I searched the web and lisp books I have and I can't find the answer to this.

Is there a easy way to convert from an integer to a bit array and vice versa?
conroe64

Posts: 3
Joined: Sun May 15, 2011 7:05 pm

### Re: Convert integer to bit array and vice versa?

I'd be interested to know too. I needed it recently and ended up writing one:
Code: Select all
`(defun bit-vector-to-integer (bits)   (reduce #'(lambda (a b) (+ (ash a 1) b)) bits)); example; (bit-vector-to-integer #*11111111); 255`

But if there is a standard way to do it, I'd sure better use that.
wvxvw

Posts: 127
Joined: Sat Mar 26, 2011 6:23 am

### Re: Convert integer to bit array and vice versa?

There is no standard way to coerce integers to bit-vectors or vice versa because Common Lisp tries to be hardware independent by all means and the binary representation of integers depends on various hard- and software specific issues like big-endian vs. little-endian, signed integers vs. unsigned integers, and if you try to simulate hardware then you also have to simulate all the various register widths and the resulting integer format overflows.

Hardware issues are usually very implementation specific, what means that there are often lots of internal functions available, so try to look-up the "Internals" section of your Common Lisp implementation's manual. But this is then no portable Common Lisp code any more.

Another good infomation source is the Lisp code of projects which deal with more hardware specific languages, e.g the CFFI.

The "inofficial" bit-vector paper is http://home.pipeline.com/~hbaker1/Bitvectors.html

Here are two functions I often use to convert bit-vectors to unsigned (positive) integers and vice versa:

Code: Select all
`(defun bit-vector->integer (bit-vector)  "Create a positive integer from a bit-vector."  (reduce #'(lambda (first-bit second-bit)              (+ (* first-bit 2) second-bit))          bit-vector))(defun integer->bit-vector (integer)  "Create a bit-vector from a positive integer."  (labels ((integer->bit-list (int &optional accum)             (cond ((> int 0)                    (multiple-value-bind (i r) (truncate int 2)                      (integer->bit-list i (push r accum))))                   ((null accum) (push 0 accum))                   (t accum))))    (coerce (integer->bit-list integer) 'bit-vector)))`

The first function is very similar to wvxvw's example, the second function first converts the integer to a list of 0 and 1 integers, and then coerces the list into a bit-vector. Using a list of integers for this is not very efficient. Also please note that there are no special type checks if the arguments are integers or bit-vectors at all, so use the functions at your own risk.

- edgar
edgar-rft

Posts: 224
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

### Re: Convert integer to bit array and vice versa?

Just to make sure we're helping you solve the right problem here, what are you actually trying to do? It may be that CL just has a different way of solving that problem that other languages tackle via bit-vectors.
JamesF

Posts: 98
Joined: Thu Jul 10, 2008 7:14 pm

### Re: Convert integer to bit array and vice versa?

I just dug through my old projects. In one which was built around "bit arrays", I wrote "Don't bother with bit vectors; just use bignums."

Tools like LDB work just fine. http://www.psg.com/~dlamkins/sl/chapter18.html

With a little effort, you can find posts on comp.lang.lisp that come to similar conclusions, and Kent Pitman notes that a C-style "type cast" is implementation-dependent. (in addition to 2's complement, there is 1's complement, BCD, lisp uses tag bits, ...)

nuntius

Posts: 532
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

### Re: Convert integer to bit array and vice versa?

There is also bit logic:

Code: Select all
`(boole boole-ior #xFF00 #x00FF) ==> #xFFFF(boole boole-and #xFF00 #x00FF) ==> 0(ldb (byte 4 0) #xABCD) ==> #xD(ldb (byte 4 4) #xABCD) ==> #xC(ldb (byte 4 8) #xABCD) ==> #xB(ldb (byte 4 8) #xABCD) ==> #xA(ash #x00F0 8) ==> #x0F00(ash #x00F0 -8) ==> #x000F`
Need an online wiki database? My Lisp startup http://www.formlis.com combines a wiki with forms and reports.

Warren Wilkinson

Posts: 116
Joined: Tue Aug 10, 2010 11:24 pm
Location: Calgary, Alberta

### Re: Convert integer to bit array and vice versa?

Sorry to nit-pick, but there's some confusion in your last example:
Code: Select all
`(ldb (byte 4 8) #xABCD) ==> #xA`

You probably wanted it to be:
Code: Select all
`(ldb (byte 4 12) #xABCD) ==> #xA`

And
Code: Select all
`(ash #x00F0 8) ==> #x0F00(ash #x00F0 -8) ==> #x000F`

You probably wanted to move it 4 positions to the left and to the right instead of 8, because 8 would move 2 hex places
Code: Select all
`(ash #x00F0 4) ==> #x0F00(ash #x00F0 -4) ==> #x000F`
wvxvw

Posts: 127
Joined: Sat Mar 26, 2011 6:23 am

### Re: Convert integer to bit array and vice versa?

Hi,
A bit late, but I have developed a simple utility function to get the digits of a number in particular base

Code: Select all
`(defun digits(n &optional (base 10))   (multiple-value-bind (q r) (floor n base)     (if (and (zerop q) (zerop r)) nil    (cons r (digits q base)))))`

CL-USER> (digits 10 2)
(0 1 0 1)
CL-USER> (digits 10 8)
(2 1)

The only drawback is that it digits are in reverse order.
Hope, this helps.
ykm

Posts: 5
Joined: Tue Sep 18, 2012 11:52 pm

### Re: Convert integer to bit array and vice versa?

Hi again,

Following is the missing piece, a reverse function, converting the list obtained from the digit function, back to its number
Code: Select all
`(defun reverse-digits(digits &optional (base 10) (power 0))   (if (null digits) 0       (+ (* (car digits) (expt base power)) (reverse-digits (cdr digits) base (incf power)))))`

CL-USER> (reverse-digits '(0 1 0 1) 2)
10
CL-USER> (reverse-digits '(0 1 0 1) 10)
1010
ykm

Posts: 5
Joined: Tue Sep 18, 2012 11:52 pm