Search code examples
common-lispbitvector

Distance between two bit vectors in LISP

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!

Solution

  • 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