LISP中循环遍历整数位的方法

Question

假设我有一个整数，例如109，1101101的二进制表示。如何迭代这个数字的位，例如：[64，32，8，4，1]？在Lisp中应该如何做？我应该通过添加一个case来修改for宏，还是应该将整数转换为位向量或列表？

- Mark

Answer 1

如果你只想处理“1”位，那么如果“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))))

它使用了一个很好的二进制补码事实，即对一个数字和它的相反数进行按位与运算会返回最低有效位，并且对一个数字和比该数字小1的数字进行按位与运算会将这个最低有效位清零。

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

- 6502

Answer 2

请看logbitp，它允许您访问整数的单个位。例如：

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

=> (1 0 1 1 0 1 1)

- huaiyuan

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的变体。

- user797257

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)

- peawormsworth