Incorrect results of right shifting huge BigIntegers

[gaazkam]

Description

Enormous negative BigIntegers produce -1 when right shifted by any value.

Reproduction Steps

using System.Numerics;

BigInteger bigInt = new BigInteger(-1) << int.MaxValue;
Console.WriteLine(bigInt.GetBitLength());
BigInteger shiftedBigInt = bigInt >> 1;
Console.WriteLine(shiftedBigInt.GetBitLength());
Console.WriteLine(shiftedBigInt == new BigInteger(-1));

Expected behavior

The program should output:

2147483647
2147483646
False

Actual behavior

The program outputs:

2147483647
0
True

Regression?

No response

Known Workarounds

No response

Configuration

Which version of .NET is the code running on?

<TargetFramework>net6.0</TargetFramework>

What OS and version, and what distro if applicable?

Windows 11 Pro Version 21H2

What is the architecture (x64, x86, ARM, ARM64)?

x64

Other information

• Positive BigIntegers seem to not suffer from this issue, even if they are as enormous: (new BigInteger(1) << int.MaxValue) >> 1 seems to give expected results.
• Slightly less enormous negative BigIntegers also seem to not suffer from this issue: (new BigInteger(-1) << (int.MaxValue - 1000)) >> 1 seems to give expected results. (new BigInteger(-1) << (int.MaxValue - 10)) >> 1, however, still returns -1.
• How much we right shift the enormous big integer does not seem to affect the result. (new BigInteger(-1) << int.MaxValue) >> (int.MaxValue - 4) still gives -1.

[ghost]

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

Issue Details

---

Description

Enormous negative BigIntegers produce -1 when right shifted by any value.

Reproduction Steps

using System.Numerics;

BigInteger bigInt = new BigInteger(-1) << int.MaxValue;
Console.WriteLine(bigInt.GetBitLength());
BigInteger shiftedBigInt = bigInt >> 1;
Console.WriteLine(shiftedBigInt.GetBitLength());
Console.WriteLine(shiftedBigInt == new BigInteger(-1));

Expected behavior

The program should output:

2147483647
2147483646
False

Actual behavior

The program outputs:

2147483647
0
True

Regression?

No response

Known Workarounds

No response

Configuration

Which version of .NET is the code running on?

<TargetFramework>net6.0</TargetFramework>

What OS and version, and what distro if applicable?

Windows 11 Pro Version 21H2

What is the architecture (x64, x86, ARM, ARM64)?

x64

Other information

• Positive BigIntegers seem to not suffer from this issue, even if they are as enormous: (new BigInteger(1) << int.MaxValue) >> 1 seems to give expected results.
• Slightly less enormous negative BigIntegers also seem to not suffer from this issue: (new BigInteger(-1) << (int.MaxValue - 1000)) >> 1 seems to give expected results. (new BigInteger(-1) << (int.MaxValue - 10)) >> 1, however, still returns -1.
• How much we right shift the enormous big integer does not seem to affect the result. (new BigInteger(-1) << int.MaxValue) >> (int.MaxValue - 4) still gives -1.

Author:	gaazkam
Assignees:	-
Labels:	area-System.Numerics, untriaged
Milestone:	-

[jeffhandley]

@tannergooding Do you think this bug can be fixed without the significant refactoring we've been talking about for BigInteger, or should we wait to address it until we have that work scheduled?

[tannergooding]

Yes, it should be. It would probably be easier after, but I don't think that its necessary or good to wait if someone has time to look at this for .NET 7

[jeffhandley]

Per discussion with the team, we will consider backporting the fix for this issue into .NET 6 if we can get validation that the user's scenario is addressed with the fix. We'd also need to get information that describes the types of applications affected, if the issues are blocking production scenarios, and an understanding of when .NET 7 would be adopted into that environment.

[gaazkam]

Per discussion with the team, we will consider backporting the fix for this issue into .NET 6 if we can get validation that the user's scenario is addressed with the fix. We'd also need to get information that describes the types of applications affected, if the issues are blocking production scenarios, and an understanding of when .NET 7 would be adopted into that environment.

I am sorry for my late reply.

But no, this doesn't block any production scenarios. I hit this issue when I was trying to self-educate by implementing a program that would compute lots of digits of pi. This has never been intended to be used in production and even for this purpose I don't need this functionality.