[API Proposal]: BitOperations.ReverseBits

[saucecontrol]

Background and motivation

This is defined and used a few places in the runtime and libs: https://github.com/search?q=repo%3Adotnet%2Fruntime%20ReverseBits&type=code

It would be generally useful to expose it publicly in BitOperations.

This operation can be hardware accelerated on Arm64 (rbit) and recent x86/64 (GFNI or AVX512_BMM).

API Proposal

namespace System.Numerics;

public static class BitOperations
{
    public static byte ReverseBits(byte value);
    public static ushort ReverseBits(ushort value);
    public static uint ReverseBits(uint value);
    public static ulong ReverseBits(ulong value);
    public static nuint ReverseBits(nuint value);
}

API Usage

uint xrev = BitOperations.ReverseBits(x);

Alternative Designs

Could consider signed and/or smaller type overloads

[dotnet-policy-service]

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

[vcsjones]

smaller type overloads

There a few places in S.S.Cryptography where doing it on a byte would be helpful. For example:

runtime/src/libraries/System.Security.Cryptography/src/System/Security/Cryptography/X509Certificates/X509KeyUsageExtension.cs

Line 107 in edd2a2a

private static byte ReverseBitOrder(byte b) => (byte)(unchecked(b * 0x0202020202ul & 0x010884422010ul) % 1023);

I don't know one way or another if it can or should be an intrinsic but it would seem neater to round out the API.

[stephentoub]

@tannergooding:

• Is BitOperations the right place for such operations? I've lost track of whether we'd want it there or promoted to the generic math interfaces or somewhere else.
• If not in the math interfaces, any reason we wouldn't want a UInt128 overload as well?

[tannergooding]

I think we would want this on the math interfaces (IBinaryInteger in particular), just with noting the DIM would be slower here (which is acceptable) as it functionally has to write the bytes, reverse the bits of the bytes, and then read those bits back. I'm not aware of an optimized trick that will work otherwise for any integer.

[kevincathcart-cas]

Putting it on IBinaryInteger does come with the consideration that with that variable sized binary integers (like BigInteger) the output could give some unexpected results. Notably reversing bits twice might could up with a different value than you started with. This wouldn't be the only method in that interface which gives results that could be unexpected when using such types, although this one does seem to be a bit more striking than some of the other oddities.

Unlikely to be a showstopper, but thought it was worth pointing out.

[stephentoub]

Note

This comment was generated with AI (GitHub Copilot).

Revised API Proposal: IBinaryInteger<TSelf>.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<byte>) — 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() 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, this is placed on IBinaryInteger<TSelf> as a static virtual method with a default interface method (DIM), rather than on BitOperations.

namespace System.Numerics;

public interface IBinaryInteger<TSelf> : IBinaryNumber<TSelf>, IShiftOperators<TSelf, int, TSelf>
    where TSelf : IBinaryInteger<TSelf>?
{
    // 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:

namespace System;

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

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

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

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

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

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

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

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

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

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

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

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

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

API Usage

// 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>(T value) where T : IBinaryInteger<T>
    => 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<TSelf> implementer without requiring them to override it.

On IBinaryInteger<TSelf> (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