Distance between two bit vectors in LISP

Question

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

Thanks!

Answer 1

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)
3
CL-USER> (distance '(1 0 1 1) '(0 1 0 1))
3
CL-USER> (distance #*1011 '(0 1 0 1))
3

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))
                       bits))))
    (logcount (logxor (to-int bits1) (to-int bits2)))))

CL-USER> (distance #b1011 '(0 1 0 1))
3
CL-USER> (distance #*1011 '(0 1 0 1))
3
CL-USER> (distance #*1011 5)
3
CL-USER> (distance 11 5)
3

Answer 2

LOGXOR works on numbers:

CL-USER 43 > (logxor 2 1)
3

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

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

See also:

CL-USER 45 > (logcount (logxor #b1011 #b0101))
3

Answer 3

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)))
3

or just add everything together:

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

Now you only need to convert this to a recursive

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

or tail-recursive version:

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

then

? (distance '(1 0 1 1) '(0 1 0 1))
3

Answer 4

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.

Answer 5

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

(defun distance (a b)
     (cond
          ((equal nil a) 0)
          (t (+ (rem (+ (first a) (first b)) 2) (distance (rest a) (rest b))))
     )
)