Integer division rounding down in C# (for negatives)

Question

Is there any way to perform integer dividing in C# (without float or decimal, I need to keep this one very fast) that rounds down the number?

The default division just discards fraction argument. Consider:

 1 / 2 = 0 // That is correct
-1 / 2 = 0 // ... but I want to get (-1) here!

My division will take both positive and negative numbers for dividor. I need not to employ if, as branching will be too costly (the operation will be run very frequently in realtime game engine)...

Answer 1

Dividing by 2 is a simple bitwise right-shift. After @elgonzo's (now deleted) mention of the properties of C#'s rightshift, I decided to have a look how it works, and it seems to do exactly what you want:

var result = number >> 1;

This gives the following results:

11 -> 5
10 -> 5
2 -> 1
1 -> 0
-1 -> -1
-2 -> -1
-32 -> -16
-33 -> -17

int.MaxValue and MinValue also work.

Performance-wise, this seems to be almost twice as fast as the currently accepted answer that uses modulo operators. Dividing (the same) 100000000 random numbers costs 2.17 seconds on my machine using a simple shift, while using the version with modulo's takes between 3.1 and 4.0 seconds.

The branched versions seem to perform just about the same as the modulo version: significantly slower than the simple rightshift.

Answer 2

If you want to divide a by b:

The approach which won't fail because of overflow:

int res = a / b;
return (a < 0 && a != b * res) ? res - 1 : res;

The following approaches may possibly fail because of negative overflow.

int mod = a % b;
if (mod < 0) {
  mod += b;
}
return (a - mod) / b;

A mess with mod += b because a % b can be negative. A shorter way:

return (a - (a % b + b) % b) / b;

And more clear one:

return a >= 0 ? a / b : (a - b + 1) / b;