Shifting set bits in a UInt64 to the right of their respective bytes

Question

I have a UInt64 value with some bits on and some off e.g.:

01010101 01010101 01010101 01010101 01010101 01010101 01010101 01010101

How can I easily shift the set bits to the right, such they are to the right end of their respective bytes e.g:

00001111 00001111 00001111 00001111 00001111 00001111 00001111 00001111

I've seen questions which move the on bits all the way to the right of the 64 bit unsigned integer, but I only want to shift them to the right of the byte in which they lie if possible.

Thanks.

Answer 1

using System;
using System.Linq;

namespace ConsoleApplication5
{
  public class Program
  {
    public static void Main(String[] args)
    {
      var inputAsBinaryString = "01010101 01010101 01010101 01010101 01010101 01010101 01010101 01010101";
      var inputAsUInt64 = GetBinaryStringAsUInt64(inputAsBinaryString);

      var actualAsUInt64 = GetRightAlignedBytes(inputAsUInt64);
      var actualAsBinaryString = GetAsBinaryString(actualAsUInt64);

      var expectedAsBinaryString = "00001111 00001111 00001111 00001111 00001111 00001111 00001111 00001111";
      var expectedAsUInt64 = GetBinaryStringAsUInt64(expectedAsBinaryString);
    } // <-- Set a breakpoint here and inspect the values.

    /* Bit-manipulation methods. */

    private static UInt64 GetRightAlignedBytes(UInt64 n)
    {
      var rightAlignedByteArray =
        BitConverter
        .GetBytes(n)
        .Select(b => GetRightAlignedByte(b))
        .ToArray();
      return BitConverter.ToUInt64(rightAlignedByteArray, 0);
    }

    /* Shove all of a byte's bits to the right. */
    private static Byte GetRightAlignedByte(Byte b)
    {
      /* The << operator only works on 32 and 64 bit values.
         This requires treating the result as an Int32 until it's returned. */
      Int32 result = 0;
      var numberOfSetBits = GetNumberOfSetBits(b);

      for (Byte n = 1; n <= numberOfSetBits; n++)
      {
        /* Need to set n bits, but only perform n - 1 left shifts. */

        result |= 1;

        if (n < numberOfSetBits)
          result = result << 1;
      }

      return (Byte) result;
    }

    private static Byte GetNumberOfSetBits(Byte b)
    {
      /* There are many ways to count the number of "set" bits in a byte.

         This StackOverflow question

           http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer

         has a mind-numbing collection of answers.
         Most of them are probably more efficient than this method. */

      Int32 result = 0;

      /* The >> operator only works on 32 and 64 bit values.
         This requires converting the Byte parameter "b" to an Int32. */
      Int32 n = b;

      while (n > 0)
      {
        result += (n & 1);
        n = n >> 1;
      }

      return (Byte) result;
    }

    /* GetBinaryStringAs* methods */

    private static Int32 GetBinaryStringAsInt32(String s)
    {
      return Convert.ToInt32(String.Join("", s.Trim().Where(c => (c == '0') || (c == '1'))), 2);
    }

    private static UInt64 GetBinaryStringAsUInt64(String s)
    {
      return Convert.ToUInt64(String.Join("", s.Trim().Where(c => (c == '0') || (c == '1'))), 2);
    }

    /* GetAsBinaryString methods. */

    private static String GetAsBinaryString_Helper(Byte[] bytes)
    {
      /* The order of the bytes returned by System.BitConverter.GetBytes()
         depends on the CPU architecture.  The returned byte array
         will round-trip with other BitConverter methods, like its
         ToInt32() method.  But those same bytes will not round-trip
         with any of the System.Convert methods, like ToInt32(String, Int32).

         The System.Convert.To* methods expect the order of the bytes they
         receive to be the *reverse* of the order returned by
         System.BitConverter.GetBytes().

         The value returned by this method can - after stripping off the spaces -
         be fed into a System.Convert.To*() method.

         For example, this round-trip test should print "True":

                         // Hi byte                    Lo byte
          Int32 n = 257; // 00000000 00000000 00000001 00000001
          Console.WriteLine(GetBinaryStringAsInt32(GetAsBinaryString(n)) == n);

       */

      return String.Join(" ", bytes.Reverse().Select(b => GetAsBinaryString(b)));
    }

    private static String GetAsBinaryString(Int32 n)
    {
      /* Note that signed integers use two's complement
         binary representation for negative numbers.

         For example, calling this method with a parameter
         of -42 returns this string:

          11111111 11111111 11111111 11010110

       */
      return GetAsBinaryString_Helper(BitConverter.GetBytes(n));
    }

    private static String GetAsBinaryString(UInt64 n)
    {
      return GetAsBinaryString_Helper(BitConverter.GetBytes(n));
    }

    private static String GetAsBinaryString(Byte n)
    {
      return Convert.ToString(n, 2).PadLeft(8, '0');
    }
  }
}