2

作为给定三个数字的建议解决方案，找到其中第二大的数字，我写道：

int second_largest(int a, int b, int c) {
    int smallest = min(min(a, b), c);
    int largest = max(max(a, b), c);

    /* Toss all three numbers into a bag, then exclude the
       minimum and the maximum */
    return a ^ b ^ c ^ smallest ^ largest;
}

这个想法是^ smallest ^ largest取消位，以便保留中间数字。

但是，@chux 指出了一个问题：

int和的一个独特问题a ^ b ^ c ^ smallest ^ largest是中间结果可能是罕见的非 2 补码平台上的陷阱表示。– 楚克斯

@chux请解释一下？XOR 只是逐位运算，并不关心位代表什么，对吧？– 200_成功

XOR 不在乎，但结果可能是一个问题：例如，使用符号幅度整数，可能-1 ^ 1会-0出现一个陷阱值 - 停止代码。参见 C11 §6.2.6.2 2. 位运算更好地用于无符号类型。– 楚克斯

进一步的 C11 §6.2.6.2 3 在罕见的非 2 的补码平台上指定 ^ 的实现定义行为 int 。特别是“未指定这些情况是否实际生成负零或正常零”，渲染 a ^ b ^ c ^ minimum ^ maximum 未指定即使不使用陷阱值它也会按需要工作。下一节将解释这如何成为 UB。最好将这个新颖的代码留给无符号类型。– 楚克斯

不幸的是，一种在逻辑上和数学上应该是合理的技术可能会因技术性而脱轨。

有没有办法挽救这种 XOR 技术并使其合法安全，理想情况下运行时开销为零？（可能涉及工会的事情？）

4

1 回答 1

0

有没有办法挽救这种 XOR 技术并使其合法安全，理想情况下运行时开销为零

使用内联汇编。汇编语言不受 C/C++ 规则的约束。

也许像下面这样。

$ cat test.c 
#include <stdio.h>
#include <stdlib.h>

#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))

int second_largest(int a, int b, int c)
{
    int s = min(min(a, b), c);
    int l = max(max(a, b), c);

    int result;
    __asm volatile (
    "mov %1, %0    \n\t"
    "xor %2, %0    \n\t"
    "xor %3, %0    \n\t"
    "xor %4, %0    \n\t"
    "xor %5, %0    \n\t"
        : "=r"(result)
        : "g"(a), "g"(b), "g"(c), "g"(s), "g"(l)
    );

    return result;
}

int main(int argc, char* argv[])
{
    int n = second_largest(10,20,30);
    printf("Result: %d\n", n);

    return 0;
}

上面的r机器约束意味着一个寄存器。上面的g机器约束意味着寄存器、内存位置或立即数。另请参阅GCC 手册的第 6.42.1 节简单约束。

接着：

$ gcc -Wall -Wstrict-overflow=5 test.c -o test.exe
$ ./test.exe 
Result: 20

以下是objdump --disassemble test.o编译后的-O3. 看起来开销保持在最低限度。看起来字节 0x00-0x17 执行minand max; 看起来xor是在字节 0x18-0x20 处执行的。

0000000000000000 <second_largest>:
   0:   39 d7                   cmp    %edx,%edi
   2:   89 d0                   mov    %edx,%eax
   4:   89 d1                   mov    %edx,%ecx
   6:   0f 4e c7                cmovle %edi,%eax
   9:   39 f0                   cmp    %esi,%eax
   b:   0f 4f c6                cmovg  %esi,%eax
   e:   39 d7                   cmp    %edx,%edi
  10:   0f 4d cf                cmovge %edi,%ecx
  13:   39 f1                   cmp    %esi,%ecx
  15:   0f 4c ce                cmovl  %esi,%ecx
  18:   89 f8                   mov    %edi,%eax
  1a:   31 f0                   xor    %esi,%eax
  1c:   31 d0                   xor    %edx,%eax
  1e:   31 c0                   xor    %eax,%eax
  20:   31 c8                   xor    %ecx,%eax
  22:   c3                      retq

内联汇编的缺点是它并非无处不在。与上述类似的 IA-32 代码适用于 BSD、Linux、OS X、某些 Solaris 和某些 Windows。*.S对于保留，如 Solaris Studio 12 或 Visual Studio x64 之前的版本，您将需要在由汇编程序汇编并从 C/C++ 代码（即 a或*.asm文件）调用的汇编源文件中提供的函数。

Solaris Studio 12添加了对 GCC 内联汇编的支持，因此早期版本的 Sun Studio 需要汇编程序。Windows Win32 支持 Intel 语法中的内联 ASM，但 X64 要求您使用 MASM，因为没有内联汇编。

于 2016-11-22T19:33:19.513 回答