整数のビットをループするlispの方法

Question

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

Answer 1

"ones"だけを処理したい場合、すべてのビットをループするのは効率的ではありません。これは、それは少し-AND演算数とその反対は最下位セットビットとそのビットの論理積数と1以下を返し素敵な2補体事実を使用しています私はこのケースで

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

を行いたいです数字よりもこの最下位ビットが0になります。この処理が最上位に最下位セットビットから動作することを

注意（あなたの例では、あなたが逆の順序付けを使用）

Answer 2

これはおそらく、あまり洗練されているが、行います。ゼロを呼び出すと、反復コールバックは呼び出されないので、使用する前に `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 

大きな数字の場合、「灰」は非常に高価になることがあります。この場合、おそらく6502のバリアントを使用することになります。

Answer 3

logbitpを見ると、整数の個々のビットにアクセスできます。たとえば、

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

=> (1 0 1 1 0 1 1)