[API Proposal]: ResetLowestSetBit on IBinaryInteger

[MihaZupan]

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

namespace System.Numerics
{
  public partial interface IBinaryInteger<TSelf>
  {
      static virtual TSelf ResetLowestSetBit(TSelf value);
  }
}

// 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<byte>
    {
        public static byte ResetLowestSetBit(byte value);
    }

    public readonly partial struct SByte : IBinaryInteger<sbyte>
    {
        public static sbyte ResetLowestSetBit(sbyte value);
    }

    public readonly partial struct UInt16 : IBinaryInteger<ushort>
    {
        public static ushort ResetLowestSetBit(ushort value);
    }

    public readonly partial struct Int16 : IBinaryInteger<short>
    {
        public static short ResetLowestSetBit(short value);
    }

    public readonly partial struct UInt32 : IBinaryInteger<uint>
    {
        public static uint ResetLowestSetBit(uint value);
    }

    public readonly partial struct Int32 : IBinaryInteger<int>
    {
        public static int ResetLowestSetBit(int value);
    }

    public readonly partial struct UInt64 : IBinaryInteger<ulong>
    {
        public static ulong ResetLowestSetBit(ulong value);
    }

    public readonly partial struct Int64 : IBinaryInteger<long>
    {
        public static long ResetLowestSetBit(long value);
    }

    public readonly partial struct UIntPtr : IBinaryInteger<nuint>
    {
        public static nuint ResetLowestSetBit(nuint value);
    }

    public readonly partial struct IntPtr : IBinaryInteger<nint>
    {
        public static nint ResetLowestSetBit(nint value);
    }

    public readonly partial struct UInt128 : IBinaryInteger<UInt128>
    {
        public static UInt128 ResetLowestSetBit(UInt128 value);
    }

    public readonly partial struct Int128 : IBinaryInteger<Int128>
    {
        public static Int128 ResetLowestSetBit(Int128 value);
    }

    public readonly partial struct Char : IBinaryInteger<char>
    {
        static char IBinaryInteger<char>.ResetLowestSetBit(char value);
    }
}

API Usage

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.

namespace System.Numerics;

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

Or also expose a bunch of other bit helpers, e.g. SetBit, ClearBit, ToggleBit

Proposal for `ResetLowestSetBit`, `SetBit`, `ClearBit`, `ToggleBit`

namespace System.Numerics
{
    public partial interface IBinaryInteger<TSelf>
    {
        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<byte>
    {
        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<sbyte>
    {
        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<ushort>
    {
        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<short>
    {
        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<uint>
    {
        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<int>
    {
        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<ulong>
    {
        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<long>
    {
        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<nuint>
    {
        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<nint>
    {
        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<UInt128>
    {
        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<Int128>
    {
        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<char>
    {
        static char IBinaryInteger<char>.ResetLowestSetBit(char value);
        static char IBinaryInteger<char>.SetBit(char value, char index);
        static char IBinaryInteger<char>.ClearBit(char value, char index);
        static char IBinaryInteger<char>.ToggleBit(char value, char index);
    }
}

Risks

No response

[dotnet-policy-service]

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

[tannergooding]

I'd note in particular the full set of commonly accelerated bit helpers is:

• (x >> y) & ((1 << z) - 1) -- Extract z length bitfield from x, starting at bit y
• x & -x -- Mask all except the lowest set bit
• x ^ (x - 1) -- Get mask up to and including the lowest set bit
• x & (x - 1) -- Reset the lowest set bit
• x & ((1 << y) - 1) -- Zero bits starting at bit y
• x & (1 << y) -- Mask Bit, if used in == 0 or != 0 then becomes Test Bit
• x | (1 << y) -- Set Bit
• x & ~(1 << y) -- Reset Bit
• x ^ (1 << y) -- Toggle Bit

Other patterns and helpers may also exist, but this is at least the set that is commonly accelerated by hardware and used; where we have several such helpers in the JIT and use some of them throughout the core libraries as well.

---

I'm generally supportive of such helpers, because I think they explicitly help with legibility and centralize the pattern we want the JIT to recognize to a single thing. However, I will note that there's been pushback against adding such helpers in the past, namely in #27382

@jkotas was one of those that had some pushback against some of the helpers at the time as the existing patterns are "very concise and easy to read for anybody dealing with bits". They had also done some investigation and determined that it is significantly more common for developers to inline the logic than to roll some helper function for it.

I'm not sure the general considerations around those have changed or if a subset of the commonly accelerated patterns are over the complexity barrier. I do have a suspicion that some of the inlining of logic is because its typically used in more perf sensitive paths and a user-defined helper function isn't guaranteed to be inlined/optimized, while an intrinsic API would be.

Either way, I'll leave this open for a few days for additional feedback before we decide to either close it or mark it ready for review. I'm doubtful this will make .NET 11 given the existing backlog (https://apireview.net/) in either case

[tannergooding]

I'd note as well, the named helper methods also solve the problem of certain operations being undefined behavior in non C# languages and in C# itself help solve the common mistakes around operator precedence, particularly shifts which occur in a somewhat "odd position" given the operation they functionally are doing is multiplication/division by a power of 2.