;; ---- (count-1.lisp) ----------------------------------------------------

(defun count-1-bits/optimized (n &aux (bits 0))
  (declare (optimize (speed 3) (debug 0))
           (type (and unsigned-byte fixnum) bits)
           (type unsigned-byte n))
  (if (typep n 'fixnum)
      (locally
          (declare (type fixnum n))
        (loop :while (plusp n) :do
          (when (oddp n)
            (incf bits))
          (setf n (ash n -1))))
      (loop :while (plusp n) :do
        (when (oddp n)
          (incf bits))
        (setf n (ash n -1))))
  bits)


(defun count-1-bits/not-optimized (n)
  (check-type n unsigned-byte)
  (labels ((count-bits (n)
             (if (< n 256)
                 (aref #.(coerce (loop
                                   :for n :below 256
                                   :collect (loop :for i :below 8 :when (logbitp i n) :sum 1))
                                 'vector)
                       n)
                 (let ((divisor (max (truncate (log (integer-length n) 2) 2)
                                     256)))
                   (multiple-value-bind (left right)  (truncate n divisor)
                     (+ (count-bits left)
                        (count-bits right)))))))
    (count-bits n)))

(defun test ()
  (loop
    :with sa := 0
    :with sb := 0
    :with rep := 20
    :repeat rep
    :do (let ((n (random (expt 2 4096))))
          (let* ((a)
                 (b)
                 (ta (com.informatimago.common-lisp.cesarum.time:chrono-run-time
                       (setf a (count-1-bits/optimized n))))
                 (tb (com.informatimago.common-lisp.cesarum.time:chrono-run-time
                       (setf b (count-1-bits/not-optimized n)))))
            (assert (= a b))
            (incf sa ta)
            (incf sb tb)))
    :finally (format t "~&average optimized     = ~,9f~%average non-optimized = ~,9f~%"
                     (/ sa rep) (/ sb rep))))

;; ------------------------------------------------------------------------
#|


cl-user> (load (compile-file #P"~/Desktop/lisp/count-1.lisp"))
#P"/Users/pjb/Desktop/lisp/count-1.dx64fsl"
cl-user> (test)
average optimized     = 0.002871750
average non-optimized = 0.000687450
nil
cl-user> (test)
average optimized     = 0.002862700
average non-optimized = 0.000653150
nil
cl-user> (test)
average optimized     = 0.002799100
average non-optimized = 0.000717150
nil
cl-user> (test)
average optimized     = 0.002888150
average non-optimized = 0.000745800
nil
cl-user> (test)
average optimized     = 0.002842350
average non-optimized = 0.000666450
nil
cl-user> (test)
average optimized     = 0.002860200
average non-optimized = 0.000701350
nil

|#