Использование "пепла" в LISP для выполнения бинарного поиска?

Question

Итак, я сейчас читаю Land of Lisp, и Lisp оказывается совершенно другим, чем другие языки программирования, которые я видел.

В любом случае, книга содержит код, который мы должны ввести в 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))

Теперь основная цель состоит в том, чтобы создать игру по угадыванию чисел, в которой пользователь / игрок выбирает число, а затем компьютер пытается угадать число. Он выполняет "двоичный поиск", чтобы найти номер игрока, заставляя игрока сообщать, является ли компьютерное число больше или меньше номера игрока.

Я немного смущен ash функция. Насколько я понимаю, это жизненно важно для бинарного поиска, но я не совсем уверен, почему. Книга несколько объясняет, что она делает, но это немного сбивает с толку.

Что это ash функцию делать? Почему прошло параметры *small* Добавлено в *big* а также -1? Как это работает? Какой цели он служит для бинарного поиска?

Answer 1

Google дает вам эту страницу, которая объясняет, что ash является операцией арифметического сдвига. Так (ash x -1) сдвиг x на один бит вправо, поэтому дает его целую половину.

Answer 2

Спасибо Basile Starynkevitch за помощь в этом...

Во всяком случае, ash выполняет операцию арифметического сдвига.

В случае (ash x -1) это сдвиги x на один бит вправо, что в конечном итоге возвращает целую половину.

Например, рассмотрим двоичное число 1101, 1101 в двоичном коде эквивалентно 13 в десятичном виде, который можно рассчитать так:

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

8 + 4 + 0 + 1 = 13

Бег (ash 13 -1) будет смотреть на двоичное представление 13 и выполнять арифметическое смещение -1, сдвигая все биты вправо на 1. Это даст двоичный вывод 110 (отрубая 1 в конце оригинального номера). 110 в двоичном коде эквивалентно 6 в десятичном виде, который можно рассчитать так:

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

4 + 2 + 0 = 6

Теперь, 13, деленное на 2, не эквивалентно 6, это эквивалентно 6,5, однако, так как он возвратит целую половину, 6 является приемлемым ответом.

Это потому, что двоичный файл является основанием 2.

Answer 3

В. Что делает функция золы? Почему передаются параметры small, добавленные в big и -1? Как это работает? Какую цель он служит для бинарного поиска?

Он выполняет операцию сдвига битов, точнее арифметического сдвига, как объяснено / представлено графически для частного случая Lisp:

> (ash 51 1)
102

Когда вы делаете (ash 51 1) это сместит двоичный код 51 т.е. 110011 на 1 бит место влево и приводит к 1100110 который дает вам 102 в десятичном виде. (процесс преобразования двоичного числа в десятичное объясняется в этом ответе)

Вот это добавляет 0 в пустынном наиболее правильном месте (называемом L восточным S незначительным B it).

> (ash 51 -1)
25

Когда вы делаете (ash 51 -1) это сместит двоичный код 51 т.е. 110011 на 1 бит на правую сторону (отрицательное значение означает противоположное направление) и приводит к 11001 который дает вам 102 в десятичном виде.

Здесь он отбрасывает избыточный LSB.

В конкретном примере игры "guss-my-number", проиллюстрированной в Land of Lisp, мы заинтересованы в уменьшении диапазона в два раза или до среднего. Так, (ash (+ *small* *big*) -1)) будет делить пополам 100+1 = 100 / 2, чтобы получить 50. Мы можем проверить это следующим образом:

> (defparameter *small* 1)
*SMALL*
> (defparameter *big* 100)
*BIG*
> 
(defun guess-my-number ()
    (ash (+ *small* *big*) -1))
GUESS-MY-NUMBER
> (guess-my-number)
50

Интересно отметить, что вы можете удвоить значение целого числа, сдвигая влево на 1 бит, и (приблизительно) вдвое его, сдвинув вправо на 1 бит.