Как узнать остаток от деления?

Интересные вам задачки дают. Полное решение не дам, это не спортивно, но идею и некоторые заготовки покажу. В основе лежит тот факт, что результат операции XOR эквивалентен результату полусумматора и остается только корректно учесть бит переноса. Разумеется, на аппаратном уровне все реализуется проще на последовательной цепочке полных сумматоров, так что тут только имитация работы такой схемы.

//сумматор
int Summ(int a, int b)
{
    int t;
    do
    {
        t = a & b; //получаем поразрядные биты переносов
        a ^= b;    //получаем поразрядные биты полусумм
        b = t << 1;//сдвигаем биты переносов влево на их потенциальное место
    }
    //продолжаем пока есть хоть один бит переноса
    while (t != 0);
    return a;
}

//двоичная инверсия
int BinNegate(int a)
{
    return a ^ -1;
}

//арифметическая инверсия
int MathNegate(int a)
{
    return Summ(BinNegate(a), 1);
}

Дальше уже сами. Двоичное деление в столбик достаточно простое, алгоритм находится элементарно, но на крайний случай можно и просто циклом вычитания обойтись, ну а сделать из сложения вычитание предоставленными средствами элементарно. Двоичное сравнение это вычитание и проверка знакового разряда. К сожалению обойтись без операции сравнения с нулем не получится, процессоры для этого используют специальный флаг в регистре флагов, который выставляется во время выполнения арифметической операции, а в C# не поддерживается соглашение "все что не ноль - истина" для условных операторов, но, например, в C/C++ это соглашение поддерживается и там можно обойтись без сравнения с нулем. Понятно, что задачка преследует исключительно академический интерес, но она интересная и ее можно решить используя только битовые операции и операции на (не)равенство нулю, без применения других операций прямого сравнения чисел и любых арифметических операций.