C#•2y ago

❔ Implementing shifts for 256 bit integer class

I'm writing a custom 256 bit int class for Godot. Internally it is stored as 4 ulong types. I've tried the following implementation but it has odd bugs such as shifts working for some numbers, but not all:

public static UInt256 operator >> (UInt256 a, int b)
    {
        ulong[] result = new ulong[4];
        int shift = b % 256;
        int fullShift = b / 256;

        for (int i = 0; i < 4; i++)
        {
            int index = (i - fullShift + 4) % 4;
            result[i] = a.values[index] >> shift;
            if (i > 0)
            {
                int shiftAmount = 64 - shift;
                result[i] |= a.values[(index - 1 + 4) % 4] << shiftAmount;
            }
        }

        return new UInt256(result[0], result[1], result[2], result[3]);
    }

    public static UInt256 operator << (UInt256 a, int b)
    {
        ulong[] result = new ulong[4];
        int shift = b % 256;
        int fullShift = b / 256;

        for (int i = 0; i < 4; i++)
        {
            int index = (i + fullShift) % 4;
            result[i] = a.values[index] << shift;
            if (i < 3)
            {
                int shiftAmount = 64 - shift;
                result[i] |= a.values[(index + 1) % 4] >> shiftAmount;
            }
        }

        Godot.GD.Print(result[0], result[1], result[2], result[3]);
        return new UInt256(result[0], result[1], result[2], result[3]);
    }

public static UInt256 operator >> (UInt256 a, int b)
    {
        ulong[] result = new ulong[4];
        int shift = b % 256;
        int fullShift = b / 256;

        for (int i = 0; i < 4; i++)
        {
            int index = (i - fullShift + 4) % 4;
            result[i] = a.values[index] >> shift;
            if (i > 0)
            {
                int shiftAmount = 64 - shift;
                result[i] |= a.values[(index - 1 + 4) % 4] << shiftAmount;
            }
        }

        return new UInt256(result[0], result[1], result[2], result[3]);
    }

    public static UInt256 operator << (UInt256 a, int b)
    {
        ulong[] result = new ulong[4];
        int shift = b % 256;
        int fullShift = b / 256;

        for (int i = 0; i < 4; i++)
        {
            int index = (i + fullShift) % 4;
            result[i] = a.values[index] << shift;
            if (i < 3)
            {
                int shiftAmount = 64 - shift;
                result[i] |= a.values[(index + 1) % 4] >> shiftAmount;
            }
        }

        Godot.GD.Print(result[0], result[1], result[2], result[3]);
        return new UInt256(result[0], result[1], result[2], result[3]);
    }

2 Replies

Anton•2y ago

it should be a struct not a class also use stackalloc for those temporary arrays well your code is just wrong it doesn't handle shift of more than 64 bits also take a byte instead of an int, or do a range check shifting by an amount larger than the size of a number is UB I think ah nevermind it does handle larger values well, must be some logical error ah I see it divide by 64 not by 256

Accord•2y ago

Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.

Gaming

Programming

❔ Implementing shifts for 256 bit integer class