for-loop - lisp循环整数位的方式

Question

假设我有一个整数，例如 109, 1101101 二进制。如何迭代此数字的位，例如：[64, 32, 8, 4, 1]？在 lisp 中这样做的好方法是什么？我应该通过添加一个案例来稍微修改 for 宏，还是应该将整数转换为位向量或列表？

Answer 1

如果您只想处理“一个”，那么如果这些位很少，则循环遍历所有位是无效的。这就是我在这种情况下要做的

(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-complement 事实，即对一个数字和它的对面进行位与运算会返回最低有效设置位，并且将一个数字与比该数字小一的数字与运算会将这个最低有效设置位归零。

请注意，此处理从最低有效设置位到最高有效（在您的示例中，您使用了相反的顺序）

Answer 2

看一下logbitp，它可以让您访问整数的各个位。例如，

(loop for i below (integer-length 109)
      collect (if (logbitp i 109) 1 0))

=> (1 0 1 1 0 1 1)

Answer 3

这可能不太复杂，但可以。请注意，您需要在使用它之前测试“zerop”，因为如果您使用零调用它，则不会调用迭代回调。

(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

另请注意，对于大数字，“ash”可能会变得非常昂贵，在这种情况下，您可能希望使用 6502 的变体。

Answer 4

( 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)