blocks|key|1871162|text|如果位运算比目标机器上的比较快，你可以这样做：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1871163|inline+int+len(uint32+val)
{
++++if(val+&+0xff000000)+return+4;
++++if(val+&+0x00ff0000)+return+3;
++++if(val+&+0x0000ff00)+return+2;
++++return+1;
}+|code-block|syntax|javascript|1871164|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

If bit ops are faster than comparison on your target machine you can do this:

<pre><code>inline int len(uint32 val)
{
 if(val &amp; 0xff000000) return 4;
 if(val &amp; 0x00ff0000) return 3;
 if(val &amp; 0x0000ff00) return 2;
 return 1;
} 
</code></pre>

blocks|key|1871166|text|这个怎么样？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1871167|inline+int+len(uint32+val)
{
++++return+4
++++++++-+((val+&+0xff000000)+==+0)
++++++++-+((val+&+0xffff0000)+==+0)
++++++++-+((val+&+0xffffff00)+==+0)
++++;
}|code-block|syntax|javascript|1871168|删除inline关键字后，g%2B%2B+-O2会将其编译为以下无分支代码：|offset|length|style|CODE|1871169|movl++++8(%25ebp),+%25edx
movl++++%25edx,+%25eax
andl++++$-16777216,+%25eax
cmpl++++$1,+%25eax
sbbl++++%25eax,+%25eax
addl++++$4,+%25eax
xorl++++%25ecx,+%25ecx
testl+++$-65536,+%25edx
sete++++%25cl
subl++++%25ecx,+%25eax
andl++++$-256,+%25edx
sete++++%25dl
movzbl++%25dl,+%25edx
subl++++%25edx,+%25eax|1871170|如果您不介意特定于机器的解决方案，您可以使用bsr指令来搜索前1位。然后，您只需除以8将位转换为字节，然后添加1将范围0..3移位到1..4：|1871171|int+len(uint32+val)
{
++++asm("mov+8(%25ebp),+%25eax");
++++asm("or++$255,+%25eax");
++++asm("bsr+%25eax,+%25eax");
++++asm("shr+$3,+%25eax");
++++asm("inc+%25eax");
++++asm("mov+%25eax,+8(%25ebp)");
++++return+val;
}|1871172|请注意，我不是内联汇编之神，所以也许有一个更好的解决方案是访问val，而不是显式地寻址堆栈。但您应该了解基本概念。|1871173|GNU编译器还有一个有趣的内置函数，称为__builtin_clz|1871174|inline+int+len(uint32+val)
{
++++return+((__builtin_clz(val+%7C+255)+%5E+31)+>>+3)+%2B+1;
}|1871175|在我看来，这比内联程序集版本要好得多:)|1871176|entityMap^0|0|0|2|6|D|7|0|0|M|3|0|0|V|3|0|K|D|0|0|0^^$0|@$1|2|3|4|5|6|7|12|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|13|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|14|8|@$I|15|J|16|K|L]|$I|17|J|18|K|L]]|9|@]|A|$]]|$1|M|3|N|5|D|7|19|8|@]|9|@]|A|$E|F]]|$1|O|3|P|5|6|7|1A|8|@$I|1B|J|1C|K|L]]|9|@]|A|$]]|$1|Q|3|R|5|D|7|1D|8|@]|9|@]|A|$E|F]]|$1|S|3|T|5|6|7|1E|8|@$I|1F|J|1G|K|L]]|9|@]|A|$]]|$1|U|3|V|5|6|7|1H|8|@$I|1I|J|1J|K|L]]|9|@]|A|$]]|$1|W|3|X|5|D|7|1K|8|@]|9|@]|A|$E|F]]|$1|Y|3|Z|5|6|7|1L|8|@]|9|@]|A|$]]|$1|10|3|-4|5|6|7|1M|8|@]|9|@]|A|$]]]|11|$]]

How about this one?

<pre><code>inline int len(uint32 val)
{
 return 4
 - ((val &amp; 0xff000000) == 0)
 - ((val &amp; 0xffff0000) == 0)
 - ((val &amp; 0xffffff00) == 0)
 ;
}
</code></pre>

Removing the <code>inline</code> keyword, <code>g++ -O2</code> compiles this to the following branchless code:

<pre><code>movl 8(%ebp), %edx
movl %edx, %eax
andl $-16777216, %eax
cmpl $1, %eax
sbbl %eax, %eax
addl $4, %eax
xorl %ecx, %ecx
testl $-65536, %edx
sete %cl
subl %ecx, %eax
andl $-256, %edx
sete %dl
movzbl %dl, %edx
subl %edx, %eax
</code></pre>

If you don't mind machine-specific solutions, you can use the <code>bsr</code> instruction which searches for the first 1 bit. Then you simply divide by 8 to convert bits to bytes and add 1 to shift the range 0..3 to 1..4:

<pre><code>int len(uint32 val)
{
 asm("mov 8(%ebp), %eax");
 asm("or $255, %eax");
 asm("bsr %eax, %eax");
 asm("shr $3, %eax");
 asm("inc %eax");
 asm("mov %eax, 8(%ebp)");
 return val;
}
</code></pre>

Note that I am not an inline assembly god, so maybe there's a better to solution to access <code>val</code> instead of addressing the stack explicitly. But you should get the basic idea.

The GNU compiler also has an interesting built-in function called <code>__builtin_clz</code>:

<pre><code>inline int len(uint32 val)
{
 return ((__builtin_clz(val | 255) ^ 31) &gt;&gt; 3) + 1;
}
</code></pre>

This looks much better than the inline assembly version to me :)

blocks|key|1871178|text|如果数字的分布不能使预测变得容易，那么您可以避免使用可能代价高昂的条件分支：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1871179|return+4+-+(val+<=+0x000000ff)+-+(val+<=+0x0000ffff)+-+(val+<=+0x00ffffff);|code-block|syntax|javascript|1871180|将<=更改为&不会对现代处理器产生太大影响。您的目标平台是什么？|offset|length|style|CODE|1871181|下面是使用gcc+-O为x86-64生成的代码|1871182|++++cmpl++++$255,+%25edi
++++setg++++%25al
++++movzbl++%25al,+%25eax
++++addl++++$3,+%25eax
++++cmpl++++$65535,+%25edi
++++setle+++%25dl
++++movzbl++%25dl,+%25edx
++++subl++++%25edx,+%25eax
++++cmpl++++$16777215,+%25edi
++++setle+++%25dl
++++movzbl++%25dl,+%25edx
++++subl++++%25edx,+%25eax|1871183|当然，也有比较指令cmpl，但这些指令后面是setg或setle，而不是条件分支(通常是这样)。在现代流水线处理器上，条件分支是昂贵的，而不是比较。所以这个版本保存了昂贵的条件分支。|1871184|我手动优化gcc的程序集的尝试：|1871185|++++cmpl++++$255,+%25edi
++++setg++++%25al
++++addb++++$3,+%25al
++++cmpl++++$65535,+%25edi
++++setle+++%25dl
++++subb++++%25dl,+%25al
++++cmpl++++$16777215,+%25edi
++++setle+++%25dl
++++subb++++%25dl,+%25al
++++movzbl++%25al,+%25eax|1871186|entityMap^0|0|0|1|2|6|1|0|5|6|0|0|9|4|M|4|R|5|0|0|0^^$0|@$1|2|3|4|5|6|7|Y|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|Z|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|10|8|@$I|11|J|12|K|L]|$I|13|J|14|K|L]]|9|@]|A|$]]|$1|M|3|N|5|6|7|15|8|@$I|16|J|17|K|L]]|9|@]|A|$]]|$1|O|3|P|5|D|7|18|8|@]|9|@]|A|$E|F]]|$1|Q|3|R|5|6|7|19|8|@$I|1A|J|1B|K|L]|$I|1C|J|1D|K|L]|$I|1E|J|1F|K|L]]|9|@]|A|$]]|$1|S|3|T|5|6|7|1G|8|@]|9|@]|A|$]]|$1|U|3|V|5|D|7|1H|8|@]|9|@]|A|$E|F]]|$1|W|3|-4|5|6|7|1I|8|@]|9|@]|A|$]]]|X|$]]

You can avoid the conditional branches that can be costly if the distribution of your numbers does not make prediction easy:

<pre><code>return 4 - (val &lt;= 0x000000ff) - (val &lt;= 0x0000ffff) - (val &lt;= 0x00ffffff);
</code></pre>

Changing the <code>&lt;=</code> to a <code>&amp;</code> will not change anything much on a modern processor. What is your target platform?

Here is the generated code for x86-64 with <code>gcc -O</code>:

<pre><code> cmpl $255, %edi
 setg %al
 movzbl %al, %eax
 addl $3, %eax
 cmpl $65535, %edi
 setle %dl
 movzbl %dl, %edx
 subl %edx, %eax
 cmpl $16777215, %edi
 setle %dl
 movzbl %dl, %edx
 subl %edx, %eax
</code></pre>

There are comparison instructions <code>cmpl</code> of course, but these are followed by <code>setg</code> or <code>setle</code> instead of conditional branches (as would be usual). It's the conditional branch that is expensive on a modern pipelined processor, not the comparison. So this version saves the expensive conditional branches.

My attempt at hand-optimizing gcc's assembly:

<pre><code> cmpl $255, %edi
 setg %al
 addb $3, %al
 cmpl $65535, %edi
 setle %dl
 subb %dl, %al
 cmpl $16777215, %edi
 setle %dl
 subb %dl, %al
 movzbl %al, %eax
</code></pre>

blocks|key|1871188|text|二分查找可能会节省几个周期，这取决于处理器的体系结构。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1871189|inline+int+len(uint32+val)
{
++++if+(val+&+0xffff0000)+return+(val+&+0xff000000)?+4:+3;
++++return+(val+&+0x0000ff00)?+2:+1;
}|code-block|syntax|javascript|1871190|或者，找出哪种是最常见的情况可能会降低平均周期数，如果大多数输入是一个字节(例如，当构建UTF-8编码时，那么您的断点就不是32/24/16/8)：|1871191|inline+int+len(uint32+val)
{
++++if+(val+&+0xffffff00)+{
+++++++if+(val+&+0xffff0000)+{
+++++++++++if+(val+&+0xff000000)+return+4;
+++++++++++return+3;
+++++++}
+++++++return+2;
++++}
++++return+1;
}|1871192|现在，短例执行的条件测试最少。|1871193|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|S|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

Binary search MIGHT save a few cycles, depending on the processor architecture.

<pre><code>inline int len(uint32 val)
{
 if (val &amp; 0xffff0000) return (val &amp; 0xff000000)? 4: 3;
 return (val &amp; 0x0000ff00)? 2: 1;
}
</code></pre>

Or, finding out which is the most common case might bring down the average number of cycles, if most inputs are one byte (eg when building UTF-8 encodings, but then your break points wouldn't be 32/24/16/8):

<pre><code>inline int len(uint32 val)
{
 if (val &amp; 0xffffff00) {
 if (val &amp; 0xffff0000) {
 if (val &amp; 0xff000000) return 4;
 return 3;
 }
 return 2;
 }
 return 1;
}
</code></pre>

Now the short case does the fewest conditional tests.

blocks|key|1871195|text|好的，再来一个版本。与Fred的相似，但操作较少。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1871196|inline+int+len(uint32+val)
{
++++return+1
++++++++%2B+(val+>+0x000000ff)
++++++++%2B+(val+>+0x0000ffff)
++++++++%2B+(val+>+0x00ffffff)
++++;
}|code-block|syntax|javascript|1871197|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Ok one more version. Similar to Fred's one, but with less operations.

<pre><code>inline int len(uint32 val)
{
 return 1
 + (val &gt; 0x000000ff)
 + (val &gt; 0x0000ffff)
 + (val &gt; 0x00ffffff)
 ;
}
</code></pre>

blocks|key|2085150|text|您是否真的有个人资料证据表明这是您的应用程序中的一个重要瓶颈？只要以最明显的方式来做，并且只有当分析显示它是一个问题时(我怀疑)，然后尝试改进事情。最有可能的情况是，通过减少对此函数的调用次数，而不是通过更改其中的某些内容，您将获得最佳的改进。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2085151|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Do you really have profile evidence that this is a significant bottleneck in your application? Just do it the most obvious way and only if profiling shows it to be a problem (which I doubt), then try to improve things. Most likely you'll get the best improvement by reducing the number of calls to this function than by changing something within it.

blocks|key|2085156|text|这给了你更少的比较。但是如果存储器访问操作花费多于两次比较，则效率可能较低。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2085157|int+precalc[1<<16];
int+precalchigh[1<<16];
void+doprecalc()
{
++++for(int+i+=+0;+i+<+1<<16;+i%2B%2B)+{
++++++++precalc[i]+=+(i+<+(1<<8)+?+1+:+2);
++++++++precalchigh[i]+=+precalc[i]+%2B+2;
++++}
}
inline+int+len(uint32+val)
{
++++return+(val+&+0xffff0000+?+precalchigh[val+>>+16]+:+precalc[val]);
}|code-block|syntax|javascript|2085158|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

This gives you less comparisons. But may be less efficient if memory access operation costs more than a couple of comparisons.

<pre><code>int precalc[1&lt;&lt;16];
int precalchigh[1&lt;&lt;16];
void doprecalc()
{
 for(int i = 0; i &lt; 1&lt;&lt;16; i++) {
 precalc[i] = (i &lt; (1&lt;&lt;8) ? 1 : 2);
 precalchigh[i] = precalc[i] + 2;
 }
}
inline int len(uint32 val)
{
 return (val &amp; 0xffff0000 ? precalchigh[val &gt;&gt; 16] : precalc[val]);
}
</code></pre>

blocks|key|2085183|text|我做了一个小型的不科学的基准测试，只是在VS2010编译器下从0到MAX_LONG的循环中调用函数时，测量GetTickCount()调用的差异。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2085184|这是我看到的：|2085185|这花了11497个刻度|2085186|inline+int+len(uint32+val)
{
++++if(val+<=+0x000000ff)+return+1;
++++if(val+<=+0x0000ffff)+return+2;
++++if(val+<=+0x00ffffff)+return+3;
++++return+4;
}+|code-block|syntax|javascript|2085187|虽然这需要14399个刻度|2085188|inline+int+len(uint32+val)
{
++++return+4
++++++++-+((val+&+0xff000000)+==+0)
++++++++-+((val+&+0xffff0000)+==+0)
++++++++-+((val+&+0xffffff00)+==+0)
++++;
}|2085189|编辑:我关于为什么一个更快的想法是错误的，因为：|2085190|inline+int+len(uint32+val)
{
++++return+1
++++++++%2B+(val+>+0x000000ff)
++++++++%2B+(val+>+0x0000ffff)
++++++++%2B+(val+>+0x00ffffff)
++++++++;
}|2085191|这个版本只使用了11107个刻度。因为%2B可能比-更快？我没有把握。|2085192|不过，二进制搜索速度更快，达到了7161次|2085193|inline+int+len(uint32+val)
{
++++if+(val+&+0xffff0000)+return+(val+&+0xff000000)?+4:+3;
++++return+(val+&+0x0000ff00)?+2:+1;
}|2085194|到目前为止，最快的是使用MS内部函数，速度为4399次|2085195|#pragma+intrinsic(_BitScanReverse)

inline+int+len2(uint32+val)
{
++++DWORD+index;
++++_BitScanReverse(&index,+val);

++++return+(index>>3)%2B1;

}|2085196|作为参考-这是我用来分析的代码：|2085197|int+_tmain(int+argc,+_TCHAR*+argv[])
{
++++int+j+=+0;
++++DWORD+t1,t2;

++++t1+=+GetTickCount();

++++for(ULONG+i=0;+i<-1;+i%2B%2B)
++++++++j=len(i);

++++t2+=+GetTickCount();

++++_tprintf(_T("%25ld+ticks+%25ld\n"),+t2-t1,+j);


++++t1+=+GetTickCount();

++++for(ULONG+i=0;+i<-1;+i%2B%2B)
++++++++j=len2(i);

++++t2+=+GetTickCount();

++++_tprintf(_T("%25ld+ticks+%25ld\n"),+t2-t1,+j);
}|2085198|我必须打印j以防止循环被优化出来。|2085199|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1A|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1B|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|1C|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|1D|8|@]|9|@]|A|$I|J]]|$1|K|3|L|5|6|7|1E|8|@]|9|@]|A|$]]|$1|M|3|N|5|H|7|1F|8|@]|9|@]|A|$I|J]]|$1|O|3|P|5|6|7|1G|8|@]|9|@]|A|$]]|$1|Q|3|R|5|H|7|1H|8|@]|9|@]|A|$I|J]]|$1|S|3|T|5|6|7|1I|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|1J|8|@]|9|@]|A|$]]|$1|W|3|X|5|H|7|1K|8|@]|9|@]|A|$I|J]]|$1|Y|3|Z|5|6|7|1L|8|@]|9|@]|A|$]]|$1|10|3|11|5|H|7|1M|8|@]|9|@]|A|$I|J]]|$1|12|3|13|5|6|7|1N|8|@]|9|@]|A|$]]|$1|14|3|15|5|H|7|1O|8|@]|9|@]|A|$I|J]]|$1|16|3|17|5|6|7|1P|8|@]|9|@]|A|$]]|$1|18|3|-4|5|6|7|1Q|8|@]|9|@]|A|$]]]|19|$]]

I did a mini unscientific benchmark just measuring the difference in GetTickCount() calls when calling the function in a loop from 0 to MAX_LONG times under the VS 2010 compiler.

Here's what I saw:

This took 11497 ticks

<pre><code>inline int len(uint32 val)
{
 if(val &lt;= 0x000000ff) return 1;
 if(val &lt;= 0x0000ffff) return 2;
 if(val &lt;= 0x00ffffff) return 3;
 return 4;
} 
</code></pre>

While this took 14399 ticks

<pre><code>inline int len(uint32 val)
{
 return 4
 - ((val &amp; 0xff000000) == 0)
 - ((val &amp; 0xffff0000) == 0)
 - ((val &amp; 0xffffff00) == 0)
 ;
}
</code></pre>

edit: my idea about why one was faster is wrong because:

<pre><code>inline int len(uint32 val)
{
 return 1
 + (val &gt; 0x000000ff)
 + (val &gt; 0x0000ffff)
 + (val &gt; 0x00ffffff)
 ;
}
</code></pre>

This version used only 11107 ticks. Since + is faster than - perhaps? I'm not sure.

Even faster though was the binary search at 7161 ticks

<pre><code>inline int len(uint32 val)
{
 if (val &amp; 0xffff0000) return (val &amp; 0xff000000)? 4: 3;
 return (val &amp; 0x0000ff00)? 2: 1;
}
</code></pre>

And fastest so far is using the MS intrinsic function, at 4399 ticks

<pre><code>#pragma intrinsic(_BitScanReverse)

inline int len2(uint32 val)
{
 DWORD index;
 _BitScanReverse(&amp;index, val);

 return (index&gt;&gt;3)+1;

}
</code></pre>

For reference - here's the code i used to profile:

<pre><code>int _tmain(int argc, _TCHAR* argv[])
{
 int j = 0;
 DWORD t1,t2;

 t1 = GetTickCount();

 for(ULONG i=0; i&lt;-1; i++)
 j=len(i);

 t2 = GetTickCount();

 _tprintf(_T("%ld ticks %ld\n"), t2-t1, j);


 t1 = GetTickCount();

 for(ULONG i=0; i&lt;-1; i++)
 j=len2(i);

 t2 = GetTickCount();

 _tprintf(_T("%ld ticks %ld\n"), t2-t1, j);
}
</code></pre>

Had to print j to prevent the loops from being optimized out.

blocks|key|1871248|text|存储整数所需的最小位数为：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1871249|int+minbits+=+(int)ceil(+log10(n)+/+log10(2)+)+;|code-block|syntax|javascript|1871250|字节数为：|1871251|int+minbytes+=+(int)ceil(+log10(n)+/+log10(2)+/+8+)+;|1871252|这是一个完全受FPU限制的解决方案，性能可能比条件测试好，也可能不比条件测试好，但也许值得研究。|1871253|编辑我做了调查；上面一千万次迭代的简单循环花费了918ms，而FredOverflow被接受的解决方案只花了49ms+(VC%2B%2B+2010)。因此，这并不是性能上的改进，尽管如果它是所需的位数，则可能仍然有用，并且可以进一步优化。|1871254|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|S|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|V|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

The minimum number of bits required to store an integer is:

<pre><code>int minbits = (int)ceil( log10(n) / log10(2) ) ;
</code></pre>

The number of bytes is:

<pre><code>int minbytes = (int)ceil( log10(n) / log10(2) / 8 ) ;
</code></pre>

This is an entirely FPU bound solution, performance may or may not be better than a conditional test, but worth investigation perhaps.

[EDIT]
I did the investigation; a simple loop of ten million iterations of the above took 918ms whereas FredOverflow's accepted solution took just 49ms (VC++ 2010). So this is not an improvement in terms of performance, though may remain useful if it were the number of bits that were required, and further optimisations are possible.

blocks|key|1871281|text|为了说明一下，基于FredOverflow的答案(这是一个很好的工作，kudos和%2B1)，关于x86上分支的一个常见陷阱。以下是由gcc输出的FredOverflow程序集：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1871282|movl++++8(%25ebp),+%25edx+++#1/.5
movl++++%25edx,+%25eax++++++#1/.5
andl++++$-16777216,+%25eax#1/.5
cmpl++++$1,+%25eax++++++++#1/.5
sbbl++++%25eax,+%25eax++++++#8/6
addl++++$4,+%25eax++++++++#1/.5
xorl++++%25ecx,+%25ecx++++++#1/.5
testl+++$-65536,+%25edx+++#1/.5
sete++++%25cl+++++++++++++#5
subl++++%25ecx,+%25eax++++++#1/.5
andl++++$-256,+%25edx+++++#1/.5
sete++++%25dl+++++++++++++#5
movzbl++%25dl,+%25edx+++++++#1/.5
subl++++%25edx,+%25eax++++++#1/.5
#+sum+total:+29/21.5+cycles|code-block|syntax|javascript|1871283|(延迟，以周期为单位，读作Prescott/Northwood)|1871284|Pascal+Cuoq的手工优化汇编(也是kudos)：|1871285|cmpl++++$255,+%25edi++++++#1/.5
setg++++%25al+++++++++++++#5
addb++++$3,+%25al+++++++++#1/.5
cmpl++++$65535,+%25edi++++#1/.5
setle+++%25dl+++++++++++++#5
subb++++%25dl,+%25al++++++++#1/.5
cmpl++++$16777215,+%25edi+#1/.5
setle+++%25dl+++++++++++++#5
subb++++%25dl,+%25al++++++++#1/.5
movzbl++%25al,+%25eax+++++++#1/.5
#+sum+total:+22/18.5+cycles|1871286|编辑:使用__builtin_clz()的FredOverflow解决方案|offset|length|style|CODE|1871287|movl+8(%25ebp),+%25eax+++#1/.5
popl+%25ebp++++++++++++#1.5
orb++$-1,+%25al++++++++#1/.5
bsrl+%25eax,+%25eax++++++#16/8
sarl+$3,+%25eax++++++++#1/4
addl+$1,+%25eax++++++++#1/.5
ret
#+sum+total:+20/13.5+cycles|1871288|和您的代码的gcc程序集：|1871289|movl+$1,+%25eax++++++++#1/.5
movl+%25esp,+%25ebp++++++#1/.5
movl+8(%25ebp),+%25edx+++#1/.5
cmpl+$255,+%25edx++++++#1/.5
jbe++.L3+++++++++++++#up+to+9+cycles
cmpl+$65535,+%25edx++++#1/.5
movb+$2,+%25al+++++++++#1/.5
jbe++.L3+++++++++++++#up+to+9+cycles
cmpl+$16777216,+%25edx+#1/.5
sbbl+%25eax,+%25eax++++++#8/6
addl+$4,+%25eax++++++++#1/.5
.L3:
ret
#+sum+total:+16/10+cycles+-+34/28+cycles|1871290|其中作为jcc指令的副作用出现的指令高速缓冲存储器线提取对于如此短的功能可能不花费任何成本。|1871291|分支可能是一个合理的选择，这取决于输入分布。|1871292|编辑:添加FredOverflow的解决方案，该方案使用__builtin_clz()。|1871293|entityMap^0|0|0|0|0|0|5|F|0|0|0|0|4|3|0|0|S|F|0^^$0|@$1|2|3|4|5|6|7|16|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|17|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|18|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|19|8|@]|9|@]|A|$]]|$1|K|3|L|5|D|7|1A|8|@]|9|@]|A|$E|F]]|$1|M|3|N|5|6|7|1B|8|@$O|1C|P|1D|Q|R]]|9|@]|A|$]]|$1|S|3|T|5|D|7|1E|8|@]|9|@]|A|$E|F]]|$1|U|3|V|5|6|7|1F|8|@]|9|@]|A|$]]|$1|W|3|X|5|D|7|1G|8|@]|9|@]|A|$E|F]]|$1|Y|3|Z|5|6|7|1H|8|@$O|1I|P|1J|Q|R]]|9|@]|A|$]]|$1|10|3|11|5|6|7|1K|8|@]|9|@]|A|$]]|$1|12|3|13|5|6|7|1L|8|@$O|1M|P|1N|Q|R]]|9|@]|A|$]]|$1|14|3|-4|5|6|7|1O|8|@]|9|@]|A|$]]]|15|$]]

Just to illustrate, based on FredOverflow's answer (which is nice work, kudos and +1), a common pitfall regarding branches on x86. Here's FredOverflow's assembly as output by gcc:

<pre><code>movl 8(%ebp), %edx #1/.5
movl %edx, %eax #1/.5
andl $-16777216, %eax#1/.5
cmpl $1, %eax #1/.5
sbbl %eax, %eax #8/6
addl $4, %eax #1/.5
xorl %ecx, %ecx #1/.5
testl $-65536, %edx #1/.5
sete %cl #5
subl %ecx, %eax #1/.5
andl $-256, %edx #1/.5
sete %dl #5
movzbl %dl, %edx #1/.5
subl %edx, %eax #1/.5
# sum total: 29/21.5 cycles
</code></pre>

(the latency, in cycles, is to be read as Prescott/Northwood)

Pascal Cuoq's hand-optimized assembly (also kudos):

<pre><code>cmpl $255, %edi #1/.5
setg %al #5
addb $3, %al #1/.5
cmpl $65535, %edi #1/.5
setle %dl #5
subb %dl, %al #1/.5
cmpl $16777215, %edi #1/.5
setle %dl #5
subb %dl, %al #1/.5
movzbl %al, %eax #1/.5
# sum total: 22/18.5 cycles
</code></pre>

Edit: FredOverflow's solution using <code>__builtin_clz()</code>:

<pre><code>movl 8(%ebp), %eax #1/.5
popl %ebp #1.5
orb $-1, %al #1/.5
bsrl %eax, %eax #16/8
sarl $3, %eax #1/4
addl $1, %eax #1/.5
ret
# sum total: 20/13.5 cycles
</code></pre>

and the gcc assembly for your code:

<pre><code>movl $1, %eax #1/.5
movl %esp, %ebp #1/.5
movl 8(%ebp), %edx #1/.5
cmpl $255, %edx #1/.5
jbe .L3 #up to 9 cycles
cmpl $65535, %edx #1/.5
movb $2, %al #1/.5
jbe .L3 #up to 9 cycles
cmpl $16777216, %edx #1/.5
sbbl %eax, %eax #8/6
addl $4, %eax #1/.5
.L3:
ret
# sum total: 16/10 cycles - 34/28 cycles
</code></pre>

in which the instruction cache line fetches which come as the side-effect of the <code>jcc</code> instructions probably cost nothing for such a short function.

Branches can be a reasonable choice, depending on the input distribution.

Edit: added FredOverflow's solution which is using <code>__builtin_clz()</code>.

blocks|key|2085271|text|在某些系统上，这在某些架构上可能会更快：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2085272|inline+int+len(uint32_t+val)+{
+++return+(int)(+log(val)+/+log(256)+);++//+this+is+the+log+base+256+of+val
}|code-block|syntax|javascript|2085273|这也可能会稍微快一点(如果比较花费的时间比逐位and长)：|2085274|inline+int+len(uint32_t+val)+{
++++if+(val+&+~0x00FFffFF)+{
++++++++return+4;
++++if+(val+&+~0x0000ffFF)+{
++++++++return+3;
++++}
++++if+(val+&+~0x000000FF)+{
++++++++return+2;
++++}
++++return+1;|2085275|}|2085276|如果你使用的是8位微控制器(如8051或AVR)，那么这将是最好的：|2085277|inline+int+len(uint32_t+val)+{
++++union+int_char+{+
++++++++++uint32_t+u;
++++++++++uint8_t+a[4];
++++}+x;
++++x.u+=+val;+//+doing+it+this+way+rather+than+taking+the+address+of+val+often+prevents
+++++++++++++++//+the+compiler+from+doing+dumb+things.
++++if+(x.a[0])+{
++++++++return+4;
++++}+else+if+(x.a[1])+{
+++++++return+3;
++++...|2085278|由tristopia编辑:上一个变体的字节顺序感知版本|2085279|int+len(uint32_t+val)
{
++union+int_char+{
++++++++uint32_t+u;
++++++++uint8_t+a[4];
++}+x;
++const+uint16_t+w+=+1;

++x.u+=+val;
++if(+((uint8_t+*)&w)[1])+{+++//+BIG+ENDIAN+(Sparc,+m68k,+ARM,+Power)
+++++if(x.a[0])+return+4;
+++++if(x.a[1])+return+3;
+++++if(x.a[2])+return+2;
++}
++else+{++++++++++++++++++++++//+LITTLE+ENDIAN+(x86,+8051,+ARM)
++++if(x.a[3])+return+4;
++++if(x.a[2])+return+3;
++++if(x.a[1])+return+2;
++}
++return+1;
}|2085280|由于const，任何称职的编译器只会为正确的字节顺序生成代码。|2085281|entityMap^0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Y|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|Z|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|10|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|11|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|12|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|13|8|@]|9|@]|A|$]]|$1|O|3|P|5|D|7|14|8|@]|9|@]|A|$E|F]]|$1|Q|3|R|5|6|7|15|8|@]|9|@]|A|$]]|$1|S|3|T|5|D|7|16|8|@]|9|@]|A|$E|F]]|$1|U|3|V|5|6|7|17|8|@]|9|@]|A|$]]|$1|W|3|-4|5|6|7|18|8|@]|9|@]|A|$]]]|X|$]]

On some systems this could be quicker on some architectures:

<pre><code>inline int len(uint32_t val) {
 return (int)( log(val) / log(256) ); // this is the log base 256 of val
}
</code></pre>

This may also be slightly faster (if comparison takes longer than bitwise and):

<pre><code>inline int len(uint32_t val) {
 if (val &amp; ~0x00FFffFF) {
 return 4;
 if (val &amp; ~0x0000ffFF) {
 return 3;
 }
 if (val &amp; ~0x000000FF) {
 return 2;
 }
 return 1;
</code></pre>

}

If you are on an 8 bit microcontroller (like an 8051 or AVR) then this will work best:

<pre><code>inline int len(uint32_t val) {
 union int_char { 
 uint32_t u;
 uint8_t a[4];
 } x;
 x.u = val; // doing it this way rather than taking the address of val often prevents
 // the compiler from doing dumb things.
 if (x.a[0]) {
 return 4;
 } else if (x.a[1]) {
 return 3;
 ...
</code></pre>

EDIT by tristopia: endianness aware version of the last variant

<pre><code>int len(uint32_t val)
{
 union int_char {
 uint32_t u;
 uint8_t a[4];
 } x;
 const uint16_t w = 1;

 x.u = val;
 if( ((uint8_t *)&amp;w)[1]) { // BIG ENDIAN (Sparc, m68k, ARM, Power)
 if(x.a[0]) return 4;
 if(x.a[1]) return 3;
 if(x.a[2]) return 2;
 }
 else { // LITTLE ENDIAN (x86, 8051, ARM)
 if(x.a[3]) return 4;
 if(x.a[2]) return 3;
 if(x.a[1]) return 2;
 }
 return 1;
}
</code></pre>

Because of the const, any compiler worth its salt will only generate the code for the right endianness.

blocks|key|2085286|text|根据您的架构，您可能会有一个更有效的解决方案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2085287|MIPS有一个"CLZ“指令，它计算一个数字的前导零位的数量。您在这里寻找的本质上是4+-+(CLZ(x)+/+8)+(其中/是整数除法)。PowerPC具有等效的指令cntlz，而x86具有BSR。这个解决方案应该简化到3-4条指令(不包括函数调用开销)和零分支。|offset|length|style|CODE|2085288|entityMap|0|LINK|mutability|MUTABLE|url|http://publib.boulder.ibm.com/infocenter/aix/v6r1/index.jsp?topic=/com.ibm.aix.aixassem/doc/alangref/cntlzw.htm|1|http://siyobik.info/index.php?module=x86&id=20^0|0|16|G|1Q|1|2C|5|2O|3|2C|5|0|2O|3|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@$D|T|E|U|F|G]|$D|V|E|W|F|G]|$D|X|E|Y|F|G]|$D|Z|E|10|F|G]]|9|@$D|11|E|12|1|13]|$D|14|E|15|1|16]]|A|$]]|$1|H|3|-4|5|6|7|17|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]|P|$5|K|L|M|A|$N|Q]]]]

You may have a more efficient solution depending on your architecture.

MIPS has a "CLZ" instruction that counts the number of leading zero-bits of a number. What you are looking for here is essentially <code>4 - (CLZ(x) / 8)</code> (where <code>/</code> is integer division). PowerPC has the equivalent instruction <a href="http://publib.boulder.ibm.com/infocenter/aix/v6r1/index.jsp?topic=/com.ibm.aix.aixassem/doc/alangref/cntlzw.htm" rel="nofollow noreferrer"><code>cntlz</code></a>, and x86 has <a href="http://siyobik.info/index.php?module=x86&amp;id=20" rel="nofollow noreferrer"><code>BSR</code></a>. This solution should simplify down to 3-4 instructions (not counting function call overhead) and zero branches.

I'd like a shortcut for the following little function, where
performance is very important (the function is called more than 10.000.000 times):

<pre><code>inline int len(uint32 val)
{
 if(val &lt;= 0x000000ff) return 1;
 if(val &lt;= 0x0000ffff) return 2;
 if(val &lt;= 0x00ffffff) return 3;
 return 4;
} 
</code></pre>

Does anyone have any idea... a cool bitoperation trick?
Thanks for your help in advance!

Is there a more efficient way to get the length of a 32bit integer in bytes?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我想要以下小函数的快捷方式，其中性能非常重要(该函数被调用超过10.000.000次)：inline int len(uint32 val){ if(val <= 0x000000ff) return 1; if(val <= 0x0000ffff) return 2; if(val <= 0x00f...

问有没有更有效的方法来获取32位整数的字节长度？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问有没有更有效的方法来获取32位整数的字节长度？EN