Calc does not include a built-in function for counting the number of “one” bits in a binary integer. It’s easy to invent one using b u to convert the integer to a set, and V # to count the elements of that set; let’s write a function that counts the bits without having to create an intermediate set.
(defmath bcount ((natnum n)) (interactive 1 "bcnt") (let ((count 0)) (while (> n 0) (if (oddp n) (setq count (1+ count))) (setq n (lsh n -1))) count))
When this is expanded by
defmath, it will become the following
Emacs Lisp function:
(defun calcFunc-bcount (n) (setq n (math-check-natnum n)) (let ((count 0)) (while (math-posp n) (if (math-oddp n) (setq count (math-add count 1))) (setq n (calcFunc-lsh n -1))) count))
If the input numbers are large, this function involves a fair amount of arithmetic. A binary right shift is essentially a division by two; recall that Calc stores integers in decimal form so bit shifts must involve actual division.
To gain a bit more efficiency, we could divide the integer into n-bit chunks, each of which can be handled quickly because they fit into Lisp integers. It turns out that Calc’s arithmetic routines are especially fast when dividing by an integer less than 1000, so we can set n = 9 bits and use repeated division by 512:
(defmath bcount ((natnum n)) (interactive 1 "bcnt") (let ((count 0)) (while (not (fixnump n)) (let ((qr (idivmod n 512))) (setq count (+ count (bcount-fixnum (cdr qr))) n (car qr)))) (+ count (bcount-fixnum n)))) (defun bcount-fixnum (n) (let ((count 0)) (while (> n 0) (setq count (+ count (logand n 1)) n (lsh n -1))) count))
Note that the second function uses
Because this function deals only with native Lisp integers (“fixnums”),
it can use the actual Emacs
+ and related functions rather
than the slower but more general Calc equivalents which
idivmod function does an integer division, returning both
the quotient and the remainder at once. Again, note that while it
might seem that ‘(logand n 511)’ and ‘(lsh n -9)’ are
more efficient ways to split off the bottom nine bits of
actually they are less efficient because each operation is really
a division by 512 in disguise;
idivmod allows us to do the
same thing with a single division by 512.