This pages shows matrix illustrations with indexes in binary
numbers. Each bit in a binary integer represents a power of two which
can be present or absent. This is how index values live in a computer.
There is all kinds of bitwise operations and manipulations that
you can do on integers. Such operations are elementary and fast. So you
can save a nanosecond here and there. (After spending precious hours to
find out how).
Although matrices for transform can theoretically have any number
NxN, choosing a power of two for N tends to simplify implementations.
Below, an 8x8 matrix is sketched with indexes in binary numbers. As
indexing generally starts with 0, 7 is the highest value and only 3
bits are used to represent the indexes. The most significant bit points
to the
four
quarters of the matrix:
The secondmost significant bit points to squares at a finer level
of resolution:
This pattern is continued till the finest resolution level.
I want to illustrate a frequently used example of bitwise manipulation. Say we multiply row indexes by column indexes like it is done to find the powers for W^{kn} of the Fourier matrix. Below is an example matrix for N=8. Only three bits are of concern. When we mask the more significant bits that are in a datatype, we see only the 'remainder' as it would show up after modulo N division. For example, binary 111*110=101010. The three least significant bits are: 010. And 7*6 modulo 8 is 2 indeed. Masking bits is a very easy operation, using a bitwiseand with N1. Computing a modulo N division for N not being a power of two is much more complicated.
When working on radix 2 bitreversal methods, I spotted the
'notidentitydiagonal', perpendicular to the identity diagonal. On
this
diagonal, the column index is the (masked) bitwise negation of the row
index. For N=2^{x}, a bitwise negation of n is always N1n,
and the notIdiagonal divides the matrix in two triangular halves. The
masked negation of n can also be found with an exclusiveor operation
with the mask itself. The effect of
exclusiveor with the mask N1 is to flip the status of all bits.
Example for N=8:
100 (binary 4)
111 (binary mask N1=7)
 (x or these values)
011 (result is binary 3)
The values 4 and 3 are additive complements within 7. In general, n
and (n^N1) are additive complements within N1 for N being a power of
2. The ^ character is the C syntax for the exclusiveor operation.
Bitwisenegated entries in a square N=2^{x} matrix appear systematically as pairs rotated over 180 degrees. Here is the notIdiagonal, and an example of such a pair:
I am still in the process of discovering ways to employ bitwise
negation. Examples are on the pages Bit Reversal and Inverse FFT.
It is sometimes useful to scan the status of a specific bit in an
indexnumber n. This can be done by using a bitwiseand operation
(bitmask). For the plot
below, I scanned the six bits in indexes n from 0 to 63, by running
over all n six times with a different mask:
n &= 1;
n &= 2;
n &= 4;
n &= 8;
n &= 16;
n &= 32;
I found that
visualisations like this help me in finding solutions. When gazing
at the above figure, I spotted a method for iterating over the odd
blocks of specific resolution, without branching. For example, if I
whish to iterate (incrementing) over the dark blue blocks in the above
illustration and skip the inbetween values, I can simply add the
following in C:
n = 8;
The bit representing 8 or 2^{3} will always be set by the
inclusiveor, so values without this bit set are excluded from the
sequence. In a decrementing sequence this would result in an infinite
loop.
An interesting sequence is formed by the isolated least significant
set bits that are in a natural binary series. It is a series of pure
powers of two. I have plotted their
values:
A very simple routine exist, to extract this least significant set
bit
from a bit pattern. I have learnt this from
topcoder.com, see http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation.
The C code for this could be: extracted_value = n & ~(n1);
Simple as it may be, I like to do an illustration of these
operations.
Subtracting 1 from n clears
the least significant set bit in n, and it sets all less significant
bits high. In the example that happens with the least significant
bit. Of n1, all bits should be inverted with bitwisenot, which is
written ~ in C. For the example, it is ~13. 
And the next step:
~13 is 4294967282 when using a 32 bits unsigned integer datatype. It is also (2^{32})113.

It is also possible, and sometimes more convenient, to have the base
2 logarithms of the
above sketched values. Such logarithms happen to
coincide with the number of 'trailing zero's' that predece the first
set bit. For example:
001000 is decimal 8 and has 3 trailing zero's
the base 2 log of 8 is 3
That pattern of trailing zero's in a natural series is plotted here:
Trailing zero's must be counted somehow. There is no ANSI C
operator for this. Some processors have an instruction for it. But
counting zero's with a loop is also quite efficient. Odd numbers have
no trailing zero's so you may skip counting that. How many trailing
zero's are there in total, for a given series N=2^{x}? I think
N1 trailing zero's theoretically, but the zero's of zero must not be
counted because these do not trail anything. Moreover, the zero's in
zero would dramatically spoil the intention of your routine. Here is an
example for N=8:
000 do not try to count the trailing zero's in zero!
001
010 1 trailing zero
011
100 2 trailing zero's
101
110 1 trailing zero
111
It is easier to count ones than zero's, therefore I negate the value
of n bitwise before starting such a loop. The counting must continue
while notn&1 (bitwiseand) is true. In C code:
for(zeros=0; notn&1; zeros++) 
There is more ways to implement this, I picked the following one from the page 'Bit Twiddling Hacks' by Sean Eron Anderson:

With the pattern of extracted powers of two, yet another interesting
pattern can be created: a socalled Gray code sequence. Start with an
arrayvariable initialised at zero and toggleswitch the bits of it one
by one, doing exclusiveor with the extracted powers of two. Iterating
over n, this could be done with the snippet from Topcoder that I
illustrated earlier:
for(n=1; n<N; n++) 
If a Gray code sequence is plotted as output values, the pattern
shows no clear
symmetry. But I was quite surprised by the individualbitspattern of
it:
Here is the natural sequence once more, for reference:
So far I have plotted quite some bit patterns, but what is the use
of it all? To be honest, I don't know. That is, I am still in the
process of exploring. You can find applications for the above mentioned
patterns on my FFT pages. That is all I have at the moment. I
documented the plots and codebits so I can stare at them every now and
than. Soon as I have more, this page will be updated.