for-loop - 整数のビットをループする Lisp の方法

Question

バイナリで 109、1101101 などの整数があるとします。[64, 32, 8, 4, 1] など、この数値のビットを反復処理するにはどうすればよいですか? Lispでそれを行う良い方法は何でしょうか? ケースを追加して for マクロを少し変更する必要がありますか、それとも整数をビットベクトルまたはリストに変換する必要がありますか?

Answer 1

整数の個々のビットにアクセスできるlogbitpを見てください。例えば、

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

=> (1 0 1 1 0 1 1)

Answer 2

「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 少ないビット アンド 演算がこの最下位セット ビットをゼロにするという優れた 2 の補数の事実を使用します。

この処理は、最下位セット ビットから最上位セット ビットまで機能することに注意してください (この例では、逆の順序を使用しました)。

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 のバリアントを使用することをお勧めします。