高效整数比较函数
比较函数是一个函数，它接受两个参数a和b，并返回一个描述其顺序的整数。如果a小于b，则结果为负整数。如果a大于b，则结果为某个正整数。否则，a和b相等，结果为零。
此函数通常用于参数化来自标准库的排序和搜索算法。
实现字符的比较功能相当容易；只需减去参数：
int compare_char(char a, char b)
{
return a - b;
}
这是因为通常假设两个字符之间的差适合一个整数。（注意，此假设不适用于sizeof（char）==sizeof（int）的系统）
这种技巧无法用于比较整数，因为两个整数之间的差通常不适合一个整数。例如，INT\u MAX-（-1）=INT\u MIN表明INT\u MAX小于-1（从技术上讲，溢出会导致未定义的行为，但让我们假设模算术）。
那么，我们如何有效地实现整数的比较函数呢？这是我的第一次尝试：
int compare_int(int a, int b)
{
int temp;
int result;
__asm__ __volatile__ (
"cmp %3, %2 \n\t"
"mov $0, %1 \n\t"
"mov $1, %0 \n\t"
"cmovg %0, %1 \n\t"
"mov $-1, %0 \n\t"
"cmovl %0, %1 \n\t"
: "=r"(temp), "=r"(result)
: "r"(a), "r"(b)
: "cc");
return result;
}
不到6条指令就能搞定吗，有没有不那么直白的方式效率更高呢？
共有3个答案
好的，我设法把它归结为四个说明：）基本思想如下：
一半的时间里，差值小到可以拟合成整数。在这种情况下，只需返回差值。否则，请将数字1向右移动。关键的问题是，然后将什么位转移到MSB中。
让我们看两个极端的例子，为了简单起见，使用8位而不是32位：
10000000 INT_MIN
01111111 INT_MAX
---------
000000001 difference
00000000 shifted
01111111 INT_MAX
10000000 INT_MIN
---------
111111111 difference
11111111 shifted
在第一种情况下移位进位位会产生0（尽管INT_MIN不等于INT_MAX），在第二种情况下会产生一些负数（尽管INT_MAX不小于INT_MIN）。
但是如果我们在换档前翻转进位，我们会得到合理的数字：
10000000 INT_MIN
01111111 INT_MAX
---------
000000001 difference
100000001 carry flipped
10000000 shifted
01111111 INT_MAX
10000000 INT_MIN
---------
111111111 difference
011111111 carry flipped
01111111 shifted
我确信翻转进位有其深刻的数学原因，但我还没有看到。
int compare_int(int a, int b)
{
__asm__ __volatile__ (
"sub %1, %0 \n\t"
"jno 1f \n\t"
"cmc \n\t"
"rcr %0 \n\t"
"1: "
: "+r"(a)
: "r"(b)
: "cc");
return a;
}
我用一百万个随机输入加上INT\u MIN、-INT\u MAX、INT\u MIN/2、-1、0、1、INT\u MAX/2、INT\u MAX/2、INT\u MAX/2、INT\u MAX/1、INT\u MAX的每个组合测试了代码。所有测试均通过。你能证明我错了吗？
以下一直被证明对我来说是相当有效的：
return (a < b) ? -1 : (a > b);
使用gcc-O2-S，这将编译为以下五条指令：
xorl %edx, %edx
cmpl %esi, %edi
movl $-1, %eax
setg %dl
cmovge %edx, %eax
作为Ambroz Bizjak的优秀回答的后续，我不相信他的程序测试了与上面发布的相同的汇编代码。而且，当我更仔细地研究编译器输出时，我注意到编译器生成的指令与我们两个答案中发布的指令不同。所以，我拿了他的测试程序，手工修改了程序集输出，以匹配我们发布的内容，并比较了结果时间。这两个版本的比较似乎大致相同。
./opt_cmp_branchless: 0m1.070s
./opt_cmp_branch: 0m1.037s
我把每个程序的汇编完整地张贴出来，这样其他人就可以尝试同样的实验，并证实或反驳我的观察。
以下是带有cmovge指令的版本（（a
.file "cmp.c"
.text
.section .rodata.str1.1,"aMS",@progbits,1
.LC0:
.string "%d=0\n"
.text
.p2align 4,,15
.globl main
.type main, @function
main:
.LFB20:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
pushq %rbx
.cfi_def_cfa_offset 24
.cfi_offset 3, -24
movl $arr.2789, %ebx
subq $8, %rsp
.cfi_def_cfa_offset 32
.L9:
leaq 4(%rbx), %rbp
.L10:
call rand
movb %al, (%rbx)
addq $1, %rbx
cmpq %rbx, %rbp
jne .L10
cmpq $arr.2789+4096, %rbp
jne .L9
xorl %r8d, %r8d
xorl %esi, %esi
orl $-1, %edi
.L12:
xorl %ebp, %ebp
.p2align 4,,10
.p2align 3
.L18:
movl arr.2789(%rbp), %ecx
xorl %eax, %eax
.p2align 4,,10
.p2align 3
.L15:
movl arr.2789(%rax), %edx
xorl %ebx, %ebx
cmpl %ecx, %edx
movl $-1, %edx
setg %bl
cmovge %ebx, %edx
addq $4, %rax
addl %edx, %esi
cmpq $4096, %rax
jne .L15
addq $4, %rbp
cmpq $4096, %rbp
jne .L18
addl $1, %r8d
cmpl $500, %r8d
jne .L12
movl $.LC0, %edi
xorl %eax, %eax
call printf
addq $8, %rsp
.cfi_def_cfa_offset 24
xorl %eax, %eax
popq %rbx
.cfi_def_cfa_offset 16
popq %rbp
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE20:
.size main, .-main
.local arr.2789
.comm arr.2789,4096,32
.section .note.GNU-stack,"",@progbits
以下版本使用无分支方法（（a
.file "cmp.c"
.text
.section .rodata.str1.1,"aMS",@progbits,1
.LC0:
.string "%d=0\n"
.text
.p2align 4,,15
.globl main
.type main, @function
main:
.LFB20:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
pushq %rbx
.cfi_def_cfa_offset 24
.cfi_offset 3, -24
movl $arr.2789, %ebx
subq $8, %rsp
.cfi_def_cfa_offset 32
.L9:
leaq 4(%rbx), %rbp
.L10:
call rand
movb %al, (%rbx)
addq $1, %rbx
cmpq %rbx, %rbp
jne .L10
cmpq $arr.2789+4096, %rbp
jne .L9
xorl %r8d, %r8d
xorl %esi, %esi
.L19:
movl %ebp, %ebx
xorl %edi, %edi
.p2align 4,,10
.p2align 3
.L24:
movl %ebp, %ecx
xorl %eax, %eax
jmp .L22
.p2align 4,,10
.p2align 3
.L20:
movl arr.2789(%rax), %ecx
.L22:
xorl %edx, %edx
cmpl %ebx, %ecx
setg %cl
setl %dl
movzbl %cl, %ecx
subl %ecx, %edx
addl %edx, %esi
addq $4, %rax
cmpq $4096, %rax
jne .L20
addq $4, %rdi
cmpq $4096, %rdi
je .L21
movl arr.2789(%rdi), %ebx
jmp .L24
.L21:
addl $1, %r8d
cmpl $500, %r8d
jne .L19
movl $.LC0, %edi
xorl %eax, %eax
call printf
addq $8, %rsp
.cfi_def_cfa_offset 24
xorl %eax, %eax
popq %rbx
.cfi_def_cfa_offset 16
popq %rbp
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE20:
.size main, .-main
.local arr.2789
.comm arr.2789,4096,32
.section .note.GNU-stack,"",@progbits
这一个没有分支，不会出现溢出或下溢：
return (a > b) - (a < b);
使用gcc-O2-S，这将编译为以下六条指令：
xorl %eax, %eax
cmpl %esi, %edi
setl %dl
setg %al
movzbl %dl, %edx
subl %edx, %eax
以下是一些用于对各种比较实现进行基准测试的代码：
#include <stdio.h>
#include <stdlib.h>
#define COUNT 1024
#define LOOPS 500
#define COMPARE compare2
#define USE_RAND 1
int arr[COUNT];
int compare1 (int a, int b)
{
if (a < b) return -1;
if (a > b) return 1;
return 0;
}
int compare2 (int a, int b)
{
return (a > b) - (a < b);
}
int compare3 (int a, int b)
{
return (a < b) ? -1 : (a > b);
}
int compare4 (int a, int b)
{
__asm__ __volatile__ (
"sub %1, %0 \n\t"
"jno 1f \n\t"
"cmc \n\t"
"rcr %0 \n\t"
"1: "
: "+r"(a)
: "r"(b)
: "cc");
return a;
}
int main ()
{
for (int i = 0; i < COUNT; i++) {
#if USE_RAND
arr[i] = rand();
#else
for (int b = 0; b < sizeof(arr[i]); b++) {
*((unsigned char *)&arr[i] + b) = rand();
}
#endif
}
int sum = 0;
for (int l = 0; l < LOOPS; l++) {
for (int i = 0; i < COUNT; i++) {
for (int j = 0; j < COUNT; j++) {
sum += COMPARE(arr[i], arr[j]);
}
}
}
printf("%d=0\n", sum);
return 0;
}
在我的64位系统上，使用gcc-std=c99-O2编译正整数（使用RAND=1）的结果：
compare1: 0m1.118s
compare2: 0m0.756s
compare3: 0m1.101s
compare4: 0m0.561s
在纯C语言的解决方案中，我建议的是最快的。尽管只编译了5条指令，但user315052的解决方案速度较慢。速度减慢可能是因为，尽管少了一条指令，但有一条条件指令（cmovge）。
总的来说，当与正整数一起使用时，FredOverflow的4指令汇编实现速度最快。然而，该代码仅对整数范围RAND_MAX进行了基准测试，因此4指令测试是有偏差的，因为它单独处理溢出，并且这些溢出不会在测试中发生；速度可能是由于成功的分支预测。
对于全范围的整数（USE\u RAND=0），4指令解决方案实际上非常慢（其他都是相同的）：
compare4: 0m1.897s
-
问题内容： 我是Java的新手，我刚刚读了一个整数类的变量，可以用API的三种不同方式来描述。我有以下代码： 这是在循环内，只是输出。 我的目标是弄清楚如何查看整数值。 我知道这是正确的方法吗？还是它？ 我知道这是不正确的。这是正确的吗？是否存在值比较运算符？ 问题答案： 整数是自动拆箱的，因此您可以执行
-
我是泛型新手，想解决一个小问题。 我想给两个类型为“V扩展可比”的对象给类ComparePredicate，然后检查方法“isOk”，如果树类的int值“值”在这两个对象之间。我选择了comareTo方法，因为整数和V应该是可比较的类型，但是编译器给出了一个错误。我认为这只是一个句法问题。 那么，我需要如何正确地书写它呢。希望你们能帮我。谢谢你的回答。 类比较谓词 类树
-
有没有一个相当标准的C（Linux）函数，或者一种代码高效但性能良好的方法来比较任意大小的两个整数？ 我正在寻找一些参数为int intcmp（const void*a，const void*b，size\t size）的东西，它适用于任何实际大小的整数。（如果架构是big-endian的话（我认为）可以工作。） 我倾向于使用这样的实现（通过高效整数比较函数的改进），但它不是完全通用的，并且有足够
-
问题内容： 在Java中整数比较是棘手的，因为和表现不同。我明白了。 但是，如本示例程序所示， （第4行）的 行为不同于 （第3行） 。为什么是这样？？ 结果 问题答案： 从JLS 如果装箱的值p为true，false，字节或\ u0000到\ u007f范围内的char或-128到127（含）之间的整数或短数，则令r1和r2为p的任何两次拳击转换。r1 == r2总是这样。 理想情况下，将给定的
-
我有一个充满整数的列表： 现在我想将最高分数与每个分数进行比较，看看哪个分数最高。直觉上，我试着这样做： 然而 所有人都告诉我错误： Compariable和int操作数类型不兼容 然而，这似乎是可行的： 那怎么可能呢？ 为什么Java允许将int设置为集合。max（集合），但不允许将int与集合进行比较。最大值（集合）？
-
上述情况导致 上述条件返回。 为什么会这样？这些片段之间有什么区别？