是否可以使用按位和受限运算符重写模 (2^n - 1)

发布于 2024-12-09 06:14:48 字数 227 浏览 0 评论 0原文

对于 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技术交流群

发布评论

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

评论(3

痴者 2024-12-16 06:14:48

是的,这是可能的。对于 255,可以按如下方式完成:

unsigned int x = 4023156861;

x = (x & 255) + (x >> 8);
x = (x & 255) + (x >> 8);
x = (x & 255) + (x >> 8);
x = (x & 255) + (x >> 8);

//  At this point, x will be in the range: 0 <= x < 256.
//  If the answer 0, x could potentially be 255 which is not fully reduced.

//  Here's an ugly way of implementing: if (x == 255) x -= 255;
//  (See comments for a simpler version by Paul R.)
unsigned int t = (x + 1) >> 8;
t = !t + 0xffffffff;
t &= 255;
x += ~t + 1;

// x = 186

如果 unsigned int 是 32 位整数,则此方法有效。

编辑:该模式应该足够明显,以了解如何将其推广到 2^n - 1。您只需计算出需要多少次迭代。对于 n = 8 和 32 位整数,4 次迭代就足够了。

编辑2:

这是一个稍微优化的版本,结合了Paul R.的条件减法代码:

unsigned int x = 4023156861;

x = (x & 65535) + (x >> 16);     //  Reduce to 17 bits
x = (x & 255) + (x >> 8);        //  Reduce to 9 bits
x = (x & 255) + (x >> 8);        //  Reduce to 8 bits
x = (x + ((x + 1) >> 8)) & 255;  //  Reduce to < 255

Yes, it's possible. For 255, it can be done as follows:

unsigned int x = 4023156861;

x = (x & 255) + (x >> 8);
x = (x & 255) + (x >> 8);
x = (x & 255) + (x >> 8);
x = (x & 255) + (x >> 8);

//  At this point, x will be in the range: 0 <= x < 256.
//  If the answer 0, x could potentially be 255 which is not fully reduced.

//  Here's an ugly way of implementing: if (x == 255) x -= 255;
//  (See comments for a simpler version by Paul R.)
unsigned int t = (x + 1) >> 8;
t = !t + 0xffffffff;
t &= 255;
x += ~t + 1;

// x = 186

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. For n = 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:

unsigned int x = 4023156861;

x = (x & 65535) + (x >> 16);     //  Reduce to 17 bits
x = (x & 255) + (x >> 8);        //  Reduce to 9 bits
x = (x & 255) + (x >> 8);        //  Reduce to 8 bits
x = (x + ((x + 1) >> 8)) & 255;  //  Reduce to < 255
£噩梦荏苒 2024-12-16 06:14:48

只需创建一个包含所有值的数组(仅需要 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.

冰魂雪魄 2024-12-16 06:14:48

当然。只需拿出一本旧的计算机体系结构教科书并刷新您对布尔代数的记忆即可。 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?

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文