当前位置：文江博客话题详情

C# algorithm math bit-manipulation

在 C# 中计算整数的 log2 的最快方法是什么？

发布于 2024-12-28 19:18:53 字数 111 浏览 2 评论 0 原文

如何最有效地计算 C# 中整数（以 2 为底的对数）所需的位数？例如：

int bits = 1 + log2(100);

=> bits == 7

原文

How can I most efficiently count the number of bits required by an integer (log base 2) in C#? For example:

int bits = 1 + log2(100);

=> bits == 7

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

柠檬心 2025-01-04 19:18:53

对 Guffa 答案的轻微改进...由于您添加到结果中的数量始终是 2 的幂，因此使用位运算可以对某些架构产生轻微的改进。此外，由于我们的上下文是位模式，因此使用十六进制更具可读性。在这种情况下，将算术移位 2 的幂很有用。

int bits = 0;

if (n > 0xffff) {
  n >>= 16;
  bits = 0x10;
}

if (n > 0xff) {
  n >>= 8;
  bits |= 0x8;
}

if (n > 0xf) {
  n >>= 4;
  bits |= 0x4;
}

if (n > 0x3) {
  n >>= 2;
  bits |= 0x2;
}

if (n > 0x1) {
  bits |= 0x1;
}

此外，应添加对 n==0 的检查，因为上面将产生 0 结果，并且 Log(0) 未定义（无论基数如何）。

在 ARM 汇编中，该算法生成非常紧凑的代码，因为可以使用条件指令消除比较后的分支，从而避免管道刷新。例如：

if (n > 0xff) {
   n >>= 8;
   bits |= 0x8;
}

变为（让 R0 = n，R1 = 位）

CMP R0, $0xff
MOVHI R0, R0, LSR $8
ORRHI R1, R1, $0x8

Slight improvement to Guffa's answer... Since the amount you are adding to the result is always a power of two using bit operations can produce slight improvement on some architectures. Also since our context is bit patterns it is slightly more readable to use hexadecimal. In this case it is useful to shift the arithmetic by a power of 2.

int bits = 0;

if (n > 0xffff) {
  n >>= 16;
  bits = 0x10;
}

if (n > 0xff) {
  n >>= 8;
  bits |= 0x8;
}

if (n > 0xf) {
  n >>= 4;
  bits |= 0x4;
}

if (n > 0x3) {
  n >>= 2;
  bits |= 0x2;
}

if (n > 0x1) {
  bits |= 0x1;
}

Further a check for n==0 should be added since the above will yield a result of 0 and Log(0) is undefined (regardless of base).

In ARM assembly this algorithm produces very compact code as the branch after comparison can be eliminated with conditional instructions which avoids pipeline flushing. For Example:

if (n > 0xff) {
   n >>= 8;
   bits |= 0x8;
}

becomes (let R0 = n, R1 = bits)

CMP R0, $0xff
MOVHI R0, R0, LSR $8
ORRHI R1, R1, $0x8

回复收藏 0 原文

看春风乍起 2025-01-04 19:18:53

您可以简单地计算必须删除位的次数，直到值为零：

int bits = 0;
while (n > 0) {
  bits++;
  n >>= 1;
}

对于大数字更有效，您可以首先计算位组：

int bits = 0;
while (n > 255) {
  bits += 8;
  n >>= 8;
}
while (n > 0) {
  bits++;
  n >>= 1;
}

编辑：

最有效的方法是使用 Flynn1179 建议的二进制步骤（已投票）寻求灵感:)，但将循环扩展为硬编码检查。这至少比上面的方法快两倍，但代码也更多：

int bits = 0;
if (n > 32767) {
  n >>= 16;
  bits += 16;
}
if (n > 127) {
  n >>= 8;
  bits += 8;
}
if (n > 7) {
  n >>= 4;
  bits += 4;
}
if (n > 1) {
  n >>= 2;
  bits += 2;
}
if (n > 0) {
  bits++;
}

You can simply count how many times you have to remove bits until the value is zero:

int bits = 0;
while (n > 0) {
  bits++;
  n >>= 1;
}

More efficient for large numbers, you can count groups of bits first:

int bits = 0;
while (n > 255) {
  bits += 8;
  n >>= 8;
}
while (n > 0) {
  bits++;
  n >>= 1;
}

Edit:

The most efficient method would be to use the binary steps that Flynn1179 suggested (upvoted for the inspiration :), but expanding the loop into hard coded checks. This is at least twice as fast as the method above, but also more code:

int bits = 0;
if (n > 32767) {
  n >>= 16;
  bits += 16;
}
if (n > 127) {
  n >>= 8;
  bits += 8;
}
if (n > 7) {
  n >>= 4;
  bits += 4;
}
if (n > 1) {
  n >>= 2;
  bits += 2;
}
if (n > 0) {
  bits++;
}

回复收藏 0 原文

眼中杀气 2025-01-04 19:18:53

最干净、最快...（适用于 .Net core 3.1 及更高版本，从 .Net 5.0 开始性能领先）

int val = BitOperations.Log2(x);

亚军...（版本中最快）低于.Net 5，.Net 5中的第二位）

int val = (int)((BitConverter.DoubleToInt64Bits(x) >> 52) + 1) & 0xFF;

注释：

在浮点中使用指数的想法受到SPWorley
2009 年 3 月 22 日。
这也支持超过 32 位。我没有测试过最大值，但确实达到了至少 2^38。
在生产代码上请谨慎使用，因为这可能会在非小端字节序的体系结构上失败。

以下是一些基准：（此处代码：https://github.com/SunsetQuest/Fast-Integer- Log2)

                                      1-2^32                  32-Bit  Zero 
Function                Time1 Time2 Time3 Time4 Time5 Errors Support Support 
Log2_SunsetQuest3       18     18    79167  19    18    255      N       N
Log2_SunsetQuest4       18     18    86976  19    18      0      Y       N
LeadingZeroCountSunsetq -      -        -   30    20      0      Y       Y
Log2_SPWorley           18     18    90976  32    18   4096      N       Y
MostSigBit_spender      20     19    86083  89    87      0      Y       Y
Log2_HarrySvensson      26     29    93592  34    31      0      Y       Y
Log2_WiegleyJ           27     23    95347  38    32      0      Y       N
Leading0Count_phuclv     -      -        -  33    20    10M      N       N
Log2_SunsetQuest1       31     28    78385  39    30      0      Y       Y
HighestBitUnrolled_Kaz  33     33   284112  35    38   2.5M      N       Y
Log2_Flynn1179          58     52    96381  48    53      0      Y       Y
BitOperationsLog2Sunsetq -      -        -  49    15      0      Y       Y
GetMsb_user3177100      58     53   100932  60    59      0      Y       Y
Log2_Papayaved         125     60   119161  90    82      0      Y       Y
FloorLog2_SN17         102     43   121708  97    92      0      Y       Y
Log2_DanielSig          28     24   960357  102  105     2M      N       Y
FloorLog2_Matthew_Watso 29     25    94222  104  102      0      Y       Y
Log2_SunsetQuest2      118    140   163483  184  159      0      Y       Y
Msb_version            136    118  1631797  212  207      0      Y       Y
Log2_SunsetQuest0      206    202   128695  212  205      0      Y       Y
BitScanReverse2        228    240  1132340  215  199     2M      N       Y
Log2floor_version       89    101 2 x 10^7  263  186      0      Y       Y
UsingStrings_version  2346   1494 2 x 10^7 2079 2122      0      Y       Y
                                                                           
Zero_Support = Supports Zero if the result is 0 or less
Full-32-Bit  = Supports full 32-bit (some just support 31 bits)
Time1 = benchmark for sizes up to 32-bit (same number tried for each size)
Time2 = benchmark for sizes up to 16-bit (for measuring perf on small numbers)
Time3 = time to run entire 1-2^32 in sequence using Parallel.For. Most results range will on the larger end like 30/31 log2 results. (note: because random was not used some compiler optimization might have been applied so this result might not be accurate) 
Time4 = .Net Core 3.1
Time5 = .Net 5

基准测试说明： AMD Ryzen CPU，Release 模式，无调试器附加，.net core 3.1

我真的很喜欢另一篇文章中的支出。该方法不存在潜在的架构问题，并且它还支持零，同时保持与 SPWorley 的浮点方法几乎相同的性能。

更新 3/13/2020： 史蒂夫注意到 Log2_SunsetQuest3 中存在一些被遗漏的错误。

更新 4/26/2020： 添加了新的 .Net Core 3 的 BitOperations.LeadingZeroCount()，如 phuclv 所指出的。

The Cleanest and Quickest... (works in .Net core 3.1 and up and takes the performance lead starting in .Net 5.0)

int val = BitOperations.Log2(x);

Runner up... (fastest in versions below .Net 5, 2nd place in .Net 5)

int val = (int)((BitConverter.DoubleToInt64Bits(x) >> 52) + 1) & 0xFF;

Notes:

The idea of using the exponent in a floating-point was inspired by SPWorley
3/22/2009.
This also supports more than 32 bits. I have not tested the max but did go to at least 2^38.
Use with caution on production code since this can possibly fail on architectures that are not little-endianness.

Here are some benchmarks: (code here: https://github.com/SunsetQuest/Fast-Integer-Log2)

                                      1-2^32                  32-Bit  Zero 
Function                Time1 Time2 Time3 Time4 Time5 Errors Support Support 
Log2_SunsetQuest3       18     18    79167  19    18    255      N       N
Log2_SunsetQuest4       18     18    86976  19    18      0      Y       N
LeadingZeroCountSunsetq -      -        -   30    20      0      Y       Y
Log2_SPWorley           18     18    90976  32    18   4096      N       Y
MostSigBit_spender      20     19    86083  89    87      0      Y       Y
Log2_HarrySvensson      26     29    93592  34    31      0      Y       Y
Log2_WiegleyJ           27     23    95347  38    32      0      Y       N
Leading0Count_phuclv     -      -        -  33    20    10M      N       N
Log2_SunsetQuest1       31     28    78385  39    30      0      Y       Y
HighestBitUnrolled_Kaz  33     33   284112  35    38   2.5M      N       Y
Log2_Flynn1179          58     52    96381  48    53      0      Y       Y
BitOperationsLog2Sunsetq -      -        -  49    15      0      Y       Y
GetMsb_user3177100      58     53   100932  60    59      0      Y       Y
Log2_Papayaved         125     60   119161  90    82      0      Y       Y
FloorLog2_SN17         102     43   121708  97    92      0      Y       Y
Log2_DanielSig          28     24   960357  102  105     2M      N       Y
FloorLog2_Matthew_Watso 29     25    94222  104  102      0      Y       Y
Log2_SunsetQuest2      118    140   163483  184  159      0      Y       Y
Msb_version            136    118  1631797  212  207      0      Y       Y
Log2_SunsetQuest0      206    202   128695  212  205      0      Y       Y
BitScanReverse2        228    240  1132340  215  199     2M      N       Y
Log2floor_version       89    101 2 x 10^7  263  186      0      Y       Y
UsingStrings_version  2346   1494 2 x 10^7 2079 2122      0      Y       Y
                                                                           
Zero_Support = Supports Zero if the result is 0 or less
Full-32-Bit  = Supports full 32-bit (some just support 31 bits)
Time1 = benchmark for sizes up to 32-bit (same number tried for each size)
Time2 = benchmark for sizes up to 16-bit (for measuring perf on small numbers)
Time3 = time to run entire 1-2^32 in sequence using Parallel.For. Most results range will on the larger end like 30/31 log2 results. (note: because random was not used some compiler optimization might have been applied so this result might not be accurate) 
Time4 = .Net Core 3.1
Time5 = .Net 5

Benchmark notes: AMD Ryzen CPU, Release mode, no-debugger attached, .net core 3.1

I really like the one created by spender in another post. This one does not have the potential architecture issue and it also supports Zero while maintaining almost the same performance as the float method from SPWorley.

Update 3/13/2020: Steve noticed that there were some errors in Log2_SunsetQuest3 that were missed.

Update 4/26/2020: Added new .Net Core 3's BitOperations.LeadingZeroCount() as pointed out by phuclv.

回复收藏 0 原文

霊感 2025-01-04 19:18:53

代码行数或运行时执行速度方面的效率？

代码很简单：Math.log(n, 2)。

运行时速度有点棘手，但你可以通过一种“二分搜索”来做到这一点：

int bits = 1;
for (int b = 16; b >=1; b/=2)
{
  int s = 1 << b;
  if (n >= s) { n>>=b; bits+=b; }
}

我不能 100% 确定我已经掌握了逻辑，但希望这个想法是清楚的。 .NET VM 中可能会有一些开销，但原则上它应该更快。

for 循环初始化程序中的 16 基于 int 所需位数的一半。如果您使用长整型，请从 32 开始，依此类推。

Efficiency in terms of lines of code, or runtime execution speed?

Code's easy: Math.log(n, 2).

Runtime speed's a little trickier, but you can do it with a kind of 'binary search':

int bits = 1;
for (int b = 16; b >=1; b/=2)
{
  int s = 1 << b;
  if (n >= s) { n>>=b; bits+=b; }
}

I'm not 100% certain I've got the logic right there, but hopefully the idea's clear. There might be some overheads in the .NET VM, but in principle it should be faster.

The 16 in the for loop initialializer is based on half the number of bits needed for an int. If you're working with longs, start it at 32, etc.

回复收藏 0 原文

贪恋 2025-01-04 19:18:53

在 .NET Core 3.0 中，有 BitOperations.LeadingZeroCount() 和 BitOperations.Log2。它们被映射到底层硬件指令，如 x86 的 LZCNT/BSR，因此这应该是最有效的解决方案

int bits = BitOperations.Log2(x); // or
int bits = x == 0 ? 1 : 32 - BitOperations.LeadingZeroCount(x);

In .NET Core 3.0 there are BitOperations.LeadingZeroCount() and BitOperations.Log2. They're mapped to the underlying hardware instructino like x86's LZCNT/BSR so that should be the most efficient solution

int bits = BitOperations.Log2(x); // or
int bits = x == 0 ? 1 : 32 - BitOperations.LeadingZeroCount(x);

回复收藏 0 原文

木緿 2025-01-04 19:18:53

直接转换为 IEEE754 32 位在大约 33554431

public unsafe static int ByPtr754_32(ulong bits) {
    var fp = (float)bits;
    return (int)(((*(uint*)&fp >> 23) & 255) - 127);
}

转换为 FP64 后有错误结果，ILogB 在 53 位后有错误结果，大约 18014398509481983

public unsafe static int ByPtr754_64(ulong bits) {
    var fp = (double)bits;
    return ((int)(*(ulong*)&fp >> 52) & 2047) - 1023;
}
public static int ByILogB(ulong bits) {
    return Math.ILogB(bits);
}

lg 和 ln 在大约 47 位后有错误，大约 281474976710655

static readonly double ln2 = Math.Log(2.0), divLn2 = 1 / ln2;
public static int ByLn(ulong bits) {
    //return (int)(Math.Log(bits) * divLn2);
    return (int)(Math.Log(bits) / ln2);
}

lb 在 48 位后有错误，大约562949953421311

public static int ByLog2(ulong bits) {
    return (int)Math.Log2(bits);
}

二分查找非常慢。

public static int BySearch(ulong bits) {
    if (0 == bits) {
        return -1;
    }

    int min = 0, max = 64;
    for (; ; ) {
        int mid = (max + min) >> 1;
        if (mid == min) {
            break;
        }
        if (bits >> mid != 0) {
            min = mid;
        } else {
            max = mid;
        }
    }
    return min;
}

我的建议在这里：
快一：

public unsafe static int ByPtr754_64(ulong bits) {
    var fp = (double)bits;
    return ((int)(*(ulong*)&fp >> 52) & 2047) - 1023;
}

const int Fp64Prec = 53;
static int[] CreateTableMix() {
    var ret = new int[1 << (64 - Fp64Prec)];
    for (int i = ret.Length; --i >= 0;) {
        ret[i] = ByPtr754_64((uint)i) + Fp64Prec;
    }
    return ret;
}
static readonly int[] _TableMix = CreateTableMix();
public static int ByTableMix(ulong bits) {
    int r;
    return (r = _TableMix[bits >> Fp64Prec]) > 0 ? r : ByPtr754_64(bits);
}

简单一：

const int Fp64Prec = 53;
static int[] CreateTableMix() {
    var ret = new int[1 << (64 - Fp64Prec)];
    for (int i = ret.Length; --i >= 0;) {
        ret[i] = ByPtr754_64((uint)i) + Fp64Prec;
    }
    return ret;
}
public static int By754Adj(ulong bits) {
    const int lack = 64 - Fp64Prec;
    int r;
    return (r = ByPtr754_64(bits >> lack)) > 0 ? r+lack : ByPtr754_64(bits);
}

速度测试结果：

 Search: 649830
 ByTest: 535859
 ByLog2: 560492
   ByLn: 376675
   ByLg: 392090
 ByILog: 252594
Table16: 136847
ByUnion: 123453
 754_64: 101358
 754_32: 118379
TableMx: 106201
 754Adj: 174889

direct convert to IEEE754 32bit has wrong result after about 33554431

public unsafe static int ByPtr754_32(ulong bits) {
    var fp = (float)bits;
    return (int)(((*(uint*)&fp >> 23) & 255) - 127);
}

convert to FP64 and ILogB has wrong result after 53bits, about 18014398509481983

public unsafe static int ByPtr754_64(ulong bits) {
    var fp = (double)bits;
    return ((int)(*(ulong*)&fp >> 52) & 2047) - 1023;
}
public static int ByILogB(ulong bits) {
    return Math.ILogB(bits);
}

lg and ln has wrong after about 47bits, about 281474976710655

static readonly double ln2 = Math.Log(2.0), divLn2 = 1 / ln2;
public static int ByLn(ulong bits) {
    //return (int)(Math.Log(bits) * divLn2);
    return (int)(Math.Log(bits) / ln2);
}

lb wrong after 48bits, about 562949953421311

public static int ByLog2(ulong bits) {
    return (int)Math.Log2(bits);
}

Binary Search is very slow.

public static int BySearch(ulong bits) {
    if (0 == bits) {
        return -1;
    }

    int min = 0, max = 64;
    for (; ; ) {
        int mid = (max + min) >> 1;
        if (mid == min) {
            break;
        }
        if (bits >> mid != 0) {
            min = mid;
        } else {
            max = mid;
        }
    }
    return min;
}

My suggestion is here:
Fast one:

public unsafe static int ByPtr754_64(ulong bits) {
    var fp = (double)bits;
    return ((int)(*(ulong*)&fp >> 52) & 2047) - 1023;
}

const int Fp64Prec = 53;
static int[] CreateTableMix() {
    var ret = new int[1 << (64 - Fp64Prec)];
    for (int i = ret.Length; --i >= 0;) {
        ret[i] = ByPtr754_64((uint)i) + Fp64Prec;
    }
    return ret;
}
static readonly int[] _TableMix = CreateTableMix();
public static int ByTableMix(ulong bits) {
    int r;
    return (r = _TableMix[bits >> Fp64Prec]) > 0 ? r : ByPtr754_64(bits);
}

Simple one:

const int Fp64Prec = 53;
static int[] CreateTableMix() {
    var ret = new int[1 << (64 - Fp64Prec)];
    for (int i = ret.Length; --i >= 0;) {
        ret[i] = ByPtr754_64((uint)i) + Fp64Prec;
    }
    return ret;
}
public static int By754Adj(ulong bits) {
    const int lack = 64 - Fp64Prec;
    int r;
    return (r = ByPtr754_64(bits >> lack)) > 0 ? r+lack : ByPtr754_64(bits);
}

Speed test result:

 Search: 649830
 ByTest: 535859
 ByLog2: 560492
   ByLn: 376675
   ByLg: 392090
 ByILog: 252594
Table16: 136847
ByUnion: 123453
 754_64: 101358
 754_32: 118379
TableMx: 106201
 754Adj: 174889

回复收藏 0 原文

~没有更多了~