Skip to content

Instantly share code, notes, and snippets.

@kleinron
Created May 8, 2023 19:47
Show Gist options
  • Save kleinron/0e5d6cf7e2394d478c409167adbdf4f4 to your computer and use it in GitHub Desktop.
Save kleinron/0e5d6cf7e2394d478c409167adbdf4f4 to your computer and use it in GitHub Desktop.
private static char[] digits = new[]
{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
public static char ToChar(int digit)
{
return digits[digit];
}
public static int div10(int n)
{
int q, r;
q = (n >> 1) + (n >> 2);
q = q + (q >> 4);
q = q + (q >> 8);
q = q + (q >> 16);
q = q >> 3;
r = n - q * 10;
return q + ((r + 6) >> 4);
}
var digitCount = (int)Math.Ceiling(Math.Log10(value));
public class V1
{
public static string ToDecimalString(int value)
{
if (value == 0)
return "0";
var list = new List<char>(1);
while (value != 0)
{
var digitAsInt = value%10;
var digitAsChar = (char) ('0' + digitAsInt);
list.Add(digitAsChar);
value /= 10;
}
list.Reverse();
return new string(list.ToArray());
}
}
public static string ToDecimalString(int value)
{
if (value == 0)
return "0";
var log10 = Math.Log10(value);
var digitCount = (int) Math.Ceiling(log10);
//fix if needed for the values of 10^n (10, 100, etc.)
if (digitCount == (int)log10)
++digitCount;
var chars = new char[digitCount];
for (var k = chars.Length - 1; k >= 0 ; --k)
{
var mod = value%10;
chars[k] = (char) ('0' + mod);
value /= 10;
}
return new string(chars);
}
private static int[] powersOf10 = new int[]
{
1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000, 1000000000
};
public static string ToDecimalString(int value)
{
if (value == 0)
return "0";
var index = Array.BinarySearch(powersOf10, value);
if (index < 0)
index = ~index; // not found, get closest index
else
++index;
var digitCount = index;
var chars = new char[digitCount];
for (var k = chars.Length - 1; k >= 0; --k)
{
var mod = value % 10;
chars[k] = (char) ('0' + mod);
value /= 10;
}
return new string(chars);
}
public class V4
{
private static readonly int[] powersOf10 = new int[]
{
1, 10, 100, 1000, 10000, 100000, 1000000,
10000000, 100000000, 1000000000
};
private static readonly int[] powersOf2 = new int[]
{
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,
2048, 4096, 8192, 16384, 32768, 65536, 131072,
262144, 524288, 1048576, 2097152, 4194304,
8388608, 16777216, 33554432, 67108864,
134217728, 268435456, 536870912, 1073741824
};
private static int[] decimalDigitsByMsb;
static V4()
{
decimalDigitsByMsb = new int[powersOf2.Length];
for (int k = 1; k < powersOf2.Length; k++)
{
decimalDigitsByMsb[k] = powersOf2[k - 1].ToString().Length;
}
}
public static string ToDecimalString(int value)
{
var mostSignificantBit = 0;
for (int k = powersOf2.Length - 1; k >= 0; k--)
{
var bit = (value & powersOf2[k]) != 0;
if (bit)
{
mostSignificantBit = k + 1;
break;
}
}
if (mostSignificantBit == 0)
return "0";
int index;
if (mostSignificantBit >= decimalDigitsByMsb.Length)
index = decimalDigitsByMsb[decimalDigitsByMsb.Length - 1];
else
index = decimalDigitsByMsb[mostSignificantBit];
if (value >= powersOf10[index])
index++;
var digitCount = index;
var chars = new char[digitCount];
for (var k = chars.Length - 1; k >= 0; --k)
{
var mod = value%10;
chars[k] = (char) ('0' + mod);
value /= 10;
}
return new string(chars);
}
}
public static string ToDecimalString(int value)
{
// ...
// old code remains the same
// ...
var chars = new char[digitCount];
for (var k = chars.Length - 1; k != (-1); --k)
{
// inline the div10 operation
int q, r;
q = (value >> 1) + (value >> 2);
q = q + (q >> 4);
q = q + (q >> 8);
q = q + (q >> 16);
q = q >> 3;
r = value - q * 10;
var valueDiv10 = q + ((r + 6) >> 4);
var mod = value - (valueDiv10 * 10);
chars[k] = digits[mod];
value = valueDiv10;
}
return new string(chars);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment