Explanation about rotating a bitmap by 90°

Question

I recently found that SO question.

The accepted answer and the answer made by Rhubbarb works fine, but I don't understand how they work. And I don't want to use code that I don't understand in my project. I know what the basics bit operations are (shifts, ANDs , ORs etc..), but I don't understand how these assembly of operations end up doing what they're doing .

Thank you for looking at this question and hopefully be able to help me.

Answer 1

The 64 bit integer value is represented as an 8-by-8 block - let's pretend we'd understand the "content" of each cell as follows:

 1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

although value is actually stored sequentially as

 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...

We also say that shifting it to the left by four (value << 4) results in

  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 ...

or

  5  6  7  8  9 10 11 12 
 13 14 15 16 17 18 19 20 ...

and shifting it to the right by four (value >> 4) gives

  0  0  0  0  1  2  3  4  
  5  6  7  8  9 10 11 12 ...

Now let's take

uint64 reflect_vert (uint64 value)
{
    value = ((value & 0xFFFFFFFF00000000ull) >> 32) | ((value & 0x00000000FFFFFFFFull) << 32);
    value = ((value & 0xFFFF0000FFFF0000ull) >> 16) | ((value & 0x0000FFFF0000FFFFull) << 16);
    value = ((value & 0xFF00FF00FF00FF00ull) >>  8) | ((value & 0x00FF00FF00FF00FFull) <<  8);
    return value;
}

Here, the 0xFFFFFFFF00000000ull-like pieces are bit masks which, in combination with the AND operation, select bits from value. Also note that 0xFF corresponds to one byte with eight bits set, so 0xFFFFFFFF effectively describes 4*8=32 selected bits. Since each row is 8 bits long, this corresponds to 4 rows.

Concretely, value & 0xFFFFFFFF00000000ull selects (keeps!) the upper 32 bits of value, i.e. the first four rows, and discards the rest, while value & 0x00000000FFFFFFFFull selects the lower 32 bits and discards the first. (It does not actually discard anything, but rather sets the value of those elements/positions that do not match to zero.)

The shifts operations in

((value & 0xFFFFFFFF00000000ull) >> 32)
((value & 0x00000000FFFFFFFFull) << 32)

then move these bits either downwards (>> 32) onto the location of the lower 32 bits or upwards (<< 32). By OR-ing them together,

value = ((value & 0xFFFFFFFF00000000ull) >> 32) | ((value & 0x00000000FFFFFFFFull) << 32);

you have effectively swapped them. Now since the lower 32 bits correspond to the "bottom half" of the block, we just swapped the rows like so:

33 34 35 36 37 38 39 40 \
41 42 43 44 45 46 47 48 |__
49 50 51 52 53 54 55 56 |  |
57 58 59 60 61 62 63 64 /  |
 1  2  3  4  5  6  7  8 \  |
 9 10 11 12 13 14 15 16 |__|
17 18 19 20 21 22 23 24 |
25 26 27 28 29 30 31 32 /

Performing the same with 0xFFFF0000FFFF0000ull and 0x0000FFFF0000FFFFull, using shifts of width 16 swaps two rows each with their neighbors:

49 50 51 52 53 54 55 56 \__
57 58 59 60 61 62 63 64 /  |
33 34 35 36 37 38 39 40 \__|
41 42 43 44 45 46 47 48 /
17 18 19 20 21 22 23 24 \__
25 26 27 28 29 30 31 32 /  |
 1  2  3  4  5  6  7  8 \__|
 9 10 11 12 13 14 15 16 /

Finally, 0xFF00FF00FF00FF00ull and 0x00FF00FF00FF00FFull with shifts of 8 swap every other row, resulting in

57 58 59 60 61 62 63 64 _
49 50 51 52 53 54 55 56
41 42 43 44 45 46 47 48 _
33 34 35 36 37 38 39 40
25 26 27 28 29 30 31 32 _
17 18 19 20 21 22 23 24
 9 10 11 12 13 14 15 16 _
 1  2  3  4  5  6  7  8

at which point the block has been successfully flipped vertically.

The reflect_diag method uses the same approach to swap bits selectively. The thing to note here is that 0x0100000000000000 selects the eight-highest (top row, left of the middle) bit:

0000 0001 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000

while 0x0000000000000080 selects the eight-lowest (bottom row, right of the middle)

0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 0000 0000
0000 0000 1000 0000

bit. They are exactly 49 bits apart, so shifting them by 49 swaps their location.

For another example, the pattern 0x4020100804020100 selects the bits

0100 0000 0010 0000 
0001 0000 0000 1000
0000 0100 0000 0010
0000 0001 0000 0000

whereas its counterpart 0x0080402010080402 selects

0000 0000 1000 0000
0100 0000 0010 0000
0001 0000 0000 1000
0000 0100 0000 0010

You'll notice that the distances between the bits form a pattern that allows the whole block to be shifted in such a way that they align with each other's original position.

Also note that compared to the horizontally and vertically flipped versions, this code does not overwrite the original values but composes a new output. Michiel's code does the shifting in-place and encodes the shifts in octal, so >> 010 actually means >> 8, 020 is 16 and so on.