Path: utzoo!utgpu!watmath!clyde!att!osu-cis!killer!ames!mailrus!uflorida!gatech!hubcap!MOBY
From: mcvax!etive.ed.ac.uk!gvw@uunet.UU.NET (MOBY)
Newsgroups: comp.parallel
Subject: Clever programming tricks wanted
Message-ID: <4061@hubcap.UUCP>
Date: 11 Jan 89 13:10:26 GMT
Sender: fpst@hubcap.UUCP
Followup-To: comp.lang.misc (please)
Lines: 35
Approved: parallel@hubcap.clemson.edu

I'm looking for "clever" programming tricks.  For example,
consider the following problem:

    Given a computer word W in which one or more bits are set,
    change the lowest set bit from 1 to 0, and set the corresponding
    bit in another word B to 1.  Eg. if the input is W = 0x0860,
    return W' = 0x0840 and B' = 0x0020.

The obvious technique uses shifting and a bit mask.  A much slicker
approach is:

    Procedure getNextBit( W, B )
      W, B : Integer
    {
      B := W
      W := W MINUS 1    -- modulo minus (i.e., ignore overflow)
      W := W AND B      -- bit-wise AND
      B := B XOR W      -- bit-wise XOR
    }

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 :-), and trying to find a description of a
mythical technique for creating doubly-linked lists using single
pointers and XOR operations.

Please send all correspondence to comp.lang.misc, or directly to
me (gvw@uk.ac.ed.etive).

Cheers,

Greg Wilson
-- 
Edinburgh Concurrent Supercomputer Project