Skip to content

System.Numerics.BigInteger.TrailingZeroCount is broken for numbers with a lot of trailing zeros. #77720

Closed
@tkekalainen

Description

@tkekalainen

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:

for (int i = 1; (part == 0) && (i < value._bits.Length); i++)
{
part = value._bits[i];
result += (sizeof(uint) * 8);
i++;
}

As does this one:

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++;
}

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

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions