diff options
| author | Drew Kersnar <18474647+dakersnar@users.noreply.github.com> | 2022-11-10 19:52:53 +0300 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2022-11-10 19:52:53 +0300 |
| commit | 97643fd6231c2168d6992c31c7f5293544d7e357 (patch) | |
| tree | fe01913456b8f4deab82f680efe7c8f1c59be749 | |
| parent | 1205538e7a619e294fec7dc059df66072d302462 (diff) | |
Fix bug with BigInteger.TrailingZeroCount (#77727)
* Fix bug with BigInteger.TrailingZeroCount
* Update src/libraries/System.Runtime.Numerics/tests/BigIntegerTests.GenericMath.cs
Co-authored-by: Tommi Kekäläinen <76913562+tkekalainen@users.noreply.github.com>
* Update negative code path
* Simplify logic for handling negative values
* Update src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs
Co-authored-by: Tommi Kekäläinen <76913562+tkekalainen@users.noreply.github.com>
* Update comment
Co-authored-by: Tommi Kekäläinen <76913562+tkekalainen@users.noreply.github.com>
| -rw-r--r-- | src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs | 39 | ||||
| -rw-r--r-- | src/libraries/System.Runtime.Numerics/tests/BigIntegerTests.GenericMath.cs | 3 |
2 files changed, 11 insertions, 31 deletions
diff --git a/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs b/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs index 532f1258897..78e3ec4f7e5 100644 --- a/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs +++ b/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs @@ -3481,42 +3481,19 @@ namespace System.Numerics ulong result = 0; - if (value._sign >= 0) - { - // When the value is positive, we simply need to do a tzcnt for all bits until we find one set - - uint part = value._bits[0]; + // Both positive values and their two's-complement negative representation will share the same TrailingZeroCount, + // so the sign of value does not matter and both cases can be handled in the same way - for (int i = 1; (part == 0) && (i < value._bits.Length); i++) - { - part = value._bits[i]; - result += (sizeof(uint) * 8); + uint part = value._bits[0]; - i++; - } - - result += uint.TrailingZeroCount(part); - } - else + for (int i = 1; (part == 0) && (i < value._bits.Length); i++) { - // When the value is negative, we need to tzcnt the two's complement representation - // We'll do this "inline" to avoid needing to unnecessarily allocate. - - uint part = ~value._bits[0] + 1; - - for (int i = 1; (part == 0) && (i < value._bits.Length); i++) - { - // Simply process bits, adding the carry while the previous value is zero - - part = ~value._bits[i] + 1; - result += (sizeof(uint) * 8); - - i++; - } - - result += uint.TrailingZeroCount(part); + part = value._bits[i]; + result += (sizeof(uint) * 8); } + result += uint.TrailingZeroCount(part); + return result; } diff --git a/src/libraries/System.Runtime.Numerics/tests/BigIntegerTests.GenericMath.cs b/src/libraries/System.Runtime.Numerics/tests/BigIntegerTests.GenericMath.cs index d4e06061325..3e19f1cf22e 100644 --- a/src/libraries/System.Runtime.Numerics/tests/BigIntegerTests.GenericMath.cs +++ b/src/libraries/System.Runtime.Numerics/tests/BigIntegerTests.GenericMath.cs @@ -366,6 +366,9 @@ namespace System.Numerics.Tests Assert.Equal((BigInteger)63, BinaryIntegerHelper<BigInteger>.TrailingZeroCount(Int64MaxValuePlusOne)); Assert.Equal((BigInteger)0, BinaryIntegerHelper<BigInteger>.TrailingZeroCount(UInt64MaxValue)); + + Assert.Equal((BigInteger)1000, BinaryIntegerHelper<BigInteger>.TrailingZeroCount(BigInteger.Pow(2, 1000))); + Assert.Equal((BigInteger)1000, BinaryIntegerHelper<BigInteger>.TrailingZeroCount(-BigInteger.Pow(2, 1000))); } [Fact] |