* Warren D Smith <warren.wds@gmail.com> [Apr 18. 2014 18:50]:
[...]
Henry Warren's book "Hacker's delight" already discussed the 8x8 matrix transpose, which is one of these 7 problems. He ended up with the following incredible algorithm:
uint64 TransposeBitBd(BitBd x){ //Adapted from Warren:: Hacker's delight. uint64 t; t = (x ^ (x >> 7)) & U64(0x00AA00AA00AA00AA); x = x ^ t ^ (t << 7); t = (x ^ (x >> 14)) & U64(0x0000CCCC0000CCCC); x = x ^ t ^ (t << 14); t = (x ^ (x >> 28)) & U64(0x00000000F0F0F0F0); x = x ^ t ^ (t << 28); return(x); }
Good luck figuring it out.
Hint: ? n=8; M=matrix(n,n,r,c,n*(r-1)+c-1) [ 0 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] ? M - M~ \\ tilde is "transpose" in Pari [ 0 -7 -14 -21 -28 -35 -42 -49] [ 7 0 -7 -14 -21 -28 -35 -42] [14 7 0 -7 -14 -21 -28 -35] [21 14 7 0 -7 -14 -21 -28] [28 21 14 7 0 -7 -14 -21] [35 28 21 14 7 0 -7 -14] [42 35 28 21 14 7 0 -7] [49 42 35 28 21 14 7 0] Which suggests (DO see https://oeis.org/draft/A241216 !) the partition [7, 14, 28] right away. Exercise: Transpose 4 x 4 in two steps: ? n=4; M=matrix(n,n,r,c,n*(r-1)+c-1) [ 0 1 2 3] [ 4 5 6 7] [ 8 9 10 11] [12 13 14 15] ? M - M~ [0 -3 -6 -9] [3 0 -3 -6] [6 3 0 -3] [9 6 3 0] How many steps does one apparently need for n x n (using min-step m, and 2*m, 4*m, 8*m, ... as far as needed) ?
[...]
Best, jj