5 ms·
Not sure if this counts, but I got tired of seeing all of the magic constants used in several of these tricks and not understanding how they were generated. Cam
by kittoes 2y ago
Not sure if this counts, but I got tired of seeing all of the magic constants used in several of these tricks and not understanding how they were generated. Came up with the following via trial and error:
static T NthFermatMask<T>(this int value) where T : IBinaryInteger<T> {
var x = T.AllBitsSet;
var y = T.IsNegative(value: x).As<int>();
return ((((x >>> y) / value.NthFermatNumber<T>()) << y) | T.One);
}
static T NthFermatNumber<T>(this int value) where T : IBinaryInteger<T> {
return ((T.One << (1 << value)) + T.One);
}
NthFermatNumber generates the nth Fermat number (see https://oeis.org/A000215 https://oeis.org/A000215) and NthFermatMask generates magic constants of the form 0x55555555, 0x33333333, 0x0F0F0F0F, etc. To demonstrate usage, here is a generic interleave bits implementation:
public static TResult BitwisePair<TInput, TResult>(this TInput value, TInput other) where TInput : IBinaryInteger<TInput> where TResult : IBinaryInteger<TResult> {
switch (value) {
case short:
case ushort:
if (Bmi2.IsSupported) {
return (
TResult.CreateTruncating(value: Bmi2.ParallelBitDeposit(mask: 0.NthFermatMask<uint>(), value: uint.CreateTruncating(value: value))) |
TResult.CreateTruncating(value: Bmi2.ParallelBitDeposit(mask: (0.NthFermatMask<uint>() << 1), value: uint.CreateTruncating(value: other)))
);
}
break;
case int:
case uint:
if (Bmi2.X64.IsSupported) {
return (
TResult.CreateTruncating(value: Bmi2.X64.ParallelBitDeposit(mask: 0.NthFermatMask<ulong>(), value: ulong.CreateTruncating(value: value))) |
TResult.CreateTruncating(value: Bmi2.X64.ParallelBitDeposit(mask: (0.NthFermatMask<ulong>() << 1), value: ulong.CreateTruncating(value: other)))
);
}
break;
default:
break;
}
const int loopOffset = 7;
int offset;
int shift;
var bitCountDividedByTwo = (int.CreateChecked(value: BinaryIntegerConstants<TResult>.Size) >> 1);
var evenBits = TResult.CreateTruncating(value: other);
var oddBits = TResult.CreateTruncating(value: value);
if (loopOffset.NthPowerOfTwo<int>() < bitCountDividedByTwo) {
var i = ((int.CreateChecked(value: BinaryIntegerConstants<TResult>.Log2Size) - loopOffset) - 1);
do {
offset = (i + (loopOffset - 1));
shift = offset.NthPowerOfTwo<int>();
DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift);
} while (0 < --i);
}
offset = 6; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); }
offset = 5; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); }
offset = 4; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); }
offset = 3; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); }
offset = 2; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); }
offset = 1; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); }
offset = 0; if ((shift = offset.NthPowerOfTwo<int>()) < bitCountDividedByTwo) { DistributeBits(evenBits: ref evenBits, oddBits: ref oddBits, offset: offset, shift: shift); }
return (oddBits | (evenBits << shift));
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void DistributeBits(int offset, int shift, ref TResult evenBits, ref TResult oddBits) {
var mask = offset.NthFermatMask<TResult>();
evenBits = ((evenBits | (evenBits << shift)) & mask);
oddBits = ((oddBits | (oddBits << shift)) & mask);
}
}