CODEWITHSUNDEEP
for-looplispcommon-lispbit-manipulationsbcl
Mark
Mark

Reputation: 8688

lisp way of looping over bits of an integer

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?

Upvotes: 3

Views: 1206

Answers (4)

peawormsworth
peawormsworth

Reputation: 1220

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

provides

* (ones 109)

(64 32 8 4 1)

Upvotes: -1

user797257
user797257

Reputation:

This is probably less sophisticated, but will do. Note that you need to test for `zerop' before using it, because if you call it with zero the iteration callback will not be called.

(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

Also note that for big numbers `ash' may become quite expensive, in which case you probably want to use 6502's variant.

Upvotes: 0

huaiyuan
huaiyuan

Reputation: 26539

Take a look at logbitp, which lets you access individual bits of an integer. For example,

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

=> (1 0 1 1 0 1 1)

Upvotes: 6

6502
6502

Reputation: 114529

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

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)

Upvotes: 6

Related Questions