146
1
using System;
2
using System.Diagnostics;
3
4
public class Program
5
{
6
public static int ModuloBitShiftRussianPeasant(int i, int j)
7
{
8
if (i <= j) //trivial modulo
9
return (i == j) ? 0 : i;
10
else if (j==0)
11
return i;
12
13
int x = j;
14
int halfi = i >> 1;
15
while (x < halfi)
16
{
17
x <<= 1;
18
}
19
while (i >= j)
20
{
21
if (i >= x)
22
i -= x;
23
else
24
x >>= 1;
Cached Result