How to rotate an array of bits

there's no way to do rotation by arbitrary angles without sines and cosines, but it is possible to optimize the calculation depending on what other constraints you're prepared to impose. This can get very complicated, but can result in huge improvements for the "special case" you've defined.

If your images are all the same size and reasonably small, like your butterfly, and you were planning to do a lot of them, you could preform the slow calculation once, and simply remember the x,y of each pixel of the source image that became the x',y' of the destination image

If you always want to rotate an image by a specific angle each time, you only need to do the heavy math once (and really, it's not that heavy). The best way to do this is by working the process backwards. For every pixel in the destination image, you calculate the corresponding location in the starting image. This "source" pixel coordinate is saved in what is called a Lookup Table or LUT. Once you build this LUT for the angle and origin of location that you want, then it is very quick to use each entry of the LUT to "move" the pixels of a source image to the correct pixel of the destination image. Where this gets tricky and involves more math is whn deciding how to weight the source date to come up with the destination data. When you work backwards from the integer destination image coordinates, you will end up with floating point coordinates in the source image. These floating point coordinates need to be interpolated. The simplest method is to use the "Nearest Neighbor" integer pixel coordinate to the calculated floating point values, but there are other algorithms such as "Bi-Linear" or "Bi-Cubic" that will provide a better quality of the finished image (but are of course slower than Nearest NEighbor"

To see that it can't be just a question of shifting points around, just draw a frame around your image: In the rotated version, the image will have diagonal edges and so won't even fit in the dimensions of the original image.

So, to rotate it you'll have to compute where each pixel goes. Note that the top left point (0,1) will not end up at (1,1) but at a point on the diagonal whose distance from the origin is 1: namely, at (sqrt(2)/2, sqrt(2)/2). Since sin(45) = cos(45) = sqrt(2)/2, the algorithm you're looking for is multiplication of each point's coordinates by this transformation matrix:

|  sqrt(2)/2  sqrt(2)/2 |
| -sqrt(2)/2  sqrt(2)/2 |

See the wikipedia page on Transformation Matrices for the details. So, you have to do a lot of multiplications but you don't have to calculate any sines or cosines (I just did that for you from memory). You can take some other shortcuts, as the other answers suggested, but one way or another you have to compute where each pixel must go.

Of course you'll also have to crop or pad to create a normal rectangular image.

PS. Better yet, instead of implementing this solution, outsource it to a graphics library that does rotations. Or check out this SO question and the solution suggested in the comments under the question:

Consider scipy.ndimage.interpolation.shift() and rotate() or skimage.transform.fast_homography() for interpolated translations and rotations of 2D numpy arrays.

If you only want to limit rotation to 45 degrees, you don't need to use sin and cos, for that particular case I would advice you to use a fast isometric diamond drawing algorithm and adapt it to your matrix. Usually a couple nested loops and 4 variables (x, y, width, height) will do it.