zenith@inmos.co.uk (Steven Zenith) (01/19/89)
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 **