The Estimable Item 175

Here are some more recreations suggested by reading TAoCP Fascicle 4.1. This is a wonderful little book, reasonably priced and deserving of a place on every computer programmer’s bookshelf.

This example illustrates a famous “Gosper hack.” There is apparently some controversy over which Gosper hack merits the title THE Gosper hack. Often that title goes to MIT A.I. Laboratory HAKMEM Item 145. The code below is based on Gosper hack 175 from the same document, which is the one Knuth mentions.

The example below contains a series of experiments which should make it increasingly obvious what the Gosper function 175 computes. In case that’s not enough, another function in the same general class is also illustrated.

(Presented “as-is” and without warranty or implied fitness; use at your own risk.)

// HAKMEM Item 175 (Gosper) 
let g175 x = 
  let u = x &&& -x
  let v = x + u
  v + (((v^^^x)/u)>>>2)
  
  
// Some tests.

// x of 1 to 32.
let l0 = List.map (fun x->(x,(g175 x))) [1..32]


// Unfold x from 1 to <64.
let l1 = 
  Seq.toList(
    Seq.unfold (
      fun s -> 
        if s>=64 
          then None 
          else Some(s,(g175 s))) 
      1)


// Unfold x from 0x1f to <64.
let l2 = 
  Seq.toList(
    Seq.unfold (
      fun s -> 
        if s>=64 
          then None 
          else Some(s,(g175 s))) 
      0x1f)


// Hideously overly complex binary formatter
// just for the fun of it.
let binaryFmt =
  let rec binaryFmt0 f b =
    match b with 
    | 0 -> f("")
    | _ -> 
        match (b&&&1) with 
        | 0 -> binaryFmt0 (fun s -> s+f("0")) (b/2)
        | _ -> binaryFmt0 (fun s -> s+f("1")) (b/2)
  binaryFmt0 (fun s->s)    


// Unfold x from 7 to <64.
// Results in binary.
let l3 = 
  Seq.toList(
    Seq.unfold (
      fun s -> 
        if s>=64 
          then None 
          else Some((binaryFmt s),(g175 s))) 
      7)
      

// Another function in 
// the same general class.      
let ee n =
  let u = n&&&(-n)
  ((binaryFmt (n/u)),u)


// x from 1 to 64.
let l4 = List.map (fun n->ee n) [1..64]


printf "Your breakpoint here."

Bit Operations from TAoCP in F#

In the interest of keeping the blog active in the midst of tax time, dragging out the bit theme a bit longer, etc., here the bit enumerators based on Dr. Knuth's TAoCP (Fascicle 4.1) in F#. My earlier C# posts on this can be found here and here.

(Presented “as-is” and without warranty or implied fitness; use at your own risk.)

// Enumerate the bits in an integer.
let rec bits n = seq {
  match n with 
  | 0 -> ()
  | _ -> 
    let b = n&&&(-n)
    yield b
    yield! bits (n&&&(~~~b))
}


// Enumerate the power set of the bits in
// an integer, including the null set.
let powerSet = 
  let rec powerSet0 s n = seq {  
    yield s 
    match (s=n) with 
    | true -> ()
    | _ -> yield! powerSet0 ((s-n)&&&n) n
  }
  powerSet0 0
  

// Test.
let x0 = Seq.toList (bits 0xDD)
let x1 = Seq.toList (powerSet 5)
let x2 = Seq.toList (powerSet 0xDD)
let x3 = Seq.toList (powerSet 7)

printf "Your breakpoint here."

Enumerating Bits

OK, so the enumerating the set of subsets of non-zero bits is not a common task. But what about enumerating the set of non-zero bits in an integer? That’s something that tends to happen at least one or twice in any large project. Here’s how that can be done use a related function.

Given an integer (i), the least significant non-zero bit (b) can be found using this equation:

b = (i & -i)

(This is discussed as equation (37) in Donald Knuth’s The Art of Computer Programming, Volume 4, pre-fascicle 1A, page 8.)

It is easy to turn this into a loop which enumerates the bits in an integer:

while (xInteger>0)
{
  int xBit = (xInteger & -xInteger);
  xInteger &= ~xBit;
  // Do something with xBit here.
}

(This is probably a case where one wouldn’t want to use a generic “yield return” enumerator, since if one is working at this level of detail, efficiency is probably the main concern.)

This can also be made to work in C# with unsigned integers by using various types of casting. But if efficiency is paramount, pay attention to the generated MSIL, since casting at some points generates more efficient code than does casting at other points.

Tests in release mode show that this construct is nearly four times faster in C# (.NET 3.5 version) than is shifting! But it looks arcane at first glance, so be sure to document the code well.

Power Set of a Bitmask

Here’s a cute trick for enumerating the power set of an integer bitmask. It’s based on equation (84) in Donald Knuth’s The Art of Computer Programming, Volume 4, pre-fascicle 1A, page 18, available in an "alpha test" version at:

http://www-cs-faculty.stanford.edu/~knuth/taocp.html

The idea is that, given a subset (x) of a mask (M) the next largest lexicographic subset (x') is:

x’ = (x – M) & M

Combined with the C# "yield return" statement, this allows a simple enumeration of the power set of a mask. You simply seed the subset with zero, and iterate until it is once again zero.

public static IEnumerable<int> PowerSet (
  int maskIn)
{
  int xSet = 0;
      
  do 
  {
    yield return xSet;
    xSet = (xSet - maskIn) & maskIn;
  } 
  while (xSet!=0);
}

For example, calling PowerSet(0x19) returns an enumerator which yields (in binary):

00000
00001
01000
01001
10000
10001
11000
11001

I can’t think of a specific use for it right off hand, but if a project uses enough bit manipulation, I’m sure something would arise.