🚀 go-pugleaf

RE: Subject: Clever programming tricks wanted

Greg Wilson of Edinburgh Concurrent Supercomputer Project writes..

> I'm looking for "clever" programming tricks.  For example,
> ...
> I would like to hear about similar tricks that people have invented/
> discovered.  In particular, I'm looking for fast ways to count the
> number of 1 bits in a word (on machines that don't have this as a
> machine instruction :-), ....

Bit counting.

This Occam function *bitcount* takes any sized array of integers, and
returns the number of bits set in the array.
The algorithm is particularly effective for counting
the bits in a sparse array.

-- occam program *bitcount*. 18/1/89
-- Steven Ericsson Zenith: Architecture Group
-- INMOS Limited, Bristol, UK.
#USE userio

INT FUNCTION bitcount (VAL []INT array)
  INT count :
  VALOF
    SEQ
      count := 0
      INT x :
      SEQ i = 0 FOR SIZE array
        SEQ
          x := array[i]
          WHILE x <> 0
            SEQ
              x := x /\ (x MINUS 1)
              count := count + 1
    RESULT count
:

[10]INT array :
SEQ
  -- first input an array of ten integers
  INT char, num :
  SEQ i = 0 FOR 10
    SEQ
      write.int         (screen, i, 5)
      write.full.string (screen, " #")
      read.echo.char    (keyboard, screen, char)
      read.echo.hex.int (keyboard, screen, num, char)
      array[i] := num
  -- count bits in array and write result to the screen
  newline           (screen)
  write.full.string (screen, "Set bits counted in above array = ")
  write.hex.int     (screen, bitcount (array), 8)
  -- wait for any key press
  INT any:
  keyboard ? any

It would is a simple matter to add timers here to time the *bitcount*
function, we could even look at the code generation if you like.

The key to the algorithm lies in the expression (x /\ (x MINUS 1)).
David May brought this to my attention some time ago, I forget to
whom he attributed the original observation. Look at what happens.
Take a value, subtract 1 (ignoring overflow), and BITAND it with
the original value. Each time we do this we cause one bit to disappear.
When the value equals zero we have counted each set bit.


-- 
 *  Steven Ericsson Zenith     Snail mail: INMOS Limited, 1000 Aztec West,
 |    zenith@inmos.uucp                    Almondsbury, Bristol BS12 4SQ. UK.
      zenith@inmos.co.uk                   Voice: (UK)0454 616616x513
      ** All can know beauty as beauty only because there is ugliness **