Repository navigation
System.Numerics.BigInteger.TrailingZeroCount is broken for numbers with a lot of trailing zeros. #77720
Description
Description
When given a large BigInteger with a high number of trailing zeros, TrailingZeroCount only checks and counts a part of them.
Reproduction Steps
BigInteger.TrailingZeroCount(BigInteger.Pow(2, 1000))
Expected behavior
Returns 1000
Actual behavior
Returns 520
Regression?
To my knowledge, this is a new method.
Known Workarounds
None, except to avoid this method and implement the count in a slower way.
Configuration
7.0.100-rc.2.22477.23
Windows 10 21H2 (19044.2130)
x64
Other information
This loop increments i twice per iteration, once in the loop body, and a second time in the for statement:
runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs
Lines 3490 to 3496 in 33be29e
As does this one:
runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs
Lines 3507 to 3515 in 33be29e
This means that i = 2, 4, 6... are skipped completely, they aren't tested whether they are nonzero, nor do they increment the count.
As a side note, the bottom loop is unnecessary. The number of trailing zeros of a negative two's complement number is the same as that of its absolute value. If value._bits[i] is zero, ~value._bits[i] + 1 is also zero. And if value._bits[i] is not zero, then the end of it is of the form one, followed by n zeros. Inverting it gives zero, followed by n ones. And adding one to this changes it back to one, followed by n zeros. As we don't care about the leading bits of value._bits[i], only the number of trailing zeros, the negation again doesn't change anything.
Some C++ compilers, like clang, know this:
int trailing_zero_count(unsigned int num) { return __builtin_ctz(num); }
int trailing_zero_count_negate(unsigned int num) { return __builtin_ctz(~num + 1); }
clang 15.0.0 -O3
trailing_zero_count(unsigned int): # @trailing_zero_count(unsigned int)
bsf eax, edi
ret
trailing_zero_count_negate(unsigned int): # @trailing_zero_count_negate(unsigned int)
bsf eax, edi
ret
Activity
vcsjones commentedon Nov 1, 2022
I'm perplexed by the output of the answer too, but I don't expect it to be 1000. Length of the string should be 302 digits:
Can you explain how you arrived at 1000? Myself, I would expect the answer to be zero.
tkekalainen commentedon Nov 1, 2022
Doesn't TrailingZeroCount return the number of trailing zero bits? At least that's how it is implemented for int, uint, long etc. The documentation doesn't seem to specify, for whatever reason.
vcsjones commentedon Nov 1, 2022
🤔 clearly I need more coffee.... 🤦
dakersnar commentedon Nov 1, 2022
This is a bug. I investigated further and found that there was an accidental extra increment when iterating through the BigInteger, leading to only roughly half of the bits being counted. Putting up a fix shortly.