我一直试图在SO和其他网站上搜索这个具体的答案,但到目前为止还没有得到任何明确的答案。
是否可以使用位运算符找到x % 10
的整数的最后一位?
在我的代码中,我有类似rand() % 10
的东西,我想知道是否有什么可以让它成为一个按位操作,在更少的行可能。
我知道如果你有一个十六进制数,你可以通过以下方式做到这一点:0xABCDE & 0xF == E
0xABCD & 0xF == D
and so on...
然而,这将导致大于10的范围。由于我使用的是随机数生成器,我希望所有这些操作都在from 0 to 9.
范围内,这可能吗?
4条答案
按热度按时间ruarlubt1#
在C中可以用位运算符来生成
x%10
吗?不,不合理。
众所周知,如果
N
是2的幂,则可以通过使用位掩码来有效地计算x%N
。(例如,x%16
是x & 0x0F
,至少只要x
是无符号的。)事实上,这是众所周知的,几乎任何C编译器都知道如何做到这一点。考虑到2的幂模的吸引人的效率和经济性,我们很想为其他除数寻找类似的技巧。不幸的是,数学不工作了。正如这个问题的其他答案所示,虽然从技术上讲,您可以使用按位运算符的精心组合来计算
x%10
,但并不清楚这个练习是否有任何价值。参见Fast division/mod by 10x。最后,如果你想计算
x%10
,用C语言表达它的最佳方式是完全不神奇但显而易见的:如果有比实际除法更好的方法来实现它,请让编译器为您进行优化。代码仍然很明显,因为每个人都知道
x % 10
的意思。(And事实上,尽管我刚才说我不认为有合理的“按位快捷方式”来计算
x % 10
,但事实证明,gcc至少倾向于将该特定表达式编译为一个神秘的、可能更有效的乘法、加法和移位序列,而根本不需要任何DIV指令。如果计算
x%10
被证明是程序中的一个瓶颈,那么应该问,为什么要计算x%10
这么多,有更好的替代方案吗?你提到你有“类似
rand() % 10
的东西”,好像你正在生成单个的、随机的十进制数字。如果这是你需要做的基本事情,可能没有更好的方法了。不过,你浪费了很多rand()
试图给予你的熵。您可能需要考虑一个特殊用途的随机数生成器。或者,如果您要将单个随机数字组合成更大的数字,则可能需要考虑更直接地生成这些更大的数字。当然,
x%10
经常出现的另一个地方是将数字转换为十进制表示时。例如,我曾经写过一个任意精度的算术库,它在内部以二进制工作,当它必须将其中一个大数转换为十进制并将其打印出来时,它可能会花费大量的时间。调整库以在内部使用 decimal 表示,可以让它更有效地以十进制打印内容。(当然,它会使某些其他操作的效率明显降低。如果您要将数字转换为十进制作为序列化格式的一部分,并且如果不要求序列化格式易于阅读,则可以考虑以十六进制而不是十进制序列化整数,因为在这种情况下,转换将涉及一系列
x%16
而不是x%10
的计算。pxyaymoc2#
这个算吗没有循环,没有条件,只有
&
,>>
和数组索引。对于64位支持,请将函数的长度增加一倍。请注意,绝对没有理由使用这段代码,但它确实有效,并且值得理解它。
其工作原理是
tab[a][b]
等于(2*b + a) % 10
。另一种看待它的方式是,我们在DFA中执行32个步骤,从状态0
开始,每个状态都有两个箭头:箭头0
指向(2*n)%10
,箭头1
指向(2*n+1)%10
。最后的状态就是结果。mxg2im7a3#
我想出了这个可行的方法,但可能有一种更优雅的方法来实现它。使用查找表似乎有点像作弊,但我不知道如何摆脱最后几个倍数的10没有分支和循环等。不管怎么说,可能有人会感兴趣。
一个64位的版本也可以用类似的方法构造,但是我选择了一个64位的函数,它调用32位的函数,所有的输入值都经过了检查。
编辑:
一些可能很容易在微控制器上编码的东西,实际上可以扩展为用于32位无符号整数的二进制到十进制转换,如下所示。
编辑2:
如果64位算术是可用的另一种选择,
zengzsys4#
对于0-99范围内的数字,您可以用途:
它不是严格意义上的位运算,而且它是否比余数运算快还值得怀疑。