After posting a question about Alphanumeric Hash generation on StackOverflow, the most helpful answer was to change the conversion method from pulling 5-bit chunks of a binary hash value, to instead changing the number to base-36.
This is pretty straightforward; find the quotient and remainder of the number divided by 36, encode the remainder as the next most significant digit of the result, then repeat with the quotient.
Sounds great, except that if I want to start with an integer hash 128 bits or greater, I can't just use the divide operator. In that case, I have to use "long division":
Decimal:
18 R 3
__
5)93
-5
43
-40
3
Binary:
00010010 R 11
________
0101)01011101
-0101
0000110
-0101
00011
So, to base-36-encode a large integer, stored as a byte array, I have the following method, which performs the basic iterative algorithm for binary long division, storing the result in another byte array and returning the modulus as an output parameter:
public static byte[] DivideBy(this byte[] bytes, ulong divisor, out ulong mod, bool preserveSize = true)
{
//the byte array MUST be little-endian here or the operation will be totally fubared.
var bitArray = new BitArray(bytes);
ulong buffer = 0;
byte quotientBuffer = 0;
byte qBufferLen = 0;
var quotient = new List<byte>();
//the bitarray indexes its values in little-endian fashion;
//as the index increases we move from LSB to MSB.
for (var i = bitArray.Count - 1; i >= 0; --i)
{
//The basic idea is similar to decimal long division;
//starting from the most significant bit, take enough bits
//to form a number divisible by (greater than) the divisor.
buffer = (buffer << 1) + (ulong)(bitArray[i] ? 1 : 0);
if (buffer >= divisor)
{
//Now divide; buffer will never be >= divisor * 2,
//so the quotient of buffer / divisor is always 1...
quotientBuffer = (byte)((quotientBuffer << 1) + 1);
//then subtract the divisor from the buffer,
//to produce the remainder to be carried forward.
buffer -= divisor;
}
else
//to keep our place; if buffer < divisor,
//then by definition buffer / divisor == 0 R buffer.
quotientBuffer = (byte)(quotientBuffer << 1);
qBufferLen++;
if (qBufferLen == 8)
{
//preserveSize forces the output array to be the same number of bytes as the input;
//otherwise, insert only if we're inserting a nonzero byte or have already done so,
//to truncate leading zeroes.
if (preserveSize || quotient.Count > 0 || quotientBuffer > 0)
quotient.Add(quotientBuffer);
//reset the buffer
quotientBuffer = 0;
qBufferLen = 0;
}
}
//and when all is said and done what's left in our buffer is the remainder.
mod = buffer;
//The quotient list was built MSB-first, but we can't require
//a little-endian array and then return a big-endian one.
return quotient.AsEnumerable().Reverse().ToArray();
}
... which is then used by the (now pretty simple) base-36 encoder algorithm to iteratively divide the number by 36:
public static string ToBase36String(this IEnumerable<byte> toConvert, bool bigEndian = false)
{
//the "alphabet" for base-36 encoding is similar in theory to hexadecimal,
//but uses all 26 English letters a-z instead of just a-f.
var alphabet = new[]
{
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f',
'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
'w', 'x', 'y', 'z'
};
//most .NET-produced byte arrays are "little-endian" (LSB first),
//but MSB-first is more natural to read bitwise left-to-right;
//here, we can handle either way.
var bytes = bigEndian
? toConvert.Reverse().ToArray()
: toConvert.ToArray();
var builder = new StringBuilder();
while (bytes.Any(b => b > 0))
{
ulong mod;
bytes = bytes.DivideBy(36, out mod);
builder.Insert(0,alphabet[mod]);
}
return builder.ToString();
}
It's... passable, I guess. An N-bit number of initial magnitude M encodes in Nlog36M time which is pretty efficient, all things considered. Is there a faster basic method, or any glaring efficiency issues (I am doing a lot of conversions; byte array, to bit array, producing a list, reversing it, then converting to array)?
The division algorithm also doesn't handle division by a divisor longer than 64 bits (thus taking a byte array for the divisor), nor can it handle signed arithmetic. Are there any simple improvements to let it do so?
toConvert
... \$\endgroup\$