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

Question

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

В любом случае, в книге представлен код, который мы должны ввести в REPL CLISP:

(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

Благодарю Василия Старынкевича за помощь в этом ...

В любом случае, 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

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

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

> (ash 51 1)
102

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

Вот оно добавляет 0 в наиболее свободном месте (называемом L восток S воспламеняющийся B это).

> (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 бит.