Bitmath

static class Bitmath
{
    // allowed primitive operations: ~(a & b), a == 0, bitshifts by constant values (logical or arithmetic), and reading/writing T[a].
    public static int Nand(this int a, int b) { return ~(a & b); }
    public static bool IsZero(this int a) { return a == 0; }
    public static int LRS(this int a, int b) { return (int)((uint)a >> b); }

    // constructed operations
    public static int Not(this int a) { return Nand(a, -1); }
    public static int And(this int a, int b) { return Not(Nand(a, b)); }
    public static int Or(this int a, int b) { return Nand(Not(a), Not(b)); }
    public static int Xor(this int a, int b) { int x = Nand(a, b); return Nand(Nand(a, x), Nand(b, x)); }

    public static bool IsNegative(this int a) { return !(a >> 31).IsZero(); }
    public static bool IsPositive(this int a) { return !(a.IsZero() | a.IsNegative()); }

    public static int LeftShift(this int a, int b)
    {
        if (!b.And(16).IsZero()) a = a << 16;
        if (!b.And(8).IsZero()) a = a << 8;
        if (!b.And(4).IsZero()) a = a << 4;
        if (!b.And(2).IsZero()) a = a << 2;
        if (!b.And(1).IsZero()) a = a << 1;
        return a;
    }

    public static int ArithmeticRightShift(this int a, int b)
    {
        if (!b.And(16).IsZero()) a = a >> 16;
        if (!b.And(8).IsZero()) a = a >> 8;
        if (!b.And(4).IsZero()) a = a >> 4;
        if (!b.And(2).IsZero()) a = a >> 2;
        if (!b.And(1).IsZero()) a = a >> 1;
        return a;
    }

    public static int LogicalRightShift(this int a, int b)
    {
        if (!b.And(16).IsZero()) a = a.LRS(16);
        if (!b.And(8).IsZero()) a = a.LRS(8);
        if (!b.And(4).IsZero()) a = a.LRS(4);
        if (!b.And(2).IsZero()) a = a.LRS(2);
        if (!b.And(1).IsZero()) a = a.LRS(1);
        return a;
    }

    static int[] RollOffsetTable =
    {
        0, 31, 30, 29, 28, 27, 26, 25,
        24, 23, 22, 21, 20, 19, 18, 17,
        16, 15, 14, 13, 12, 11, 10, 9,
        8, 7, 6, 5, 4, 3, 2, 1
    };

    public static int RollLeft(this int a, int b)
    {
        b = b.And(31);
        return a.LeftShift(b).Or(a.LogicalRightShift(RollOffsetTable[b]));
    }

    public static int RollRight(this int a, int b)
    {
        b = b.And(31);
        return a.LogicalRightShift(b).Or(a.LeftShift(RollOffsetTable[b]));
    }

    public static bool EQ(this int a, int b)
    {
        return a.Sub(b).IsZero();
    }

    public static bool NE(this int a, int b)
    {
        return !a.EQ(b);
    }

    public static bool GT(this int a, int b)
    {
        if (a.IsPositive() == b.IsPositive())
            return a.Sub(b).IsPositive();
        else
            return a.IsPositive();
    }

    public static bool LT(this int a, int b)
    {
        if (a.IsPositive() == b.IsPositive())
            return a.Sub(b).IsNegative();
        else
            return a.IsNegative();
    }

    public static bool GE(this int a, int b)
    {
        return !a.LT(b);
    }

    public static bool LE(this int a, int b)
    {
        return !a.GT(b);
    }

    public static int Add(this int a, int b)
    {
        int c;
        while (!b.IsZero())
        {
            c = a & b;
            a ^= b;
            b = c << 1;
        }
        return a;
    }

    public static int Neg(this int a)
    {
        return a.Not().Add(1);
    }

    public static int Sub(this int a, int b)
    {
        return a.Add(b.Neg());
    }

    public static int Mul(this int a, int b)
    {
        int c = 0;
        while (!b.IsZero())
        {
            if (!b.And(1).IsZero())
                c = c.Add(a);
            a = a << 1;
            b = b.LRS(1);
        }
        return c;
    }

    public static void Divmod(ref int a, ref int b)
    {
        if (a.IsZero() | b.IsZero())
        {
            b = 0;
            return;
        }
        int c = 0;
        if (a.IsPositive() & b.IsPositive())
        {
            while (b.LE(a))
            {
                c = c.Add(1);
                a = a.Sub(b);
            }
            b = a;
            a = c;
        }
        else if (a.IsPositive())
        {
            while (a.IsPositive())
            {
                c = c.Sub(1);
                a = a.Add(b);
            }
            b = a;
            a = c;
            if (!b.IsZero())
                a = a.Add(1);
        }
        else if (b.IsNegative())
        {
            while (b.GE(a))
            {
                c = c.Add(1);
                a = a.Sub(b);
            }
            b = a;
            a = c;
        }
        else
        {
            while (a.IsNegative())
            {
                c = c.Sub(1);
                a = a.Add(b);
            }
            b = a;
            a = c;
            if (!b.IsZero())
                a = a.Add(1);
        }
    }

    public static int Div(this int a, int b)
    {
        Bitmath.Divmod(ref a, ref b);
        return a;
    }

    public static int Mod(this int a, int b)
    {
        Bitmath.Divmod(ref a, ref b);
        return b;
    }
}