Project HAKMEM [Oldschool MIT]

Hard problems for real nerds (like me) :-D

Project HAKMEM [Oldschool MIT]
inwap.com

Brilliant book, picked it up not long ago. So far, my favorite thing I have learned is on page 14 - the snoob function.

Snoob stands for "same number of one bits". Essentially, if x is an integer whose binary representation contains n one-bits, snoob(x) will return the next smallest integer which is also represented using n one-bits. The obvious application here is iterating through all subsets of a certain size. The function is as follows:

unsigned int snoob(unsigned int x) {

    unsigned int smallest, ripple, ones = 0;

    smallest = x & -x;

    ripple = x + smallest;

    ones = x ^ ripple;

    ones = (ones >> 2) / smallest;

    return ripple | ones;

}

Given a set containing N elements, to generate all subsets of size K you initialize a bitmask to (1 (Disclaimer: Although neat, I've never found a use for this outside of programming competitions)