Info Catalog calc: Example Definitions calc: Example Definitions calc: Sine Example

calc: Bit Counting Example

 
 18.5.5.1 Bit-Counting
 .....................
 
 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.
 

Info Catalog calc: Example Definitions calc: Example Definitions calc: Sine Example