Lisp循环遍历整数位的方式 [英] lisp way of looping over bits of an integer

问题描述

假设我有一个整数，例如109，1101101，二进制.如何遍历此数字的位，例如:[64、32、8、4、1]?用Lisp做到这一点的一个好方法是什么?我应该通过添加大小写来稍微修改for宏还是应该将整数转换为位向量或列表?

Suppose I have an integer such as 109, 1101101 in binary. How do I iterate over bits of this number, eg: [64, 32, 8, 4, 1]? What would be a good way of doing that in lisp? Should I modify the for macro a bit by adding a case or should I just convert the integer into a bit-vector or a list?

推荐答案

如果您只想处理"1"，那么如果所有位很少，那么遍历所有位就没有效率.这是我在这种情况下要做的

If you want to process only "ones" then looping over all bits is not efficient if the ones are few. This is what I'd do in this case

(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补码事实，即对一个数字及其相反的位进行求和将返回最低有效的置位，而对一个数字进行与之相反的操作并返回一个比数字小1的值，则将此最低有效设置位归零.

It uses the nice 2-complement facts that bit-anding a number and its opposite returns the least significant set bit and that bit-anding a number and one less than the number zeroes this least significant set bit.

请注意，此处理从最低有效位到最高有效位(在您的示例中，您使用相反的顺序)

Note that this processing works from the least significant set bit to the most significant (in your example you used the opposite ordering)

这篇关于Lisp循环遍历整数位的方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！