HAKMEM 175

September 8, 2009 | General | By: Mark VandeWettering

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.

Comments

Comment from Pseudonym
Time 9/8/2009 at 11:32 pm

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.