🚀 go-pugleaf

Richard A. O'Keefe (ok@cs.rmit.edu.au) wrote:
: [ bitset operations ]

: Note the following trick for walking through an array of unsigned longs,
: processing each bit.  It assumes that each bit in the array is used.

: 	void walk_bits_in_ulongs(
: 	    unsigned long const *base,
: 	    unsigned             nwords,
: 	    void (*f)(unsigned /*bitno*/, int /*bit*/)
: 	) {
: 	    unsigned bitno;
: 	    unsigned i;

: 	    for (bitno = 0, i = 0; i < nwords; i++) {
: 		unsigned long const word = base[i];
: 		unsigned long mask;

>>>             if (!word) continue;

: 		for (mask = 1; mask != 0; mask <<= 1, bitno++)
: 		    f(bitno, (word & mask) != 0);
: 	    }
: 	}

: Again, the saving comes about because we are NOT fetching bits in a
: true ELEMENT-WISE fashion, but in groups.

The above trick inserted (>>>) is a good one to remember when working
with bitsets.  On many CPUs, the above check is essentially 'free',
since it just depends on a condition flag that gets set when the value
is loaded anyway.

Intersection and union, of course, are very efficient (just use & and
|) in terms of bitsets.

Of course, you can do even better than that.  I timed a similar
algorithm on a wide variety of architectures, and the following
algorithm won for finding the set bit in a bitfield (or giving an
error if more than one is set):

static int get_single(unsigned int *, bv) {
    int i, res = -1;

    for (i = 0; i < NUM_BITVEC_INTS; i++) {
        if (bv[i]) { /* test 16 bits at a time! */
            if (res != -1) return -1;
	    res = i;
        }
    }
    if (res == -1) return res;

    i = bv[res];
    /* Binary search for the set bit, unrolled for speed. */
    if (i & 0x0000ffff) {
        if (i & 0xffff0000)
            return -1;
    } else {
        i >>= 16;
        res += 16;
    }

    if (i & 0x00ff) {
        if (i & 0xff00)
            return -1;
    } else {
        i >>= 8;
        res += 8;
    }
    
    if (i & 0x0f) {
        if (i & 0xf0)
            return -1;
    } else {
        i >>= 4;
        res += 4;
    }
    
    if (i & 0x3) {
        if (i & 0xc)
            return -1;
    } else {
        i >>= 2;
        res += 2;
    }
    
    if (i & 0x1) {
        if (i & 0x2)
            return -1;
	return res;
    } else {
        return res + 1;
    }
}

If you're wondering why the shifts are there, remember shifts are
cheap, and it turns out the full 32 bit integer constants (like
0xaaaaaaaa) appear to be rather slow on many RISC CPUs, so it's faster
to reduce the problem to one involving smaller constants.

Similar tricks for counting bits exist; I think the C FAQ has some of them.

---------------------------------------------------------------------------
Tim Hollebeek         | Disclaimer :=> Everything above is a true statement,
Electron Psychologist |                for sufficiently false values of true.
Princeton University  | email: tim@wfn-shop.princeton.edu
----------------------| http://wfn-shop.princeton.edu/~tim (NEW! IMPROVED!)