rd-net/Lifetimes/Util/BitHacks.cs (177 lines of code) (raw):
using System;
using System.Numerics;
using System.Runtime.CompilerServices;
namespace JetBrains.Util
{
/// <summary>
/// Inspired by http://graphics.stanford.edu/~seander/bithacks.html
/// </summary>
public static class BitHacks
{
#if !NET5_0_OR_GREATER
// de Bruijn multiplication, see http://supertech.csail.mit.edu/papers/debruijn.pdf
private const uint DeBruijnSequence32 = 0x07C4ACDD;
private const ulong DeBruijnSequence64 = 0x03F79D71B4CB0A89;
private static readonly byte[] ourDeBruijnBitTable32 = {
0, 9, 1, 10, 13, 21, 2, 29,
11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7,
19, 27, 23, 6, 26, 5, 4, 31
};
private static readonly byte[] ourDeBruijnBitTable64 = {
0, 47, 1, 56, 48, 27, 2, 60,
57, 49, 41, 37, 28, 16, 3, 61,
54, 58, 35, 52, 50, 42, 21, 44,
38, 32, 29, 23, 17, 11, 4, 62,
46, 55, 26, 59, 40, 36, 15, 53,
34, 51, 20, 43, 31, 22, 10, 45,
25, 39, 14, 33, 19, 30, 9, 24,
13, 18, 8, 12, 7, 6, 5, 63
};
#endif
/// <summary>
/// Returns the integer (floor) log of the specified value, base 2.
/// </summary>
/// <returns><c>y : 2^y<=x</c></returns>
public static int Log2Floor(uint x)
{
#if NET5_0_OR_GREATER
return BitOperations.Log2(x);
#else
return ReverseBitScan(x);
#endif
}
/// <summary>
/// Returns largest non-negative integer <c>y</c> such that <c>2^y<=x</c> if <c>x>0</c>, <c>0</c> if <c>x=0</c>, or throw ArgumentException if <c>x<0</c>
/// </summary>
/// <param name="x">Must be greater than or equal to zero.</param>
/// <returns><c>y : 2^y<=x</c></returns>
public static int Log2Floor(int x)
{
if (x < 0) throw new ArgumentException("x must be greater than 0");
return Log2Floor((uint)x);
}
/// <summary>
/// Returns the integer (floor) log of the specified value, base 2.
/// </summary>
/// <param name="x">Must be greater than or equal to zero.</param>
/// <returns><c>y : 2^y<=x</c></returns>
public static int Log2Floor(ulong x)
{
#if NET5_0_OR_GREATER
return BitOperations.Log2(x);
#else
return ReverseBitScan(x);
#endif
}
/// <summary>
/// Returns largest non-negative integer <c>y</c> such that <c>2^y<=x</c> if <c>x>0</c>, <c>0</c> if <c>x=0</c>, or throw ArgumentException if <c>x<0</c>
/// </summary>
/// <param name="x">Must be greater than or equal to zero.</param>
/// <returns><c>y : 2^y<=x</c></returns>
public static int Log2Floor(long x)
{
if (x < 0) throw new ArgumentException("x must be greater than 0");
return Log2Floor((ulong)x);
}
/// <summary>
/// Returns lowest non-negative integer <c>y</c> such that <c>2^y>=x</c> if <c>x>=0</c> or throw ArgumentException if <c>x<0</c>
/// </summary>
/// <param name="x">Must be greater than or equal to zero.</param>
/// <returns><c>y : 2^y>=x</c></returns>
public static int Log2Ceil(int x)
{
if (x < 0) throw new ArgumentException("x must be greater than 0");
return Log2Ceil((uint)x);
}
/// <summary>Returns the integer (ceiling) log of the specified value, base 2.</summary>
/// <param name="value">The value.</param>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Log2Ceil(uint value)
{
if (value == 0) return 0;
#if NET5_0_OR_GREATER
int result = Log2Floor(value);
if (PopCount(value) != 1)
{
result++;
}
return result;
#else
var log2Floor = ReverseBitScan(value);
if (1U << log2Floor == value) return log2Floor;
return log2Floor + 1;
#endif
}
/// <summary>
/// Returns lowest non-negative integer <c>y</c> such that <c>2^y>=x</c> if <c>x>=0</c> or throw ArgumentException if <c>x<0</c>
/// </summary>
/// <param name="x">Must be greater than or equal to zero.</param>
/// <returns><c>y : 2^y>=x</c></returns>
public static int Log2Ceil(long x)
{
if (x < 0) throw new ArgumentException("x must be greater than 0");
if (x == 0) return 0;
#if NET5_0_OR_GREATER
var result = Log2Floor(x);
if (PopCount((ulong)x) != 1)
{
result++;
}
return result;
#else
var log2Floor = ReverseBitScan((ulong)x);
if (1UL << log2Floor == (ulong)x) return log2Floor;
return log2Floor + 1;
#endif
}
/// <summary>
/// Return number of <c>1</c>-s in binary representation of <c>x</c>
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
[MethodImpl(MethodImplAdvancedOptions.AggressiveInlining)]
public static int NumberOfBitSet(int x)
{
#if NET5_0_OR_GREATER
return BitOperations.PopCount((uint)x);
#else
unchecked
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
return ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
#endif
}
/// <summary>
/// Return number of <c>1</c>-s in binary representation of <c>x</c>
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
[MethodImpl(MethodImplAdvancedOptions.AggressiveInlining)]
public static int PopCount(uint x)
{
#if NET5_0_OR_GREATER
return BitOperations.PopCount(x);
#else
unchecked
{
const uint c1 = 0x_55555555u;
const uint c2 = 0x_33333333u;
const uint c3 = 0x_0F0F0F0Fu;
const uint c4 = 0x_01010101u;
var value = x;
value -= (value >> 1) & c1;
value = (value & c2) + ((value >> 2) & c2);
value = (((value + (value >> 4)) & c3) * c4) >> 24;
return (int)value;
}
#endif
}
/// <summary>
/// Return number of <c>1</c>-s in binary representation of <c>x</c>
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
[MethodImpl(MethodImplAdvancedOptions.AggressiveInlining)]
public static int PopCount(ulong x)
{
#if NET5_0_OR_GREATER
return BitOperations.PopCount(x);
#else
unchecked
{
const ulong c1 = 0x_55555555_55555555ul;
const ulong c2 = 0x_33333333_33333333ul;
const ulong c3 = 0x_0F0F0F0F_0F0F0F0Ful;
const ulong c4 = 0x_01010101_01010101ul;
var value = x;
value -= (value >> 1) & c1;
value = (value & c2) + ((value >> 2) & c2);
value = (((value + (value >> 4)) & c3) * c4) >> 56;
return (int)value;
}
#endif
}
#if !NET5_0_OR_GREATER
[MethodImpl(MethodImplAdvancedOptions.AggressiveInlining)]
private static int ReverseBitScan(uint value)
{
unchecked
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return ourDeBruijnBitTable32[(int) ((value * DeBruijnSequence32) >> 27)];
}
}
[MethodImpl(MethodImplAdvancedOptions.AggressiveInlining)]
private static int ReverseBitScan(ulong value)
{
unchecked
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
value |= value >> 32;
return ourDeBruijnBitTable64[(int) ((value * DeBruijnSequence64) >> 58)];
}
}
#endif
}
}