Using 'ash' in LISP to perform a binary search?

2018-06-21 16:58:14

So, I'm reading Land of Lisp now, and Lisp is turning out to be quite different than other programming languages that I've seen.

Anyways, the book provides some code that we're meant to enter into the CLISP REPL:

(defparameter *small* 1)
(defparameter *big* 100)

(defun guess-my-number ()
    (ash (+ *small* *big*) -1))

(defun smaller ()
    (setf *big* (1- (guess-my-number)))
    (guess-my-number))

(defun bigger ()
    (setf *small* (1+ (guess-my-number)))
    (guess-my-number))

Now, the basic goal is to create a number guessing game wherein the user/player chooses a number, and then the computer tries to guess the number. It performs a "binary search", to find the player's number, by having the player report whether the computer-guessed number is higher or lower than the player's number.

I'm a little bit confused about the ash function. It's my understanding that this is vital to the binary search, but I'm not really sure why. The book somewhat explains what it does, but it's a little confusing.

What does the ash function do? Why is it passed the parameters of *small* added to *big* and -1 ? How does it work? What purpose does it serve to the binary search?

Google gives you this page which explains that ash is an arithmetic shift operation. So (ash x -1) shift x by one bit to the right, so gives its integer half.

Thanks to Basile Starynkevitch for the help on this one...

Anyhow, ash performs an arithmetic shift operation.

In the case of (ash x -1) it shifts x by one bit to the right, which ultimately returns the integer half.

For example, consider the binary number 1101 . 1101 in binary is equivalent to 13 in decimal, which can be calculated like so:

8 * 1 = 8
4 * 1 = 4
2 * 0 = 0
1 * 1 = 1

8 + 4 + 0 + 1 = 13

Running (ash 13 -1) would look at the binary representation of 13, and perform an arithmetic shift of -1, shifting all the bits to the right by 1. This would produce a binary output of 110 (chopping off the 1 at the end of the original number). 110 in binary is equivalent to 6 in decimal, which can be calculated like so:

4 * 1 = 4
2 * 1 = 2
1 * 0 = 0

4 + 2 + 0 = 6

Now, 13 divided by 2 is not equivalent to 6, it's equivalent to 6.5, however, since it will return the integer half, 6 is the acceptable answer.

This is because binary is base 2.

链接地址: http://www.djcxy.com/p/60946.html

上一篇: 如何检查一个特定的密钥是否存在于一个散列中？

下一篇: 在LISP中使用“灰”来执行二分搜索？