## Translating HAKMEM 175 into C…

September 8, 2010 | Checkers, Computer Science | By: Mark VandeWettering

A couple of years back, I made note of HAKMEM 175, a nifty hack by Bill Gosper that finds the next higher value that has the same number of ‘1’ bits as the input.

If I bothered to convert it to C, I didn’t scribble it down, so I thought I’d do it here.

```#include <stdio.h>

/*  _  _   _   _  ____  __ ___ __  __ _ ____ ___
* | || | /_\ | |/ /  \/  | __|  \/  / |__  | __|
* | __ |/ _ \| ' <| |\/| | _|| |\/| | | / /|__ \
* |_||_/_/ \_\_|\_\_|  |_|___|_|  |_|_|/_/ |___/
*
* A straightforward implementation of Gosper's algorithm for
* determining the next higher value which has the same number of 1
* bits. This is useful for enumerating subsets.
*
* Translated by Mark VandeWettering.
*/

unsigned int hakmem175(unsigned int A) { unsigned int B, C, D ;

B = A ;                     /* MOVE B, A */
C = -B ;                    /* MOVN C, B */
C &= B ;                    /* AND C, B */
A += C ;                    /* ADD A, C */
D = A ;                     /* MOVE D, A */
D ^= B ;                    /* XOR D, B */
D >>= 2 ;                   /* LSH D, -2 */
D /= C ;                    /* IDIVM D, C */
A |= D ;                    /* IOR A, C typo? */
return A ;
}

main()
{
unsigned int x ;
int i ;

x = 3 ;

do {
printf("0x%x\n", x) ;
x = hakmem175(x) ;
} while (x != 0) ;
}
```

I was surprised to find that there is actually a bug in the published memo. The last instruction should obviously be an OR of A and D, not A and C as listed in the published memo. After discovering the error, I seeked to find mention of it onlne somewhere. This page lists the corrected PDP-10 assembly code without comment. It also suggests a couple of optimizations: you can save one register and one instruction by variable renaming, and with a bit of work, you can avoid the integer divide, which is probably a good thing on pretty much any architecture you are likely to use.

Addendum: I thought it might be fun to show an illustration of how this could be used. At one point, while writing my checkers program, I thought about enumerating all possible positions with given numbers of checkers on each side. Counting them is actually rather easy, but enumerating them is a bit trickier, but using the trick of HAKMEM175, it becomes somewhat easier.

```#include <stdio.h>
#include <stdlib.h>

unsigned int
hakmem175 (unsigned int A)
{
unsigned int B, C, D;

B = A;                      /* MOVE B, A */
C = -B;                     /* MOVN C, B */
C &= B;                     /* AND C, B */
A += C;                     /* ADD A, C */
D = A;                      /* MOVE D, A */
D ^= B;                     /* XOR D, B */
D >>= 2;                    /* LSH D, -2 */
D /= C;                     /* IDIVM D, C */
A |= D;                     /* IOR A, C typo? */
return A;
}

/*
* Here's an interesting use (okay, semi-interesting use) of the
* above function.  Let's use it to enumerate all the potential
* positions in checkers which have two checkers (not kings) for
* each side.
*/

#define WHITEILLEGAL    (0x0000000F)
#define BLACKILLEGAL    (0xF0000000)

int
main (int argc, char *argv[])
{
unsigned int B, W;

int nb = atoi (argv[1]);

int nw = atoi (argv[2]);

if (nb < 1 || nb > 12 || nw < 1 || nw > 12) {
fprintf (stderr, "usage: checkers nb nw\n");
fprintf (stderr, "       1 <= nb, nw <= 12\n");
exit (-1);
}

B = (1 << nb) - 1;

for (;;) {
W = (1 << nw) - 1;
for (;;) {
while (W != 0 && (W & (B | WHITEILLEGAL)))
W = hakmem175 (W);
if (W == 0)
break;
/* output B, W, we could be prettier */
printf ("%x %x\n", B, W);
W = hakmem175 (W);
}
B = hakmem175 (B);
while (B != 0 && (B & BLACKILLEGAL))
B = hakmem175 (B);
if (B == 0)
break;
}

return 0;
}
```

Using this, you can easily enumerate the 125,664 positions with 2 checkers on each side, the 8,127,272 positions with 3 checkers on each side, and the 253,782,115 positions with 4 checkers on each side. By then, the code gets a little slow: it has to step over all the positions where there is a conflict in B and W placement, so it gets pretty slow. Still, it works reasonably well, and as such, might serve as part of the inner loop of a retrograde endgame analysis project.