You can avoid division (and mod) entirely if you represent your angles in something referred to as 'BAMS', which stands for Binary Angle Measurement System. The idea is that if you store your angles in an N bit integer, you use the entire range of that integer to represent the angle. That way, there's no need to worry about overflow past 360, because the natural modulo-2^N properties of your representation take care of it for you.
For example, lets say you use 8 bits. This cuts your circle into 256 possible orientations. (You may choose more bits, but 8 is convenient for the example's sake). Let 0x00 stand for 0 degrees, 0x40 means 90 degrees, 0x80 is 180 degrees, and 0xC0 is 270 degrees. Don't worry about the 'sign' bit, again, BAMS is a natural for angles. If you interpret 0xC0 as 'unsigned' and scaled to 360/256 degrees per count, your angle is (+192)(360/256) = +270; but if you interpret 0xC0 as 'signed', your angle is (-64)(360/256)= -90. Notice that -90 and +270 mean the same thing in angular terms.
If you want to apply trig functions to your BAMS angles, you can pre-compute tables. There are tricks to smallen the tables but you can see that the tables aren't all that large. To store an entire sine and cosine table of double precision values for 8-bit BAMS doesn't take more than 4K of memory, chicken feed in today's environment.
Since you mention using this in a game, you probably could get away with 8-bit or 10-bit representations. Any time you add or subtract angles, you can force the result into N bits using a logical AND operation, e.g., angle &= 0x00FF for 8 bits.
FORGOT THE BEST PART (edit)
The turn-right vs turn-left problem is easily solved in a BAMS system. Just take the difference, and make sure to only keep the N meaningful bits. Interpreting the MSB as a sign bit indicates which way you should turn. If the difference is negative, turn the opposite way by the abs() of the difference.
This ugly little C program demonstrates. Try giving it input like 20 10 and 20 30 at first. Then try to fool it by wrapping around the zero point. Give it 20 -10, it will turn left. Give it 20 350, it still turns left. Note that since it's done in 8 bits, that 181 is indistinguishable from 180, so don't be surprised if you feed it 20 201 and it turns right instead of left - in the resolution afforded by eight bits, turning left and turning right in this case are the same. Put in 20 205 and it will go the shorter way.
#include <stdio.h>
#include <math.h>
#define TOBAMS(x) (((x)/360.0) * 256)
#define TODEGS(b) (((b)/256.0) * 360)
int main(void)
{
double a1, a2; // "real" angles
int b1, b2, b3; // BAMS angles
// get some input
printf("Start Angle ? ");
scanf("%lf", &a1);
printf("Goal Angle ? ");
scanf("%lf", &a2);
b1 = TOBAMS(a1);
b2 = TOBAMS(a2);
// difference increases with increasing goal angle
// difference decreases with increasing start angle
b3 = b2 - b1;
b3 &= 0xff;
printf("Start at %7.2lf deg and go to %7.2lf deg\n", a1, a2);
printf("BAMS are 0x%02X and 0x%02X\n", b1, b2);
printf("BAMS diff is 0x%02X\n", b3);
// check what would be the 'sign bit' of the difference
// negative (msb set) means turn one way, positive the other
if( b3 & 0x80 )
{
// difference is negative; negate to recover the
// DISTANCE to move, since the negative-ness just
// indicates direction.
// cheap 2's complement on an N-bit value:
// invert, increment, trim
b3 ^= -1; // XOR -1 inverts all the bits
b3 += 1; // "add 1 to x" :P
b3 &= 0xFF; // retain only N bits
// difference is already positive, can just use it
printf("Turn left %lf degrees\n", TODEGS(b3));
printf("Turn left %d counts\n", b3);
}
else
{
printf("Turn right %lf degrees\n", TODEGS(b3));
printf("Turn right %d counts\n", b3);
}
return 0;
}