是否可以使用按位和受限运算符重写模 (2^n - 1)
对于 unsigned int x,是否可以仅使用以下运算符(不包括循环、分支或函数调用)来计算 x % 255(或一般为 2^n - 1)?
!
、~
、&
、^
、|
、+
、<<
、>>
。
For unsigned int x, is it possible to calculate x % 255 (or 2^n - 1 in general) using only the following operators (plus no loop, branch or function call)?
!
, ~
, &
, ^
, |
, +
, <<
, >>
.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
![扫码二维码加入Web技术交流群](/public/img/jiaqun_03.jpg)
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(3)
是的,这是可能的。对于 255,可以按如下方式完成:
如果
unsigned int
是 32 位整数,则此方法有效。编辑:该模式应该足够明显,以了解如何将其推广到
2^n - 1
。您只需计算出需要多少次迭代。对于 n = 8 和 32 位整数,4 次迭代就足够了。编辑2:
这是一个稍微优化的版本,结合了Paul R.的条件减法代码:
Yes, it's possible. For 255, it can be done as follows:
This will work if
unsigned int
is a 32-bit integer.EDIT: The pattern should be obvious enough to see how this can be generalized to
2^n - 1
. You just have to figure out how many iterations are needed. Forn = 8
and a 32-bit integer, 4 iterations should be enough.EDIT 2:
Here's a slightly more optimized version combined with Paul R.'s conditional subtract code:
只需创建一个包含所有值的数组(仅需要 32 或 64 个条目(即 128 或 512 字节)。然后进行查找。
Just create an array with all the values (only either need 32 or 64 entries (i.e. 128 or 512 bytes). Then just do a look up.
当然。只需拿出一本旧的计算机体系结构教科书并刷新您对布尔代数的记忆即可。 CPU 的 ALU 通过 AND 和 OR 来完成此操作;你也可以。
但为什么?
学术练习?家庭作业?好奇心?
Sure. Just get out one of your old computer architecture textbooks and refresh your memory on boolean algebra. A CPU's ALU does it with ANDs and ORs; you can, too.
But why?
An academic exercise? Homework? Curiousity?