The other day a person named Glenn Slayden sent me a new hack for my bithacks page as well as a correction. The correction was for finding the log base 2 of an N-bit integer in O(lg(N)) operations where the number is known to be a power of 2 (special case below). Some months ago I had optimized the array of constants for the general code above, but forgot to keep the constants for the special case code below, which caused it to fail. It is fixed now. The new hack is for conditionally setting or clearing bits in a word. Suppose you want to set bits, defined by mask m, in a word, w, if flag f is true; if flag f is false you want to clear the bits in w that are defined in m. The hack is to do this without branching: w ^= (-f ^ w) & m. This seems to involve more operations than the branching version: if (f) w |= m; else w &= m. Yet, I did some speed tests on an Athlon XP 2100+ using g++ -O3, and sure enough it does provide a 5-10% improvement.
Posted by seander at December 14, 2003 02:25 PM