Bug: Incorrect result for 32-bit right shift of specific negative values in BigInteger

[aklette]

Versions

System.Numerics Runtime Version v4.0.30319
VS 2017, .NetFx 4.7.2, C# 7.3, x86, x64, Debug & Release

Demonstration

The following Console App demonstrates the bug
The pattern described in the comment repeats
This is not a display issue: on iteration j == 32

• bi2's debugger-displayed value is {0} zero
• In the Watch window, ToString() returns "0"
• In the Watch window, bi2 + 1 returns a BigInteger value {1}
• The same is true at iteration j == 64

        using System;
        using System.Numerics;

        namespace ConsoleApp1
        {
          class Program
          {
            static unsafe void Main(string[] args)
            {
              BigInteger bi = new BigInteger(new byte[]
        // Pattern: <--  LoWrd non-0   -->   
                  { 0x01, 0x00, 0x00, 0x00, 
        //          <-- N x 4-byte words all 0                 --> 
                    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        //          < HiWrd all bits set >
                    0xff, 0xff, 0xff, 0xff });

              var bytes = bi.ToByteArray();
              Console.WriteLine(bi);
              Console.Write("Before:             ");
              for (int i = 0; i < bytes.Length; i++)
                Console.Write($"{bytes[i]:X2}{(i + 1 == bytes.Length ? "" : ", ")}");
              Console.WriteLine($" (sign {bi.Sign})");
              for (int j = 0; j < 66; j++)
              {
                BigInteger bi2 = bi >> j;
                bytes = bi2.ToByteArray();
                Console.Write($"After {j:D3}-bit ASHR: ");
                for (int i = 0; i < bytes.Length; i++)
                  Console.Write($"{bytes[i]:X2}{(i + 1 == bytes.Length ? "" : ", ")}");
                Console.WriteLine($" (sign {bi2.Sign})");
              }
              Console.ReadKey();
        } } }

Output:

-79228162514264337593543950335
Before:             01, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, FF (sign -1)
After 000-bit ASHR: 01, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, FF (sign -1)
After 001-bit ASHR: 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 80 (sign -1)
After 002-bit ASHR: 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, C0 (sign -1)
...
After 031-bit ASHR: 00, 00, 00, 00, 00, 00, 00, 00, FE (sign -1)
After 032-bit ASHR: 00 (sign 0) <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
After 033-bit ASHR: 00, 00, 00, 00, 00, 00, 00, 80 (sign -1)
After 063-bit ASHR: 00, 00, 00, 00, FE (sign -1)
After 064-bit ASHR: 00 (sign 0) <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
After 065-bit ASHR: 00, 00, 00, 80 (sign -1)

[aklette]

Workaround:

// instead of...
var newVar = bigInt >> n;

// this seems to work correctly (for positives, negatives and zero)...
var newVar = bigInt.Sign == -1 ? ~(~bigInt >> n) : bigInt >> n;

E&OE: Based on limited understanding of theory plus assumptions about BigInteger's internal mechanics. I don't have the bandwidth to get into it rigorously but this has worked for me so far.