Search code examples
lispcommon-lispland-of-lisp

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

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?

Solution

  • 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.