Canonical Voices

Posts tagged with 'software engineering'

David Owen

Let's say that you've got a lot of numbers that represent bitmasks of some kind, and you want to count how many times each bit is on or off across the entire set.  Maybe you're analyzing game positions represented as bitboards for an AI, or trying to find certain types of weaknesses in random-number generators, like in Forge (a successor to crypto-js) or Cryptocat (read the great write-up at Sophos).

So, you write some very straight-forward code to count the bits.  It grabs one bitmask.  If the lowest-order bit is set, it increments the counter for that bit position.  Then, it right-shifts the bitmask and moves to the counter for the next bit.  Repeat that for each bit in the mask, then repeat that for each bitmask:

const int N = 1000000;
unsigned long x[N]; // Assuming sizeof(unsigned long) == 8, or 64 bits.
int counts[64] = {0};

void count_simple(void) {
    for(int i = 0; i < N; i++) {
        int j = 0;
        while(x[i] != 0) {
            counts[j] += x[i] & 1;
            x[i] >>= 1;
            ++j;
        }
    }
}

You run your program, and it works correctly, but it's too slow.  I'll show you how to speed this up.  The technique, which applies to languages like Python or Javascript as well as to C, is both crazy, and crazy-fast!

Continue reading "A crazy fast bit-counting technique"

Read more
David Owen

Working with wrap-around

Sometimes we need to work with numbers that wrap-around, such as angles or indexes into a circular array. There are some tricks for dealing with these cases. Continue reading "Working with wrap-around"

Read more
David Owen

A circular sector is the part of a circle bounded by two radii and an arc connecting them. Determining whether a point lies in a sector is not quite as easy as rectangular bounds-checking. There are a few different approaches: θ-comparison, line-sides, and dot-products. Continue reading "Bounds-checking with a circular sector"

Read more