HAKMEM 175

HAKMEM is a legendary technical memo from MIT that’s packed full of interesting bits. On this occasion, I ran across item #175, which you can find here:

HAKMEM 175

This is a little chunk of code which given an integer, computes the next highest integer with the same number of one bits. This code is expressed somewhat sub-optimally for modern audiences, since it is PDP-10 assembly code, but encompasses a neat, but subtle algorithm. One might ask what use such a seemingly esoteric function is, but it is quite useful in quickly generating all subsets with a given number of elements. Nifty.

One thought on “HAKMEM 175

  1. Pseudonym

    Here’s a related function which is quite useful to know about:

    // B[i] = ith bit
    // u = number of ones in B
    // t = length of B
    int enumCode(bool b[], int u, int t)
    {
    int x = 0;
    for (int i = 0; i < t; ++i)
    {
    if (B[i])
    {
    x += choose(t-i-1, u); // Binomial coefficient
    –u;
    }
    }
    return x;
    }

    enumCode(B,u,t) is the index of B in the lexicographically ordered sequence of all bitmaps with u bits set. This has applications in succinct data structures, because it is an entropy coded representation of B.

Comments are closed.