Excerpts:
s2 = sqrt(2)/2; k = 0; i1 = 1 << i; // i1 = 0...010...0, i'th bit = 1 while( k < n) // k will have i'th bit = 0, k1 will have i'th bit = 1 { k1 = k | i1; t0 = q[k]; t1 = q[k1]; q[k] = s2*(t0+t1); q[k1] = s2*(t0-t1); ++k; k += (k & i1); // skip k values with i'th bit = 1 }