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!
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
reduce works on arbitrary sequences, so you can use it with vectors as well as lists.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
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments