C
C#2y ago
Gustavo

❔ 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
Anton2y 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
Accord2y 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.