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
}