最快的负数取反方法

Question

今天早上我在思考，将一些正数变成负数，将一些负数变成正数的最快方法是什么，当然，最简单的方法可能是：

int a = 10;
a = a*(-1);

或者

int a = 10;
a = -a;

但是，我想，我可以使用shift和指针命令来做到这一点......是否真的有可能使用shift运算符和内存来改变值的符号？

- Alexandre

---

编译器可能会对这样简单的事情进行优化。你可以自己试一下。 - Zeta

同意 Zeta 的观点。选择最易读的选项。 - default

不确定您想使用“指针”做什么，以及为什么认为使用它们比a = -a;更快。事实上，我不明白为什么您认为编译器在编译a = -a;时不一定会使用最有效的实现。 - Mr Lister

除非汇编程序被放置在“inline”位置并明确且不影响代码生成，否则它不太可能产生比编译器更好的代码... - Mats Petersson

编译语言的第一条规则：不要欺骗编译器；否则它会在以后回来咬你。如果你发现编译器做得不好，那就向开发人员提交一个错误报告。优化你的算法，而不是基本操作。 - ams

Answer 1

使用易读的东西，例如：

a *= -1;

或者

a = -a;

把剩下的交给优化器。

- Armen Tsirunyan

Answer 2

在优化被禁用的情况下，x86架构的gcc将第一个编译为以下汇编代码：

    .file   "optimum.c"
    .def    ___main;    .scl    2;  .type   32; .endef
    .text
.globl _main
    .def    _main;  .scl    2;  .type   32; .endef
_main:
    pushl   %ebp
    movl    %esp, %ebp
    andl    $-16, %esp
    subl    $16, %esp
    call    ___main               # MinGW library init function
    movl    $10, 12(%esp) ;i = 10
    negl    12(%esp)      ;i = -i
    movl    $0, %eax
    leave
    ret

关闭优化后，第二个产生的结果为：

    .file   "optimum.c"
    .def    ___main;    .scl    2;  .type   32; .endef
    .text
.globl _main
    .def    _main;  .scl    2;  .type   32; .endef
_main:
    pushl   %ebp
    movl    %esp, %ebp
    andl    $-16, %esp
    subl    $16, %esp
    call    ___main
    movl    $10, 12(%esp)   ;i = 10
    negl    12(%esp)        ;i = -i
    movl    $0, %eax
    leave
    ret

相同的输出！生成的汇编代码没有差别。

--------------------------编辑，问题发布者回答他使用的是VC++2012，英特尔架构-------------------

使用cl optimum.c /Fa optimum.asm进行编译（禁用优化）。

; Listing generated by Microsoft (R) Optimizing Compiler Version 16.00.30319.01 

    TITLE   C:\Users\Dell\Downloads\TTH\TTH\TTH\optimum.c
    .686P
    .XMM
    include listing.inc
    .model  flat

INCLUDELIB LIBCMT
INCLUDELIB OLDNAMES

PUBLIC  _main
; Function compile flags: /Odtp
_TEXT   SEGMENT
_a$ = -4                        ; size = 4
_argc$ = 8                      ; size = 4
_argv$ = 12                     ; size = 4
_main   PROC
; File c:\users\dell\downloads\tth\tth\tth\optimum.c
; Line 4
    push    ebp
    mov ebp, esp
    push    ecx
; Line 5
    mov DWORD PTR _a$[ebp], 10          ; 0000000aH
; Line 6
    mov eax, DWORD PTR _a$[ebp]
    neg eax ;1 machine cycle!
    mov DWORD PTR _a$[ebp], eax
; Line 7
    xor eax, eax
; Line 8
    mov esp, ebp
    pop ebp
    ret 0
_main   ENDP
_TEXT   ENDS
END

使用第二种方法（a = a * -1），禁用了优化 MSVC：

; Listing generated by Microsoft (R) Optimizing Compiler Version 16.00.30319.01 

    TITLE   C:\Users\Dell\Downloads\TTH\TTH\TTH\optimum.c
    .686P
    .XMM
    include listing.inc
    .model  flat

INCLUDELIB LIBCMT
INCLUDELIB OLDNAMES

PUBLIC  _main
; Function compile flags: /Odtp
_TEXT   SEGMENT
_a$ = -4                        ; size = 4
_argc$ = 8                      ; size = 4
_argv$ = 12                     ; size = 4
_main   PROC
; File c:\users\dell\downloads\tth\tth\tth\optimum.c
; Line 4
    push    ebp
    mov ebp, esp
    push    ecx
; Line 5
    mov DWORD PTR _a$[ebp], 10          ; 0000000aH
; Line 6
    mov eax, DWORD PTR _a$[ebp]
    imul    eax, -1 ;1 instruction, 3 machine/cycles :|
    mov DWORD PTR _a$[ebp], eax
; Line 7
    xor eax, eax
; Line 8
    mov esp, ebp
    pop ebp
    ret 0
_main   ENDP
_TEXT   ENDS
END

所以，如果你关心在MSVC下调试模式下汇编代码的性能，你可以相应地优化你的源代码。通常情况下，你只需要关心优化后的构建版本的性能。

- Aniket Inge

---

gcc 不进行优化！ gcc -c optimum.c -S -o optimum.s - Aniket Inge

任何一个像样的、自重的编译器都会生成相同（或类似）的代码。 - Aniket Inge

重点是：不要猜测，不要假设，不要读心 :) 这个问题是关于C或C++的一般性问题。但是，除非您对特定CPU有深入的了解，否则尝试手动优化根本没有任何意义。99%的程序员对这些事情的了解都不比为特定CPU编写编译器端口的人更好。 - Lundin

@Aniket 你应该能在编辑历史记录中看到他的编辑。分别为 movl $10, 12(%esp) // i = 10 和 negl 12(%esp) // i = -i。@GrijeshChauhan 建议你通过评论向发布者提出这样的更改，而不是自己编辑帖子，因为你会改变内容的含义。 - Lundin

@Aniket：MSVS 2012编译是否进行了优化？也许你可以说明一下——也许/Odtp就是这个意思，但这并不明显！只展示列表中的差异可能也是一种友善的方式。 - PJTraill

Answer 3

其他答案已经正确指出可读性更重要：

• 你应该忘记速度，选择你认为最易读的成语。
• 几乎所有编译器（启用优化）会为任何像 a = -a, a *= -1 等等代码生成等效的最优代码（可能是单个指令）。¹
• 任何试图使其更快的尝试都会使其可读性大大降低，并且很容易使其变慢。
• 如果您需要进行优化，则应从分析生成的代码和性能开始。

然而，*= -1 成语有一个实际优势：您只需要写一次左侧，它只被评估一次-并且读者只需要阅读一次！当LHS很长、复杂或昂贵，或者可能具有副作用时，这是相关的：

(valid ? a : b)[prime_after(i++)] *= -1;
*look_up (input) *= -1;  // Where look_up may have side-effects
parity[state][(unsigned int)getc(stdin)] *= -1;
variable_with_a_long_explanatory_name *= -1;

一旦人们采用了某种习语，他们往往在其他情况下也会坚持使用它。

---

¹ _{Peter Cordes的观察：几乎所有编译器都理解a = -a和a *= -1是完全相同的，并将发出无论如何在目标CPU上最有效的汇编代码，无论您如何编写它。(例如Godbolt编译器探索器用于x86 gcc/MSVC/clang和ARM gcc。) 但是，尽管MSVS 2012（仅在调试模式下）对每个操作使用一个指令，但它们在最近的英特尔CPU上需要1个周期进行= -a和3个周期进行*= -1，使用实际的imul指令。}

- PJTraill

Answer 4

还有 0 - n

Gcc 对于所有四种情况都会发出"neg"指令：-n，0 - n，n * -1和~n + 1。

- Jeremy

Answer 5

假设处理器至少有些能力且sizeof(int) == sizeof(Cpu_register)，那么“将这个数字变为负数”将是一条指令（通常称为neg）[可能需要加载和存储值，但如果您在使用变量进行其他操作，则可以在加载后保留该变量，并稍后仅存储该值...]。

乘以-1可能比a = -a;慢，但大多数合格的编译器应该能够使这两者等效。

因此，只需清晰地编写代码，其余部分就会自行处理。在大多数处理器中，取反一个数字并不是很困难的操作。如果使用某些不寻常的处理器，请查看编译器输出并查看它所做的操作。

- Mats Petersson

Answer 6

使用高级语言的解决方案

像这样的问题在面试和竞技编程领域很受欢迎。

我来到这里是为了寻找更多不使用 - 或 + 运算符进行数字否定的解决方案。

具体步骤如下：

1. 使用 ~ 运算符取反一个数字
2. 然后使用半加器逻辑将步骤1中得到的数字加1：

> int addNumbers(int x, int y)
>       {
>                    if(y==0)  return x; // carry is 0 
>                    return addNumbers(x^y,(x&y)<<1);
>         }

在这里，x^y执行比特加法，而x&y则处理进位操作。

- Divyanshu Jimmy

Answer 7

你可以尝试一下

int a = 10;
a= ~a+1;

但你不必担心这个问题，因为编译器会以最佳方式处理它。

- Alexander

---

这将是一个很好的例子，解释了为什么这种优化方式不可取。如此编写代码，会增加操作次数，降低可读性。一个好的编译器可以帮你解决第一个问题，但不能解决第二个问题。 - rici

@rici并且不可移植，因为它依赖于二进制补码。 - Gauthier

@rici：在C抽象机中有更多的操作，但它仍然可以通过gcc/clang/MSVC编译为neg（在像x86和ARM这样的2的补码机器上，这些操作在一条指令中提供）。如果您使用unsigned（并且仅在位操作后转换回int），它具有不在INT_MIN上产生UB的有趣优势，而-a或a * -1将会是有符号溢出。这是唯一的优点。它对可读性很差，而且不可移植。 - Peter Cordes

@peter：虽然我是四年半前写的这个评论，但我认为我可以坚持我的观点。我确实说过一个好的编译器会优化操作，因此gcc、clang等确实这样做与我所写的完全一致。你为什么声称-a对无符号值不确定行为（UB）？ - rici

@rici：我说过 int a = INT_MIN，做 -a 是未定义的行为，但是 (int)(~(unsigned)a + 1) 不是。当然，现在我想想，你可以直接做 (int)-(unsigned)a 得到相同的结果（C++ 实现中的二进制补码/无符号取反，甚至适用于一的补码或正负数表示法）。所以算了，这没有任何优势。（关于效率：我只是说这不会更糟。绝对不是比 - 和 *= -1 更好！正如你所说，它与 - 和 *= -1 的编译结果一样。） - Peter Cordes