2

与えられた 3 つの数値の提案された解決策として、それらの 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 は問題を指摘しました。

intandの特異な問題a ^ b ^ c ^ smallest ^ largestは、まれな非 2 の補数プラットフォームで中間結果がトラップ表現になる可能性があることです。– チュークス

@chux説明してください？XOR はビットごとに動作するだけで、ビットが何を表しているかは気にしませんよね? – 200_成功

XOR は気にしませんが、結果が問題になる可能性があります。たとえば、符号と絶対値の整数の場合、トラップ値が発生してコードが停止する可能性があります-1 ^ 1。-0C11 §6.2.6.2 を参照してください。– チュークス

さらに、C11 §6.2.6.2 3 では、まれな非 2 の補数プラットフォームでの int を使用した ^ の実装定義の動作を指定しています。特に、「これらのケースが実際に負のゼロまたは通常のゼロを生成するかどうかは指定されていません」 ^ b ^ c ^ 最小 ^ 最大の未指定をレンダリングすると、トラップ値が使用されていない場合でも、必要に応じて機能します。次のセクションでは、これが UB になる方法について説明します。この斬新なコードは unsigned 型に任せるのが最善です。– チュークス

論理的にも数学的にも正しいはずの技術が、専門性によって狂ってしまうのは残念なことです。

この 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 Simple Constraintsも参照してください。

その後：

$ 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 で動作します。*.SSolaris Studio 12 以前や Visual Studio x64 などのホールドアウトについては、アセンブラによってアセンブルされ、C/C++ コード (つまり、または*.asmファイル)から呼び出されるアセンブリ ソース ファイルに含まれる関数が必要です。

Solaris Studio 12では GCC インライン アセンブリのサポートが追加されたため、以前のバージョンの Sun Studio ではアセンブラが必要でした。Windows Win32 は Intel 構文でインライン ASM をサポートしていますが、X64 ではインライン アセンブリがないため、MASM を使用する必要があります。

于 2016-11-22T19:33:19.513 に答える