这个问题与语言无关,但我将使用 C,因为这就是我编码的内容。
给定两个跨越 n_word< 的整数 a
和 b
/code> 每个单词,比较这些多单词数字的最有效方法是什么,例如确定 a < b? (†)
作为一个具体示例,我们可以将 a
和 b
视为长度为 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 = 200
和 b = 123< /code>(其中 a > b
)的计算结果与 a = 100
和 b = 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.
发布评论
评论(1)
看来你的担心(有不止一个比较)是没有根据的。
ASM
指令CMP
设置 FLAG 寄存器,并且两个条件跳转都是基于这些标志执行的。请参阅https://godbolt.org/z/rfxP185Mf
It appears that your concern (that there is more than one comparison) is unfounded.
The
ASM
instructionCMP
sets the FLAG register, and both conditional jumps are performed based on those flags.Please see https://godbolt.org/z/rfxP185Mf