Convert integer to bit array and vice versa?

[conroe64]

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?

[wvxvw]

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.

[edgar-rft]

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

[JamesF]

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.

[nuntius]

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, ...)

[Warren Wilkinson]

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



[wvxvw]

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

[ykm]

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]

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