Предположим, у меня есть целое число, такое как 109, 1101101 в двоичном формате. Как перебрать биты этого числа, например: [64, 32, 8, 4, 1]? Что было бы хорошим способом сделать это в lisp? Должен ли я немного изменить макрос for, добавив случай, или я должен просто преобразовать целое число в битовый вектор или список?
lisp способ перебора битов целого числа
Ответы (4)
Если вы хотите обрабатывать только «единицы», то цикл по всем битам неэффективен, если их мало. вот что бы я сделал в этом случае
(defmacro do-bits ((var x) &rest body)
"Evaluates [body] forms after binding [var] to each set bit in [x]"
(let ((k (gensym)))
`(do ((,k ,x (logand ,k (1- ,k))))
((= ,k 0))
(let ((,var (logand ,k (- ,k))))
,@body))))
Он использует хороший факт с дополнением до 2, что битовое и число и его противоположность возвращает младший значащий установленный бит и что битовое и число и на единицу меньше, чем число, обнуляют этот наименее значащий установленный бит.
Обратите внимание, что эта обработка работает от младшего бита набора до самого старшего (в вашем примере вы использовали противоположный порядок)
Взгляните на logbitp, который позволяет получить доступ к отдельным битам целого числа. Например,
(loop for i below (integer-length 109)
collect (if (logbitp i 109) 1 0))
=> (1 0 1 1 0 1 1)
Это, вероятно, менее сложно, но сойдет. Обратите внимание, что вам нужно проверить `ноль' перед его использованием, потому что, если вы вызовете его с нулем, обратный вызов итерации не будет вызван.
(defun iterate-bits-of (x handler)
(unless (zerop x)
(and (funcall handler (logand x 1))
(iterate-bits-of (ash x -1) handler))))
(iterate-bits-of
#b1101101
#'(lambda (x) (not (format t "bit ~b~&" x))))
;; bit 1
;; bit 0
;; bit 1
;; bit 1
;; bit 0
;; bit 1
;; bit 1
Также обратите внимание, что для больших чисел "ясень" может стать довольно дорогим, и в этом случае вы, вероятно, захотите использовать вариант 6502.
( defun firstbit (x)
( logand x (- x)))
( defun ones (x)
( do (( bit (firstbit x) (firstbit x)) bits)
(( zerop bit) bits)
( setq bits (cons bit bits))
( setq x (logxor x bit))))
обеспечивает
* (ones 109)
(64 32 8 4 1)