Skip to content

Instantly share code, notes, and snippets.

@Kittoes0124
Last active April 13, 2024 14:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Kittoes0124/30d5ee50574820bd723a5c00c9b69919 to your computer and use it in GitHub Desktop.
Save Kittoes0124/30d5ee50574820bd723a5c00c9b69919 to your computer and use it in GitHub Desktop.
using System.Numerics;
var w = BinaryIntegerFunctions.ComputeMagicConstant<ushort>();
Console.WriteLine($"{w} {Convert.ToString((long)w, 2)}");
var x = BinaryIntegerFunctions.ComputeMagicConstant<uint>();
Console.WriteLine($"{x} {Convert.ToString(x, 2)}");
var y = BinaryIntegerFunctions.ComputeMagicConstant<ulong>();
Console.WriteLine($"{y} {Convert.ToString((long)y, 2)}");
var z = BinaryIntegerFunctions.ComputeMagicConstant<UInt128>();
Console.WriteLine($"{z} {Convert.ToString((long)z, 2)}");
public static class BinaryIntegerConstants<T> where T : IBinaryInteger<T>
{
public static T Size { get; }
static BinaryIntegerConstants() {
var size = T.PopCount(value: T.AllBitsSet);
Size = size;
}
}
public static class BinaryIntegerFunctions
{
public static T ComputeMagicConstant<T>() where T : IBinaryInteger<T> {
var @base = (T.One << 8);
var limit = (T.One << 1);
var power = T.Zero;
var size = uint.CreateChecked(value: ((BinaryIntegerConstants<T>.Size >> 4) + T.One));
var result = T.Zero;
for (var i = 0U; (i < size); ++i) {
limit *= @base.Exponentiate(exponent: (T.One << 1));
power *= @base.Exponentiate(exponent: (T.One << 1));
result *= @base;
while ((power + (result << 1) + T.One) <= limit) {
power += ((result << 1) + T.One);
result += T.One;
}
}
return (result / @base);
}
public static T Exponentiate<T>(this T value, T exponent) where T : IBinaryInteger<T> {
var result = T.One;
do {
if (T.IsOddInteger(value: exponent)) {
result *= value;
}
exponent >>= 1;
value *= value;
} while (T.Zero < exponent);
return result;
}
}
/*
Expected output:
255 11111111 <-- WRONG!
19195 100101011111011
1257966796 1001010111110110000110011001100
5402926248376769403 100101011111011000011001100110000000110001000011001101101111011
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment