[API Proposal]: BitOperations.ReverseBits

-- Commented edited by area owners to match: https://github.com/dotnet/runtime/issues/125879#issuecomment-4113640759

> [!NOTE]
> This comment was generated with AI (GitHub Copilot).

# Revised API Proposal: `IBinaryInteger.ReverseBits`

## Background and Motivation

Bit reversal is a common operation in CRC computation, Huffman coding (DEFLATE), ASN.1 named bit lists, FFT (decimation-in-time), and cryptographic key usage parsing. The runtime already contains **5+ private/internal implementations** of this operation:

- `Crc32ParameterSet.ReverseBits(uint)` — CRC-32 computation
- `Crc64ParameterSet.ReverseBits(ulong)` — CRC-64 computation
- `AsnDecoder.ReverseBitsPerByte(Span)` — ASN.1 named bit list decoding
- `X509KeyUsageExtension.ReverseBitOrder(byte)` — X.509 certificate key usage
- `HuffmanTree.BitReverse(uint, int)` — DEFLATE decompression

Hardware acceleration exists on ARM64 (`rbit` via `ArmBase.ReverseElementBits`) and recent x86 (`AVX-512 BMM` via `Avx512Bmm.ReverseBits`), but there is no general-purpose public API.

**Prior art**: Rust has [`reverse_bits()`](https://doc.rust-lang.org/std/primitive.u32.html#method.reverse_bits) on all integer primitives. LLVM has `llvm.bitreverse`. Python has no built-in but `int.bit_length()` is commonly paired with manual reversal. C++ has `std::bitset` but no scalar intrinsic.

## API Surface

Per @tannergooding's [feedback](https://github.com/dotnet/runtime/issues/125879#issuecomment-4113034265), this is placed on `IBinaryInteger` as a `static virtual` method with a default interface method (DIM), rather than on `BitOperations`.

```diff
namespace System.Numerics;

public interface IBinaryInteger : IBinaryNumber, IShiftOperators
where TSelf : IBinaryInteger?
{
// EXISTING:
// static virtual TSelf LeadingZeroCount(TSelf value);
// static abstract TSelf PopCount(TSelf value);
// static virtual TSelf RotateLeft(TSelf value, int rotateAmount);
// static virtual TSelf RotateRight(TSelf value, int rotateAmount);
// static abstract TSelf TrailingZeroCount(TSelf value);

+ static virtual TSelf ReverseBits(TSelf value);
}
```

Optimized implementations on all built-in integer types:

```diff
namespace System;

public readonly partial struct Byte : IBinaryInteger
{
+ public static byte ReverseBits(byte value);
}

public readonly partial struct SByte : IBinaryInteger
{
+ public static sbyte ReverseBits(sbyte value);
}

public readonly partial struct UInt16 : IBinaryInteger
{
+ public static ushort ReverseBits(ushort value);
}

public readonly partial struct Int16 : IBinaryInteger
{
+ public static short ReverseBits(short value);
}

public readonly partial struct UInt32 : IBinaryInteger
{
+ public static uint ReverseBits(uint value);
}

public readonly partial struct Int32 : IBinaryInteger
{
+ public static int ReverseBits(int value);
}

public readonly partial struct UInt64 : IBinaryInteger
{
+ public static ulong ReverseBits(ulong value);
}

public readonly partial struct Int64 : IBinaryInteger
{
+ public static long ReverseBits(long value);
}

public readonly partial struct UIntPtr : IBinaryInteger
{
+ public static nuint ReverseBits(nuint value);
}

public readonly partial struct IntPtr : IBinaryInteger
{
+ public static nint ReverseBits(nint value);
}

public readonly partial struct UInt128 : IBinaryInteger
{
+ public static UInt128 ReverseBits(UInt128 value);
}

public readonly partial struct Int128 : IBinaryInteger
{
+ public static Int128 ReverseBits(Int128 value);
}

public readonly partial struct Char : IBinaryInteger
{
+ static char IBinaryInteger.ReverseBits(char value);
}
```

## API Usage

```csharp
// Direct usage on primitive types
uint reversed = uint.ReverseBits(0x0000_0001u); // 0x8000_0000u
byte b = byte.ReverseBits(0xAA); // 0x55

// Generic math usage
T ReverseBitsGeneric(T value) where T : IBinaryInteger
=> T.ReverseBits(value);
```

## Design Decisions

**`static virtual` with DIM (not `static abstract`)**: The DIM writes the value's bytes, reverses bits within each byte, reverses byte order, and reads back. This is slower than the optimized implementations but works for any `IBinaryInteger` implementer without requiring them to override it.

**On `IBinaryInteger` (not `BitOperations`)**: This follows the generic math pattern established by `PopCount`, `RotateLeft`, `RotateRight`, `LeadingZeroCount`, and `TrailingZeroCount`. It enables generic programming over any integer type.

**Hardware intrinsics**: The `uint` and `ulong` implementations use `ArmBase.ReverseElementBits` (ARM `rbit` instruction) when available, with a software fallback using the standard bit-swap algorithm. All smaller/larger types delegate through these, so they benefit transitively. Methods are also marked `[Intrinsic]` for future JIT intrinsification.

**`BigInteger` uses the DIM**: The DIM reverses bits within the minimal two's complement byte representation. An optimized override could be added in a follow-up.

## Alternatives Considered

- **`BitOperations` static methods only**: The original proposal. Rejected per tannergooding's feedback — the generic math interface is the right home for this.
- **`static abstract` (no DIM)**: Would force all `IBinaryInteger` implementers to provide their own implementation. The DIM is acceptable despite being slower.

## Risks

- **No binary breaking changes**: This is purely additive.
- **Source breaking changes**: Extremely unlikely — `ReverseBits` is not a commonly-defined method name that would conflict with extension methods.
- **Performance**: The DIM is intentionally slower for unknown types. All built-in types have O(1) hardware-friendly implementations using ARM intrinsics where available.

## Prototype

Working prototype with tests: [`api-proposal/reverse-bits`](https://github.com/stephentoub/runtime/tree/api-proposal/reverse-bits)