是否可以比较两个多字整数,每个字只进行一次比较?

发布于 2025-01-12 19:24:00 字数 1316 浏览 0 评论 0 原文

这个问题与语言无关,但我将使用 C,因为这就是我编码的内容。

给定两个跨越 n_word< 的整数 ab /code> 每个单词,比较这些多单词数字的最有效方法是什么,例如确定 a < b? (†)

作为一个具体示例,我们可以将 ab 视为长度为 n_word 的 8 位整数数组,每个数组代表一个 < code>8*n_word 位整数(并假设大端排序)。(††) 或者,可以使用常规的旧十进制数字来表达问题,例如,a = 456在哪里a[0] 是第一个数字 (4) 等。

我有以下有效的代码,但我想知道是否可以摆脱两个比较之一:

for (unsigned int i = 0; i < n_word; ++i) {
    if (a[i] > b[i]) {
        i = n_word + 1;   /* use as magic number to indicate that a > b */
        break;
    }
    else if (a[i] < b[i]) {
        break;
    }
}

那么结果是由循环后的 i 值确定:

if i < n_word,  then a < b
if i > n_word,  then a > b
if i == n_word, then a == b

但我实际上不想/不需要区分所有三种情况;将两个箱子折叠成一个就完全没问题了。但是,如果我只是删除例如 > 比较而不更改任何其他内容,那么(在十进制示例中)a = 200b = 123< /code>(其中 a > b)的计算结果与 a = 100b = 123(其中 a ),这显然是不正确的。在循环中用 <= 替换 < 似乎同样是假的。


† 虽然 a > b 或其相反的任何一个也是可以接受的。

†† 不,当然,我实际上并不是在尝试比较两个 32 位整数,而是更像是 10 个 32 位整数,它们形成一个非常长的整数,超出了任何本机类型的范围。

This question is independent of language, but I'll use C since that's what I'm coding it in.

Given two integers a and b that span n_word words each, what is the most efficient way of comparing these multi-word numbers, for example determining a < b? (†)

As a concrete example, we could consider a and b to be 8-bit integer arrays of length n_word which each represent one 8*n_word-bit integer (and assume big-endian ordering).(††) Alternatively, the question can be phrased using regular old decimal numbers, e.g., a = 456 where a[0] is the first digit (4) etc.

I have the following code which works, but I'm wondering if it's possible to get rid of one of the two comparisons:

for (unsigned int i = 0; i < n_word; ++i) {
    if (a[i] > b[i]) {
        i = n_word + 1;   /* use as magic number to indicate that a > b */
        break;
    }
    else if (a[i] < b[i]) {
        break;
    }
}

Then the result is determined by the value of i after the loop:

if i < n_word,  then a < b
if i > n_word,  then a > b
if i == n_word, then a == b

But I don't actually want/need to distinguish between all three cases; collapsing two of the cases into one is perfectly fine. However, if I just remove, e.g., the > comparison without changing anything else, then (in the decimal example) a = 200 and b = 123 (where a > b) would evaluate to the same as a = 100 and b = 123 (where a < b), which is clearly incorrect. Replacing < with <= in the loop seems to be equally bogus.


† Though a > b or either of their converses would also be acceptable.

†† And no, of course I'm not actually trying to compare two 32-bit integers, but more like 10 32-bit integers that form one very long integer beyond the reach of any native types.

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

扫码二维码加入Web技术交流群

发布评论

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

评论(1

微暖i 2025-01-19 19:24:00

看来你的担心(有不止一个比较)是没有根据的。

ASM 指令 CMP 设置 FLAG 寄存器,并且两个条件跳转都是基于这些标志执行的。

请参阅https://godbolt.org/z/rfxP185Mf

It appears that your concern (that there is more than one comparison) is unfounded.

The ASM instruction CMP sets the FLAG register, and both conditional jumps are performed based on those flags.

Please see https://godbolt.org/z/rfxP185Mf

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