dotnet / dotnet/runtime

[API Proposal]: ResetLowestSetBit on IBinaryInteger

Open
#129,719 5 comments 0 reactions 0 assignees View on GitHub
api-suggestion area-System.Numerics help wanted
Dominant language
C#
Stars
18.3k
Forks
5.6k
PR merge metrics
PR metrics pending

Description

### Background and motivation

The JIT already recognizes the `value & (value - 1)` pattern and replaces it with the cheap instructions, but having a named helper is easier to read. This currently exists in CoreLib as `BitOperations.ResetLowestSetBit` (next to `TrailingZeroCount`, `LeadingZeroCount`, etc.).

### API Proposal

```csharp
namespace System.Numerics
{
public partial interface IBinaryInteger
{
static virtual TSelf ResetLowestSetBit(TSelf value);
static virtual TSelf SetBit(TSelf value, TSelf index);
static virtual TSelf ClearBit(TSelf value, TSelf index);
static virtual TSelf ToggleBit(TSelf value, TSelf index);
}
}

// Public/implicit on all types except char (explicitly special handled), and BigInteger (either explicit or via DIM)
// Same as ReverseBits in https://github.com/dotnet/runtime/issues/125879#issuecomment-4433166525
namespace System
{
public readonly partial struct Byte : IBinaryInteger
{
public static byte ResetLowestSetBit(byte value);
public static byte SetBit(byte value, byte index);
public static byte ClearBit(byte value, byte index);
public static byte ToggleBit(byte value, byte index);
}

public readonly partial struct SByte : IBinaryInteger
{
public static sbyte ResetLowestSetBit(sbyte value);
public static sbyte SetBit(sbyte value, sbyte index);
public static sbyte ClearBit(sbyte value, sbyte index);
public static sbyte ToggleBit(sbyte value, sbyte index);
}

public readonly partial struct UInt16 : IBinaryInteger
{
public static ushort ResetLowestSetBit(ushort value);
public static ushort SetBit(ushort value, ushort index);
public static ushort ClearBit(ushort value, ushort index);
public static ushor tToggleBit(ushort value, ushort index);
}

public readonly partial struct Int16 : IBinaryInteger
{
public static short ResetLowestSetBit(short value);
public static short SetBit(short value, short index);
public static short ClearBit(short value, short index);
public static short ToggleBit(short value, short index);
}

public readonly partial struct UInt32 : IBinaryInteger
{
public static uint ResetLowestSetBit(uint value);
public static uint SetBit(uint value, uint index);
public static uint ClearBit(uint value, uint index);
public static uint ToggleBit(uint value, uint index);
}

public readonly partial struct Int32 : IBinaryInteger
{
public static int ResetLowestSetBit(int value);
public static int SetBit(int value, int index);
public static int ClearBit(int value, int index);
public static int ToggleBit(int value, int index);
}

public readonly partial struct UInt64 : IBinaryInteger
{
public static ulong ResetLowestSetBit(ulong value);
public static ulong SetBit(ulong value, ulong index);
public static ulong ClearBit(ulong value, ulong index);
public static ulong ToggleBit(ulong value, ulong index);
}

public readonly partial struct Int64 : IBinaryInteger
{
public static long ResetLowestSetBit(long value);
public static long SetBit(long value, long index);
public static long ClearBit(long value, long index);
public static long ToggleBit(long value, long index);
}

public readonly partial struct UIntPtr : IBinaryInteger
{
public static nuint ResetLowestSetBit(nuint value);
public static nuint SetBit(nuint value, nuint index);
public static nuint ClearBit(nuint value, nuint index);
public static nuint ToggleBit(nuint value, nuint index);
}

public readonly partial struct IntPtr : IBinaryInteger
{
public static nint ResetLowestSetBit(nint value);
public static nint SetBit(nint value, nint index);
public static nint ClearBit(nint value, nint index);
public static nint ToggleBit(nint value, nint index);
}

public readonly partial struct UInt128 : IBinaryInteger
{
public static UInt128 ResetLowestSetBit(UInt128 value);
public static UInt128 SetBit(UInt128 value, UInt128 index);
public static UInt128 ClearBit(UInt128 value, UInt128 index);
public static UInt128 ToggleBit(UInt128 value, UInt128 index);
}

public readonly partial struct Int128 : IBinaryInteger
{
public static Int128 ResetLowestSetBit(Int128 value);
public static Int128 SetBit(Int128 value, Int128 index);
public static Int128 ClearBit(Int128 value, Int128 index);
public static Int128 ToggleBit(Int128 value, Int128 index);
}

public readonly partial struct Char : IBinaryInteger
{
static char IBinaryInteger.ResetLowestSetBit(char value);
static char IBinaryInteger.SetBit(char value, char index);
static char IBinaryInteger.ClearBit(char value, char index);
static char IBinaryInteger.ToggleBit(char value, char index);
}
}
```

### API Usage

```diff
do
{
uint bit = uint.TrailingZeroCount(value);
// Do stuff with the bit
- value &= value - 1;
+ value = uint.ResetLowestSetBit(value);
}
while (value != 0);
```

### Alternative Designs

Expose the helpers on `BitOperations` instead.

```csharp
namespace System.Numerics;

public static partial class BitOperations
{
public static uint ResetLowestSetBit(uint value);
public static ulong ResetLowestSetBit(ulong value);
}
```

### Risks

_No response_

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the IBinaryInteger proposal and the existing BitOperations.ResetLowestSetBit implementation in CoreLib. Compare the proposed members across the listed integer types, including the special handling for Char and BigInteger, and consider the alternative BitOperations design. Done means the API shape and implementation scope are resolved.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp
Domain
backend-api-design
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.