BigInteger to Hex/Decimal/Octal/Binary strings?

Question

In Java, I could do

BigInteger b = new BigInteger(500);

Then format it as I pleased

b.toString(2); //binary
b.toString(8); //octal
b.toString(10); //decimal
b.toString(16); //hexadecimal

In C#, I can do

int num = int.Parse(b.ToString());
Convert.ToString(num,2) //binary
Convert.ToString(num,8) //octal

etc. But I can only do it with long values and smaller. Is there some method to print a BigInteger with a specified base? I posted this, BigInteger Parse Octal String?, yesterday and received the solution of how to convert basically all strings to BigInteger values, but haven't had success outputting.

Answer 1

Convert BigInteger to decimal, hex, binary, octal string:

Let's start with a BigInteger value:

BigInteger bigint = BigInteger.Parse("123456789012345678901234567890");

Base 10 and Base 16

The built-in Base 10 (decimal) and base 16 (hexadecimal) conversions are easy:

// Convert to base 10 (decimal):
string base10 = bigint.ToString();

// Convert to base 16 (hexadecimal):
string base16 = bigint.ToString("X");

Leading Zeros (positive vs. negative BigInteger values)

Take note, that ToString("X") ensures hexadecimal strings have a leading zero when the value of BigInteger is positive. This is unlike the usual behavior of ToString("X") when converting from other value types where leading zeros are suppressed.

EXAMPLE:

var positiveBigInt = new BigInteger(128);
var negativeBigInt = new BigInteger(-128);
Console.WriteLine(positiveBigInt.ToString("X"));
Console.WriteLine(negativeBigInt.ToString("X"));

RESULT:

080
80

There is a purpose for this behavior as a leading zero indicates the BigInteger is a positive value--essentially, the leading zero provides the sign. This is necessary (as opposed to other value type conversions) because a BigInteger has no fixed size; therefore, there is no designated sign bit. The leading zero identifies a positive value, as opposed to a negative one. This allows for "round-tripping" BigInteger values out through ToString() and back in through Parse(). This behavior is discussed on the BigInteger Structure page on MSDN.

Extension methods: BigInteger to Binary, Hex, and Octal

Here is a class containing extension methods to convert BigInteger instances to binary, hexadecimal, and octal strings:

using System;
using System.Numerics;
using System.Text;

/// <summary>
/// Extension methods to convert <see cref="System.Numerics.BigInteger"/>
/// instances to hexadecimal, octal, and binary strings.
/// </summary>
public static class BigIntegerExtensions
{
  /// <summary>
  /// Converts a <see cref="BigInteger"/> to a binary string.
  /// </summary>
  /// <param name="bigint">A <see cref="BigInteger"/>.</param>
  /// <returns>
  /// A <see cref="System.String"/> containing a binary
  /// representation of the supplied <see cref="BigInteger"/>.
  /// </returns>
  public static string ToBinaryString(this BigInteger bigint)
  {
    var bytes = bigint.ToByteArray();
    var idx = bytes.Length - 1;

    // Create a StringBuilder having appropriate capacity.
    var base2 = new StringBuilder(bytes.Length * 8);

    // Convert first byte to binary.
    var binary = Convert.ToString(bytes[idx], 2);

    // Ensure leading zero exists if value is positive.
    if (binary[0] != '0' && bigint.Sign == 1)
    {
      base2.Append('0');
    }

    // Append binary string to StringBuilder.
    base2.Append(binary);

    // Convert remaining bytes adding leading zeros.
    for (idx--; idx >= 0; idx--)
    {
      base2.Append(Convert.ToString(bytes[idx], 2).PadLeft(8, '0'));
    }

    return base2.ToString();
  }

  /// <summary>
  /// Converts a <see cref="BigInteger"/> to a hexadecimal string.
  /// </summary>
  /// <param name="bigint">A <see cref="BigInteger"/>.</param>
  /// <returns>
  /// A <see cref="System.String"/> containing a hexadecimal
  /// representation of the supplied <see cref="BigInteger"/>.
  /// </returns>
  public static string ToHexadecimalString(this BigInteger bigint)
  {
    return bigint.ToString("X");
  }

  /// <summary>
  /// Converts a <see cref="BigInteger"/> to a octal string.
  /// </summary>
  /// <param name="bigint">A <see cref="BigInteger"/>.</param>
  /// <returns>
  /// A <see cref="System.String"/> containing an octal
  /// representation of the supplied <see cref="BigInteger"/>.
  /// </returns>
  public static string ToOctalString(this BigInteger bigint)
  {
    var bytes = bigint.ToByteArray();
    var idx = bytes.Length - 1;

    // Create a StringBuilder having appropriate capacity.
    var base8 = new StringBuilder(((bytes.Length / 3) + 1) * 8);

    // Calculate how many bytes are extra when byte array is split
    // into three-byte (24-bit) chunks.
    var extra = bytes.Length % 3;

    // If no bytes are extra, use three bytes for first chunk.
    if (extra == 0)
    {
      extra = 3;
    }

    // Convert first chunk (24-bits) to integer value.
    int int24 = 0;
    for (; extra != 0; extra--)
    {
      int24 <<= 8;
      int24 += bytes[idx--];
    }

    // Convert 24-bit integer to octal without adding leading zeros.
    var octal = Convert.ToString(int24, 8);

    // Ensure leading zero exists if value is positive.
    if (octal[0] != '0' && bigint.Sign == 1)
    {
      base8.Append('0');
    }

    // Append first converted chunk to StringBuilder.
    base8.Append(octal);

    // Convert remaining 24-bit chunks, adding leading zeros.
    for (; idx >= 0; idx -= 3)
    {
      int24 = (bytes[idx] << 16) + (bytes[idx - 1] << 8) + bytes[idx - 2];
      base8.Append(Convert.ToString(int24, 8).PadLeft(8, '0'));
    }

    return base8.ToString();
  }
}

On first glance, these methods may seem more complex than necessary. A bit of extra complexity is, indeed, added to ensure the proper leading zeros are present in the converted strings.

Let's examine each extension method to see how they work:

BigInteger.ToBinaryString()

Here is how to use this extension method to convert a BigInteger to a binary string:

// Convert BigInteger to binary string.
bigint.ToBinaryString();

The fundamental core of each of these extension methods is the BigInteger.ToByteArray() method. This method converts a BigInteger to a byte array, which is how we can get the binary representation of a BigInteger value:

var bytes = bigint.ToByteArray();

Beware, though, the returned byte array is in little-endian order, so the first array element is the least-significant byte (LSB) of the BigInteger. Since a StringBuilder is used to build the output string--which starts at the most-significant digit (MSB)--the byte array must be iterated in reverse so that the most-significant byte is converted first.

Thus, an index pointer is set to the most significant digit (the last element) in the byte array:

var idx = bytes.Length - 1;

To capture the converted bytes, a StringBuilder is created:

var base2 = new StringBuilder(bytes.Length * 8);

The StringBuilder constructor takes the capacity for the StringBuilder. The capacity needed for the StringBuilder is calculated by taking the number of bytes to convert multiplied by eight (eight binary digits result from each byte converted).

The first byte is then converted to a binary string:

var binary = Convert.ToString(bytes[idx], 2);

At this point, it is necessary to ensure that a leading zero exists if the BigInteger is a positive value (see discussion above). If the first converted digit is not a zero, and bigint is positive, then a '0' is appended to the StringBuilder:

// Ensure leading zero exists if value is positive.
if (binary[0] != '0' && bigint.Sign == 1)
{
  base2.Append('0');
}

Next, the converted byte is appended to the StringBuilder:

base2.Append(binary);

To convert the remaining bytes, a loop iterates the remainder of the byte array in reverse order:

for (idx--; idx >= 0; idx--)
{
  base16.Append(Convert.ToString(bytes[idx], 2).PadLeft(8, '0'));
}

Notice that each converted byte is padded on the left with zeros ('0'), as necessary, so that the converted string is eight binary characters. This is extremely important. Without this padding, the hexadecimal value '101' would be converted to a binary value of '11'. The leading zeros ensure the conversion is '100000001'.

When all bytes are converted, the StringBuilder contains the complete binary string, which is returned by the extension method:

return base2.ToString();

BigInteger.ToOctalString

Converting a BigInteger to an octal (base 8) string is more complicated. The problem is octal digits represent three bits which is not an even multiple of the eight bits held in each element of the byte array created by BigInteger.ToByteArray(). To solve this problem, three bytes from the array are combined into chunks of 24-bits. Each 24-bit chunk evenly converts to eight octal characters.

The first 24-bit chunk requires some modulo math:

var extra = bytes.Length % 3;

This calculation determines how many bytes are "extra" when the entire byte array is split into three-byte (24-bit) chunks. The first conversion to octal (the most-significant digits) gets the "extra" bytes so that all remaining conversions will get three bytes each.

If there are no "extra" bytes, then the first chunk gets a full three bytes:

if (extra == 0)
{
  extra = 3;
}

The first chunk is loaded into an integer variable called int24 that holds up to 24-bits. Each byte of the chunk is loaded. As additional bytes are loaded, the previous bits in int24 are left-shifted by 8-bits to make room:

int int24 = 0;
for (; extra != 0; extra--)
{
  int24 <<= 8;
  int24 += bytes[idx--];
}

Conversion of a 24-bit chunk to octal is accomplished by:

var octal = Convert.ToString(int24, 8);

Again, the first digit must be a leading zero if the BigInteger is a positive value:

// Ensure leading zero exists if value is positive.
if (octal[0] != '0' && bigint.Sign == 1)
{
  base8.Append('0');
}

The first converted chunk is appended to the StringBuilder:

base8.Append(octal);

The remaining 24-bit chunks are converted in a loop:

for (; idx >= 0; idx -= 3)
{
  int24 = (bytes[idx] << 16) + (bytes[idx -1] << 8) + bytes[idx - 2];
  base8.Append(Convert.ToString(int24, 8).PadLeft(8, '0'));
}

Like the binary conversion, each converted octal string is left-padded with zeros so that '7' becomes '00000007'. This ensures that zeros won't be dropped from the middle of converted strings (i.e., '17' instead of '100000007').

Conversion to Base x?

Converting a BigInteger to other number bases could be far more complicated. As long as the number base is a power of two (i.e., 2, 4, 8, 16) the byte array created by BigInteger.ToByteArray() can be appropriately split into chunks of bits and converted.

However, if the number base is not a power of two, the problem becomes much more complicated and requires a good deal of looping and division. As such number base conversions are rare, I have only covered the popular computing number bases here.

Answer 2

After a good long day of working with BigInteger, I got a better way of doing things to output the string in binary, try this! (works for negative numbers)

// Important note: when parsing hexadecimal string, make sure to prefix
// with 0 if the number is positive. Ex: 0F instead of F, and 01A3 instead of 1A3.
// If the number is negative, then the first bit should be set to 1.

var x = BigInteger.Parse("0F", NumberStyles.HexNumber); // Or: BigInteger.Parse("15")

var biBytes = x.ToByteArray();

var bits = new bool [8 * biBytes.Length];

new BitArray(x.ToByteArray()).CopyTo(bits, 0);

bits = bits.Reverse().ToArray(); // BigInteger uses little endian when extracting bytes (thus bits), so we inverse them.

var builder = new StringBuilder();

foreach(var bit in bits)
{
    builder.Append(bit ? '1' : '0');
}

string final = Regex.Replace(builder.ToString(), @"^0+", ""); // Because bytes consume full 8 bits, we might occasionally get leading zeros.

Console.WriteLine(final);

Output: 1111