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 `defun`

, not `defmath`

.
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 `defmath`

uses.

The `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 `n`

,
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.

Go to the first, previous, next, last section, table of contents.