Project HAKMEM [Oldschool MIT](inwap.com)
inwap.com
Project HAKMEM [Oldschool MIT]
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
Hard problems for real nerds (like me) :-D
2 comments
See also: http://www.hackersdelight.org/
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) {
Given a set containing N elements, to generate all subsets of size K you initialize a bitmask to (1 << K) - 1 then perform a snoob N Choose K times to get all the bitmasks you need.
(Disclaimer: Although neat, I've never found a use for this outside of programming competitions)
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,
smallest = x & -x;
ripple = x + smallest;
^ ripple;
>> 2) / smallest;
return ripple | ones;
Given a set containing N elements, to generate all subsets of size K you initialize a bitmask to (1 << K) - 1 then perform a snoob N Choose K times to get all the bitmasks you need.
(Disclaimer: Although neat, I've never found a use for this outside of programming competitions)