Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

RotateLeft and RotateRight of BigInteger is buggy. #112854

Open
kzrnm opened this issue Feb 24, 2025 · 3 comments · May be fixed by #112864 or #112878
Open

RotateLeft and RotateRight of BigInteger is buggy. #112854

kzrnm opened this issue Feb 24, 2025 · 3 comments · May be fixed by #112864 or #112878
Labels
area-System.Numerics bug help wanted [up-for-grabs] Good issue for external contributors in-pr There is an active PR which will close this issue when it is merged

Comments

@kzrnm
Copy link
Contributor

kzrnm commented Feb 24, 2025

Description

See Reproduction Steps.

Reproduction Steps

Rotate((BigInteger.One << 64) - 1);
Rotate(BigInteger.One << 64);
Rotate((BigInteger.One << 64) + 1);
Rotate((BigInteger.One << 64) + 6);


Rotate((BigInteger.MinusOne << 64) - 1);
Rotate(BigInteger.MinusOne << 64);
Rotate((BigInteger.MinusOne << 64) + 1);
Rotate((BigInteger.MinusOne << 64) + 6);

void Rotate(BigInteger num)
{
    Console.Write("       Orig: "); WriteLine(num);
    Console.Write("RotateRight: "); WriteLine(BigInteger.RotateRight(num, 1));
    Console.Write(" RotateLeft: "); WriteLine(BigInteger.RotateLeft(num, 1));
    Console.WriteLine();
}
void WriteLine<T>(T num)
{
    Console.WriteLine($"{num:B96}");
}

Expected behavior

       Orig: 000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111
RotateRight: 000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111
 RotateLeft: 000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111

       Orig: 000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000
RotateRight: 000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000
 RotateLeft: 000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000

       Orig: 000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001
RotateRight: 100000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000
 RotateLeft: 000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000010

       Orig: 000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000110
RotateRight: 000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000011
 RotateLeft: 000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000001100

       Orig: 111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111
RotateRight: 000000000000000000000000000000010111111111111111111111111111111111111111111111111111111111111111
 RotateLeft: 111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111

       Orig: 111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000
RotateRight: 011111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000
 RotateLeft: 111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000001

       Orig: 111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000001
RotateRight: 111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000
 RotateLeft: 111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000011

       Orig: 111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000110
RotateRight: 011111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000011
 RotateLeft: 111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000001101

Actual behavior

       Orig: 000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111
RotateRight: 000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111
 RotateLeft: 000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111

       Orig: 000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000
RotateRight: 000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000
 RotateLeft: 000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000

       Orig: 000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001
RotateRight: 000000000000000000000000000000001000000000000000000000000000000010000000000000000000000000000000
 RotateLeft: 000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000010

       Orig: 000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000110
RotateRight: 000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000011
 RotateLeft: 000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000001100

       Orig: 111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111
RotateRight: 111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111
 RotateLeft: 111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111

       Orig: 111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000
RotateRight: 011111111111111111111111111111110000000000000000000000000000000010000000000000000000000000000000
 RotateLeft: 111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000001

       Orig: 111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000001
RotateRight: 111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000
 RotateLeft: 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010

       Orig: 111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000110
RotateRight: 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
 RotateLeft: 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001100

Regression?

.NET 7 or later

Known Workarounds

No response

Configuration

No response

Other information

similar to #112564
@dotnet-issue-labeler dotnet-issue-labeler bot added the needs-area-label An area label is needed to ensure this gets routed to the appropriate area owners label Feb 24, 2025
@dotnet-policy-service dotnet-policy-service bot added the untriaged New issue has not been triaged by the area owner label Feb 24, 2025
@huoyaoyuan huoyaoyuan added area-System.Numerics and removed needs-area-label An area label is needed to ensure this gets routed to the appropriate area owners labels Feb 24, 2025
@dotnet-policy-service Dotnet Policy Service
Copy link
Contributor

Tagging subscribers to this area: @dotnet/area-system-numerics
See info in area-owners.md if you want to be subscribed.

@kzrnm kzrnm changed the title RotateRight and RotateRight of BigInteger is buggy. RotateLeft and RotateRight of BigInteger is buggy. Feb 24, 2025
@tannergooding
Copy link
Member

tannergooding commented Feb 24, 2025 •
edited
Loading

Looks like this is because RotateRight is taking the initial carry from "currentPosition - 1when it should instead be taking it fromcurrentPosition + 1`.

It should potentially be iterating from end to beginning rather than beginning to end as well, to avoid other complexities.

A fix would be welcome here, otherwise someone from the team will try to get to it soon.

@tannergooding tannergooding added bug help wanted [up-for-grabs] Good issue for external contributors and removed untriaged New issue has not been triaged by the area owner labels Feb 24, 2025
@kzrnm
Copy link
Contributor Author

kzrnm commented Feb 24, 2025

Additionally, there is a bug where the two’s complement is not correctly obtained when the most significant bit is set.

runtime/src/libraries/System.Runtime.Numerics/src/System/Numerics/BigInteger.cs

Lines 3278 to 3281 in 5f97ddf

if (negx)
{
NumericsHelpers.DangerousMakeTwosComplement(xd);
}

@kzrnm kzrnm linked a pull request Feb 24, 2025 that will close this issue
Open
@dotnet-policy-service dotnet-policy-service bot added the in-pr There is an active PR which will close this issue when it is merged label Feb 24, 2025
@kzrnm kzrnm linked a pull request Feb 24, 2025 that will close this issue
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
area-System.Numerics bug help wanted [up-for-grabs] Good issue for external contributors in-pr There is an active PR which will close this issue when it is merged
Projects
None yet
Milestone
No milestone
3 participants
@huoyaoyuan @tannergooding @kzrnm