Byte extension methods for common bitwise operations

Question

I'd like to learn how I can optimize the following byte extension methods.

I'm targeting .NET Standard 2.0 but I'm curious if there are any ways to go about some of this functionality using features available in 2.1 (like Span<T>).

I feel like the ShiftRight, byte.HasSamePrefix, byte[].HasSamePrefix methods could be improved.

using System;

namespace SharpTorrent.Dht.Extensions
{
    /// <summary>
    /// This class provides static extension methods for the byte type.
    /// </summary>
    public static class ByteExtensions
    {
        /// <summary>
        /// Determine if the bit at the provided index is set (indexed from left-to-right).
        /// </summary>
        /// <param name="value">The byte whose index to check.</param>
        /// <param name="index">The bit index to check.</param>
        /// <returns>The mutated byte value</returns>
        public static bool IsBitSetAtIndex(
            this byte value
            , byte index
        ) => index > 7
            ? throw new IndexOutOfRangeException("Index must be between 0 and 7 inclusive.")
            : (value & (1 << 7 - index)) != 0;

        /// <summary>
        /// Set the bit value at the provided index (indexed from left-to-right).
        /// </summary>
        /// <param name="value">The byte value whose bit to set.</param>
        /// <param name="index">The index of the bit to set.</param>
        /// <returns>The mutated byte value</returns>
        public static byte SetBitAtIndex(
            this byte value
            , byte index
        ) => index > 7
            ? throw new IndexOutOfRangeException("Index must be between 0 and 7 inclusive.")
            : (byte) (value | (1 << 7 - index));

        /// <summary>
        /// Clear the bit value at the provided index (indexed from left-to-right).
        /// </summary>
        /// <param name="value">The byte value whose bit to clear.</param>
        /// <param name="index">The index of the bit to clear.</param>
        /// <returns>The mutated byte value</returns>
        public static byte ClearBitAtIndex(
            this byte value
            , byte index
        ) => index > 7
            ? throw new IndexOutOfRangeException("Index must be between 0 and 7 inclusive.")
            : (byte) (value & ~(1 << 7 - index));

        /// <summary>
        /// Toggle the bit value at the provided index (indexed from left-to-right).
        /// </summary>
        /// <param name="value">The byte value whose bit to toggle.</param>
        /// <param name="index">The index of the bit to toggle.</param>
        /// <returns>The mutated byte value</returns>
        public static byte ToggleBitAtIndex(
            this byte value
            , byte index
        ) => index > 7
            ? throw new IndexOutOfRangeException("Index must be between 0 and 7 inclusive.")
            : (byte) (value ^ (1 << 7 - index));


        /// <summary>
        /// Shift the bits of the provided byte array right by the provided distance. Bits will shift across byte
        /// boundaries in the array. Zero will be shifted in from the left. The sign of the byte array isn't considered.
        /// </summary>
        /// <param name="bytes">The byte array to shift.</param>
        /// <param name="distance">The distance to shift the bits.</param>
        /// <returns>The shifted byte array.</returns>
        public static byte[] ShiftRight(
            this byte[] bytes
            , uint distance = 1
        )
        {
            // For each index distance to shift the bits.
            for (var d = 0; d < distance; d++)
            {
                // For every byte in the array (MSB <- LSB).
                for (var i = bytes.Length - 1; i >= 0; i--)
                {
                    // Shift the current index right by one bit.
                    bytes[i] = (byte) (bytes[i] >> 1);

                    // Set the most significant bit if necessary.
                    if (i >= 1 && (bytes[i - 1] & 0x01) != 0)
                    {
                        bytes[i] |= (byte) (bytes[i] | 0x80);
                    }
                }
            }

            return bytes;
        }

        /// <summary>
        /// Mask off the the nth bit position of the byte starting from the left. Indexing is 0-based.
        /// 
        /// e.g. A value of 0xFF will produce the following:
        /// 
        /// 11111111 (0) -> 01111111
        /// 11111111 (1) -> 00111111
        /// 11111111 (2) -> 00011111
        /// 11111111 (3) -> 00001111
        /// 11111111 (4) -> 00000111
        /// 11111111 (5) -> 00000011
        /// 11111111 (6) -> 00000001
        /// 11111111 (7) -> 00000000
        /// </summary>
        /// <param name="value">The byte to mask.</param>
        /// <param name="maskIndex"></param>
        /// <returns>The masked byte value.</returns>
        public static byte MaskLeft(this byte value, byte maskIndex) => (byte) (value & (0xFF >> (maskIndex + 1)));

        /// <summary>
        /// Mask off the the nth bit position of the byte starting from the right. Indexing is 0-based.
        /// 
        /// e.g. A value of 0xFF will produce the following:
        /// 
        /// 11111111 (0) -> 11111110
        /// 11111111 (1) -> 11111100
        /// 11111111 (2) -> 11111000
        /// 11111111 (3) -> 11110000
        /// 11111111 (4) -> 11100000
        /// 11111111 (5) -> 11000000
        /// 11111111 (6) -> 10000000
        /// 11111111 (7) -> 00000000
        /// </summary>
        /// <param name="value"></param>
        /// <param name="maskIndex"></param>
        /// <returns></returns>
        public static byte MaskRight(this byte value, byte maskIndex) => (byte) (value & (0xFF << (maskIndex + 1)));


        /// <summary>
        /// Determine if two bytes share a common prefix from left-to-right. Indexing is 0-based.
        /// </summary>
        /// <param name="value">The first value.</param>
        /// <param name="second">The value to compare against.</param>
        /// <param name="bitIndex">The prefix index to check up to.</param>
        /// <returns>Whether or not the two bytes share a matching prefix.</returns>
        /// <exception cref="IndexOutOfRangeException">Thrown when a bit index greater than 7 is provided.</exception>
        public static bool HasSamePrefix(this byte value, byte second, byte bitIndex)
        {
            if (bitIndex > 7)
            {
                throw new IndexOutOfRangeException("Index must be between 0 and 7 inclusive.");
            }

            if (bitIndex == 7)
            {
                return value.IsBitSetAtIndex(7) == second.IsBitSetAtIndex(7);
            }

            var maskIndex = (byte) (6 - bitIndex);

            return value.MaskRight(maskIndex) == second.MaskRight(maskIndex);
        }

        /// <summary>
        /// Determine if the byte arrays share a common prefix from left-to-right. Indexing is 0-based.
        /// </summary>
        /// <param name="first">The first byte array.</param>
        /// <param name="second">The byte array to compare against.</param>
        /// <param name="bitIndex">The bit index to check up to.</param>
        /// <returns></returns>
        /// <exception cref="IndexOutOfRangeException">
        /// Thrown when the bit index is greater than the number of bits in the smallest byte array.
        /// </exception>
        public static bool HasSamePrefix(
            this byte[] first
            , byte[] second
            , int bitIndex
        )
        {
            var maxIndex = Math.Min(first.Length, second.Length) - 1;
            var endByteIndex = bitIndex / 8;
            var byteIndex = 0;

            if (endByteIndex > maxIndex)
            {
                throw new IndexOutOfRangeException("Bit index exceeds bit index of smallest array.");
            }

            for (; byteIndex < endByteIndex; byteIndex++)
            {
                if (first[byteIndex] != second[byteIndex])
                {
                    return false;
                }
            }

            return first[byteIndex].HasSamePrefix(
                second[byteIndex]
                , (byte) (7 - bitIndex % 8)
            );
        }
    }
}

Answer 1

ShiftRight does not need to be a series of shift-by-1 operations.

An other approach is:

1. shift whole bytes, by a distance of distance / 8
2. shift the bytes by distance % 8, while shifting in bits from the next byte

I have to be a little careful here because you used an unsual byte order (lowest order byte last) and you're doing this in-place. Here's an attempt (not debugged):

// move bytes to shift by multiples of 8
int byteDistance = (int)(distance / 8);
for (int i = bytes.Length - 1; i >= byteDistance; i--)
{
    bytes[i] = bytes[i - byteDistance];
}
// zero out the "top" of the array
for (int i = byteDistance - 1; i >= 0; i--)
{
    bytes[i] = 0;
}

// bit-granular shift by the remainder of the distance
int bitShift = (int)(distance % 8);
for (int i = bytes.Length - 1; i >= 1; i--)
{
    int twoBytes = bytes[i] | (bytes[i - 1] << 8);
    bytes[i] = (byte)(twoBytes >> bitShift);
}
bytes[0] >>= bitShift;

Some variants may be interesting:

• The last loop can iterate less, stopping at the part of the array that was left zero by the byte-granular shift.
• The last loop could be unrolled, packing more bytes into an int and making "better use" of the integer shift.
• With Span<T> and primarily targeting 64bit, we could MemoryMarshal.Cast the Span<byte> to an Span<uint>, then do a similar thing as above but with two uint in an ulong rather than two byte in an int. It takes some care with arrays with length not a multiple of 4, of course.

Notable non-possibility:

• An other new thing in Standard 2.1 thing is System.Numerics.Vector, but it still lacks bit-shifts (I've heard they will probably be added someday), so it can't be used for this, even though the hardware can do it.

Answer 2

Review

• The postfix AtIndex is too verbose. You don't have any other operations like AtMask or anything and the index is provided as argument. So I would prefer IsBitSet over IsBitSetAtIndex etc.
• The index is sometimes a byte, sometimes a uint. I would not bother with such level of (over-)engineered type picks. Stick with the common type for an index int. You can always add argument checks for bounds.
• You can replace 1 << 7 - index with 1 << index in your operations. This is written more compactly and is a well known bit operation technique. Right-to-left indexes are more common in bitwise systems.