Counting bits using masks (riddle)

Newsgroups	comp.lang.forth
From	Albert van der Horst <albert@spenarnc.xs4all.nl>
Subject	Counting bits using masks (riddle)
Date	2012-07-03 21:27 +0000
Message-ID	<m6lsx7.2m9@spenarnc.xs4all.nl> (permalink)
Organization	Dutch Forth Workshop

Show all headers | View raw

The following is a fairly well known to count the bits in a word faster
than with shifts:

HEX
: COUNT-BITS   ( u -- n )
   DUP 05555555555555555 AND SWAP 1 RSHIFT 05555555555555555 AND +
   DUP 03333333333333333 AND SWAP 2 RSHIFT 03333333333333333 AND +
   DUP 00F0F0F0F0F0F0F0F AND SWAP 4 RSHIFT 00F0F0F0F0F0F0F0F AND +
   0FF MOD ;
DECIMAL

We can save one AND operation.
How?

Groetjes Albert

--
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

Back to comp.lang.forth | Previous | Next — Next in thread | Find similar

Thread

Counting bits using masks (riddle) Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-07-03 21:27 +0000
  Re: Counting bits using masks (riddle) "A. K." <akk@nospam.org> - 2012-07-03 23:51 +0200
  Re: Counting bits using masks (riddle) Pablo Hugo Reda <pabloreda@gmail.com> - 2012-07-03 15:38 -0700
    Re: Counting bits using masks (riddle) Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-07-04 11:14 +0000
      Re: Counting bits using masks (riddle) Alex McDonald <blog@rivadpm.com> - 2012-07-04 04:26 -0700
        Re: Counting bits using masks (riddle) mhx@iae.nl (Marcel Hendrix) - 2012-07-04 19:30 +0200
          Re: Counting bits using masks (riddle) Alex McDonald <blog@rivadpm.com> - 2012-07-04 12:44 -0700
  Re: Counting bits using masks (riddle) Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-07-04 11:40 +0000
  Re: Counting bits using masks (riddle) Mark Wills <markrobertwills@yahoo.co.uk> - 2012-07-04 14:03 -0700

csiph-web