Does anyone know an efficient way to rotate a 32 * 32 bit matrix by 90 degrees in C#?

Question

Possible Duplicate:
How do you rotate a two dimensional array?

I have 32 Int32's. Picture this as a block of 32 * 32 bits.

I need to rotate this block of bits 90 degrees clockwise. What's the most efficient way to do this in C#?

Answer 1

http://geekswithblogs.net/cwilliams/archive/2008/06/16/122906.aspx -- hope it will help.

Answer 2

int[] oldArray;
int[] newArray;

for(int i = 0; i < 32; i++)
{
   for(int j = 0; j < 32; j++)
   {
      newArray[i] += ((oldArray[j] & (1 << i)) >> i) << j;
   }
}

This is written off the top of my head, but it should work.

Answer 3

Rotate which way by 90 degrees? This rotates anticlockwise:

static uint[] BitwiseRotateAnticlockwise(uint[] matrix)
{
    uint[] output = new uint[matrix.Length];
    uint mask = 0x01;
    for (int i = 0; i < output.Length; ++i)
    {
        for (int j = 0; j < matrix.Length; ++j)
        {
            output[i] <<= 1;
            output[i] += (matrix[j] & mask) > 0 ? 1U : 0U;
        }
        mask <<= 1;
    }
    return output;
}

Answer 4

Thanks @Dimitry

I figured out a better way of solving the problem, using DeBruijn LSB lookups, rather than rotating.

Answer 5

@Mikael Svenson you answered this, but as a comment.

Answer 6

This can be solved in O(1), you must only save information about how much degrees was your matrix rotated, and overload matrix reading functions, get into it other matrix traversing algorithm depends on how much degrees matrix was rotated.

Answer 7

If you need super efficient solution you can use a data-structure solution, a new

class Rotatable{
    bool IsRotated;
    array myarray;

    object get(int idx1,int idx2)
    {
        if(IsRotated)
              return myarray.getElementAt(calcRotatedIdx1(idx1,idx2),calcRotatedIdx2(idx1,idx2);

        return myarray.getElementAt(idx1,idx2);
    }

}

it has very slight performance overhead when accessing the new array but will get you there very fast