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