; population count

(define (ash int cnt)
  (if (negative? cnt)
      (let ((n (expt 2 (- cnt))))
        (if (negative? int)
            (+ -1 (quotient (+ 1 int) n))
            (quotient int n)))
      (* (expt 2 cnt) int)))

(define (logand a b)
  (if (or (zero? a) (zero? b)) 0
    (+ (* (logand (floor (/ a 2)) (floor (/ b 2))) 2)
       (if (or (even? a) (even? b)) 0 1))))

(define (pop-count n)
  (let loop ((n n) (count 0))
    (if (zero? n) count
      (loop (ash n -1) (+ count (logand n 1))))))

(display (pop-count 23)) (newline)
(display (pop-count 23451449)) (newline)

(define (pop-count n)
  (let ((bits #(0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4)))
    (let loop ((n n) (count 0))
      (if (zero? n) count
        (loop (ash n -4) (+ count (vector-ref bits (logand n #xF))))))))

(display (pop-count 23)) (newline)
(display (pop-count 23451449)) (newline)

(define (pop-count n)
  (let loop ((n n) (count 0))
    (if (zero? n) count
      (loop (logand n (- n 1)) (+ count 1)))))

(display (pop-count 23)) (newline)
(display (pop-count 23451449)) (newline)

(define (pop-count n)
  (let ((count n))
    (set! count (- count (logand (ash n -1) #o33333333333)))
    (set! count (- count (logand (ash n -2) #o11111111111)))
    (set! count (logand (+ count (ash count -3)) #o30707070707))
    (modulo count 63)))

(display (pop-count 23)) (newline)
(display (pop-count 23451449)) (newline)

4
15
4
15
4
15
4
15