RotateLeft and RotateRight of BigInteger is buggy.

[kzrnm]

Description

See Reproduction Steps.

Reproduction Steps

Rotate((BigInteger.One << 64) - 1);
Rotate(BigInteger.One << 64);
Rotate((BigInteger.One << 64) + 1);
Rotate((BigInteger.One << 64) + 6);


Rotate((BigInteger.MinusOne << 64) - 1);
Rotate(BigInteger.MinusOne << 64);
Rotate((BigInteger.MinusOne << 64) + 1);
Rotate((BigInteger.MinusOne << 64) + 6);

void Rotate(BigInteger num)
{
    Console.Write("       Orig: "); WriteLine(num);
    Console.Write("RotateRight: "); WriteLine(BigInteger.RotateRight(num, 1));
    Console.Write(" RotateLeft: "); WriteLine(BigInteger.RotateLeft(num, 1));
    Console.WriteLine();
}
void WriteLine<T>(T num)
{
    Console.WriteLine($"{num:B96}");
}

Expected behavior

       Orig: 000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111
RotateRight: 000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111
 RotateLeft: 000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111

       Orig: 000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000
RotateRight: 000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000
 RotateLeft: 000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000

       Orig: 000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001
RotateRight: 100000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000
 RotateLeft: 000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000010

       Orig: 000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000110
RotateRight: 000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000011
 RotateLeft: 000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000001100

       Orig: 111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111
RotateRight: 000000000000000000000000000000010111111111111111111111111111111111111111111111111111111111111111
 RotateLeft: 111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111

       Orig: 111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000
RotateRight: 011111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000
 RotateLeft: 111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000001

       Orig: 111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000001
RotateRight: 111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000
 RotateLeft: 111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000011

       Orig: 111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000110
RotateRight: 011111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000011
 RotateLeft: 111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000001101

Actual behavior

       Orig: 000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111
RotateRight: 000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111
 RotateLeft: 000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111

       Orig: 000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000
RotateRight: 000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000
 RotateLeft: 000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000

       Orig: 000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001
RotateRight: 000000000000000000000000000000001000000000000000000000000000000010000000000000000000000000000000
 RotateLeft: 000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000010

       Orig: 000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000110
RotateRight: 000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000011
 RotateLeft: 000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000001100

       Orig: 111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111
RotateRight: 111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111
 RotateLeft: 111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111

       Orig: 111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000
RotateRight: 011111111111111111111111111111110000000000000000000000000000000010000000000000000000000000000000
 RotateLeft: 111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000001

       Orig: 111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000001
RotateRight: 111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000
 RotateLeft: 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010

       Orig: 111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000110
RotateRight: 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
 RotateLeft: 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100

Regression?

.NET 7 or later

Known Workarounds

No response

Configuration

No response

Other information

similar to #112564

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-numerics
See info in area-owners.md if you want to be subscribed.

[tannergooding]

Looks like this is because RotateRight is taking the initial carry from "currentPosition - 1when it should instead be taking it fromcurrentPosition + 1`.

It should potentially be iterating from end to beginning rather than beginning to end as well, to avoid other complexities.

A fix would be welcome here, otherwise someone from the team will try to get to it soon.

[kzrnm]

Additionally, there is a bug where the two’s complement is not correctly obtained when the most significant bit is set.

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 3278 to 3281 in 5f97ddf

	if (negx)
	{
	NumericsHelpers.DangerousMakeTwosComplement(xd);
	}