Take the 2-minute tour ×

I am having an issue calculating the distance between two bit vectors using common lisp.

I am quite new to lisp and this is the final Homework problem for my Artificial Intelligence homework and believe the issue I am running into is a matter of syntax.

Here is the question:

Write a recursive function DISTANCE between two bit vectors of the same length represented by lists of ones and zeros. For example,

(distance '(1 0 1 1) '(0 1 0 1))

Answer - 3

Discuss what would have to be done, if the vectors were of a different length.

From my understanding the distance between two bit vectors is simply XORing the two and then counting up the 1s.

Using the example we would have 1011 ^ 0101 = 1110 which would equal 3.

Assuming this is the correct method of computing the distance then my issue is finding a way to XOR in lisp in addition to making this recursive.

How can I take two lists and put them into a format that I can use something like logxor (shown here) and then count up the 1s in the resulting list?

While attempting to do (logxor '(1 0 1 1) '(0 1 0 1))it tells me that '(1 0 1 1) is not an integer so it appears that logxor wouldn't work with lists which leaves me at a loss.

Any help that you could offer would be appreciated


share|improve this question
Is the answer positive or negative 3? I'm not sure what you meant by "Answer - 3". –  Joshua Taylor Feb 10 at 0:53
Also note that you're working with lists of bits; Common Lisp actually has bit vectors, which will typically be more efficient than lists of bits. –  Joshua Taylor Feb 10 at 0:54

5 Answers 5

up vote 6 down vote accepted

Your question mentions "bit vectors", but you're actually working with lists of bits. Common Lisp actually provides a bit-vector type, though. It's a specialized type of array. It's still a vector, though, so you can use sequence functions that work on arbitrary sequences (vectors or lists), and so you could write a solution to this that works for bit vectors as well as any other sequences whose elements are bits by using map:

(defun distance (bits1 bits2)
  (reduce '+ (map 'bit-vector 'logxor bits1 bits2)))

It works as expected, but note that you can use bit vectors (which you can write easily with the #*… notation), as well as lists. You don't get this flexibility with mapcar, which works only on lists. Also note the use of (reduce '+ …) rather than (apply '+ …). There are two reasons for this

  1. reduce works on arbitrary sequences, so you can use it with vectors as well as lists.
  2. apply is subject to call-arguments-limit which is the maximum number of arguments that can be passed to a function. While the small cases here aren't going to run afoul of that, if you had larger bit vectors, you could run into that problem.
CL-USER> (distance #*1011 #*0101)
CL-USER> (distance '(1 0 1 1) '(0 1 0 1))
CL-USER> (distance #*1011 '(0 1 0 1))

Rainer Joswig's answer pointed out that you can also do bit operations with integers. Since that's a pretty reasonable thing to do (especially since you can then use the binary integer notation), it's worth making a version that works with that too. Here's an implementation that converts all of its arguments to integers (whether they're already integers or sequences of bits) and uses (logcount (logxor … …)):

(defun distance (bits1 bits2)
  (flet ((to-int (bits)
           (if (integerp bits) bits
               (reduce (lambda (int bit)
                         (logior (ash int 1) bit))
    (logcount (logxor (to-int bits1) (to-int bits2)))))
CL-USER> (distance #b1011 '(0 1 0 1))
CL-USER> (distance #*1011 5)
CL-USER> (distance 11 5)
share|improve this answer
I think this was my main point of confusion with the question. I was unable to find anything about bit vectors using the syntax she provided. –  Jason Bristol Feb 10 at 19:51

LOGXOR works on numbers:

CL-USER 43 > (logxor 2 1)

There is also a notation to write numbers as 0s an 1s.

CL-USER 44 > (logxor #b1010 #b0101)

See also:

CL-USER 45 > (logcount (logxor #b1011 #b0101))
share|improve this answer
Ahh that is useful to know, thanks! –  Jason Bristol Feb 9 at 21:35

Just map logxor to your lists:

? (mapcar #'logxor '(1 0 1 1) '(0 1 0 1))
(1 1 1 0)

and count the ones:

? (count 1 (mapcar #'logxor '(1 0 1 1) '(0 1 0 1)))

or just add everything together:

? (apply #'+ (mapcar #'logxor '(1 0 1 1) '(0 1 0 1)))

Now you only need to convert this to a recursive

(defun distance (lst1 lst2)
  (if (or (null lst1) (null lst2))
    (+ (logxor (car lst1) (car lst2))
       (distance (cdr lst1) (cdr lst2)))))

or tail-recursive version:

(defun distance (lst1 lst2 &optional (res 0))
    (distance (cdr lst1) 
              (cdr lst2) 
              (+ res (logxor (car lst1) (car lst2)))))))


share|improve this answer
This is great, thank you so much. I didn't think of using car and cdr, that makes it a whole lot simpler and lets me use logxor naturally –  Jason Bristol Feb 9 at 21:34
Note that this solution works on lists of bits (which is what the OPs question showed), but not on bit vectors. map would still work on bit-vectors, though, since they're sequences. It would also be better to (reduce '+ …) than to (apply '+ …), because apply is subject to call-arguments-limit, which could be a problem with bigger vectors. –  Joshua Taylor Feb 10 at 0:57

The simple recursive version is not tail-recursive:

(defun distance (v u)
  (cond ((null v) (length u)) ; assume that missing is different from both 0 & 1
        ((null u) (length v)) ; ditto
        (t (+ (if (= (first u) (first v)) 0 1) 
              (distance (rest v) (rest u))))))

This corresponds to the axiomatic definition of distance (the number of discrepancies) as

  1. if one vector is empty, the distance is the length of the other
  2. the distance is additive: dist(v1,u1)+dist(v2,u2)=dist(v1+v2,u1+u2) if length(v1)=length(u1); + means concatenation
  3. if length(v1)=length(v2)=1, then dist(v1,v2):=(v1==v2? 0 : 1)

If you need a tail-recursive version (which can be easier converted to iteration by the compiler), you would need to carry the partial result with the function.

share|improve this answer

If you want to use one simple defun statement you could always do something like.

(defun distance (a b)
          ((equal nil a) 0)
          (t (+ (rem (+ (first a) (first b)) 2) (distance (rest a) (rest b))))
share|improve this answer
Explain why this works by editing the answer. –  Bleeding Fingers Feb 9 at 20:43
This is more complicated than it needs to be, and it won't work with bit vectors (though it will work with lists of bits, which are what's actually shown in the question). –  Joshua Taylor Feb 10 at 1:07

Your Answer


