Convert integer to bit array and vice versa?

Discussion of Common Lisp

Convert integer to bit array and vice versa?

Postby conroe64 » Sun May 15, 2011 7:08 pm

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?

Postby wvxvw » Sun May 15, 2011 11:11 pm

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?

Postby edgar-rft » Mon May 16, 2011 1:49 pm

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: 154
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Convert integer to bit array and vice versa?

Postby JamesF » Mon May 16, 2011 6:33 pm

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: 95
Joined: Thu Jul 10, 2008 7:14 pm

Re: Convert integer to bit array and vice versa?

Postby nuntius » Mon May 16, 2011 7:37 pm

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, ...)
User avatar
nuntius
 
Posts: 498
Joined: Sat Aug 09, 2008 10:44 am
Location: Burlington, MA

Re: Convert integer to bit array and vice versa?

Postby Warren Wilkinson » Thu May 19, 2011 10:54 pm

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.
User avatar
Warren Wilkinson
 
Posts: 116
Joined: Tue Aug 10, 2010 11:24 pm
Location: Calgary, Alberta

Re: Convert integer to bit array and vice versa?

Postby wvxvw » Sat May 21, 2011 4:18 am

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?

Postby ykm » Wed Sep 26, 2012 12:46 am

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?

Postby ykm » Wed Sep 26, 2012 12:57 am

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


Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 1 guest