fastest way to negate a number

Question

I was thinking this morning here, what would be the fastest way to reverse a number of positive to negative and from negative to positive, of course, the simplest way might be:

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

or

int a = 10;
a = -a;

But then, I thought, I take that to do this, using commands shift and pointers ... That really would be possible to change the sign of a value, using commands shift operators and memory?

Solution 1

With optimization disabled, gcc for x86 compiles the first to this asm:

    .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

With optimization disabled, the second one produces:

    .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

Same output! No difference in the assembly code produced.

--------------------------EDIT, OP ANSWERS HE USES VC++2012, INTEL ARCH-------------------

Compiled using cl optimum.c /Fa optimum.asm (optimization disabled)

; 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

and with second approach (a = a * -1), optimization disabled 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

So if you care about the performance of your debug-mode asm under MSVC, you could optimize your source accordingly. Normally you only care about performance in optimized builds.

Solution 2

Use something that is readable, such as

a *= -1;

or

a = -a;

Leave the rest to the optimizer.

Solution 3

The other answers have correctly indicated that readability matters more:

• You should forget about speed and choose the idiom that you find most readable.
• Almost all compilers (with optimizations enabled) generate equivalent optimal code (probably a single instruction) for anything like a = -a, a *= -1 etc.¹
• Any attempt to make it faster will make it far less readable and could easily make it slower.
• If you need to optimise, you should start by analysing generated code and performance.

There is however a practical advantage to the *= -1 idiom: you only have to write the left hand side once, it is only evaluated once – and the reader only has to read it once! This is relevant when the LHS is long, complex or expensive or may have side-effects:

(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;

And once one has adopted an idiom, one tends to stick with it in other situations.

---

¹ _{Observations by Peter Cordes: Almost all compilers understand that a = -a and a *= -1 are exactly the same and will emit whatever asm they decide will be most efficient on the target CPU, regardless of how you write it. (e.g. Godbolt compiler explorer for x86 gcc/MSVC/clang, and ARM gcc.) But though MSVS 2012 (in debug mode only) uses one instruction for each, they take 1 cycle for = -a and 3 for *= -1 on recent Intel CPUs, using an actual imul instruction.}

Solution 4

Also 0 - n

Gcc emits the "neg" instruction for all four cases: -n, 0 - n, n * -1, and ~n + 1

Solution 5

Assuming the processor is at least somewhat competent and has sizeof(int) == sizeof(Cpu_register), then a "make this number negative" will be a single instruction (usually called neg) [well, may need the value loading and storing too, but if you are using the variable for anything else, it can remain after the load, and only be stored later one...]

Multiplying by -1 is most likely slower than a = -a;, but most competent compilers should be able to make both of these equivalent.

So, just write the code clearly, and the rest should take care of itself. Negating a number is not a difficult operation in most processors. If you are using some unusual processsor, then look at the compiler output, and see what it does.

View more solutions

Comments

[Zeta]

The compiler will probably optimize such simple things. Try for yourself.

[default]

agree with Zeta. Go for what is most readable

[Dmytro]

I do not understand the context of this problem. If you are not happy with c optimizations, go ahead and use assembly. Honestly, this sounds like premature optimization. if you are interested in how to negate something in "low level way", look at two's complement. cs.cornell.edu/~tomf/notes/cps104/twoscomp.html

[Alexandre]

It's not that, is just a doubts...

[Mr Lister]

Not sure what you want to do with "pointers" and why you think using them would be faster than a = -a;. In fact, I don't understand why you think the compiler would not necessarily use the most efficient implementation when compiling a = -a;.

[Dmytro]

I do not understand why this post was downvoted, I suggested the best possible solution to this problem -- using twos complement in assembly, or using an inbuilt assembly command to negate, and link it with C code.

[Mats Petersson]

Unless the assembler is placed inline and definitely not otherwise affecting the code-generation, it's unlikely to produce better code than the compiler...

[Dmytro]

If done right, it shouldn't be worse.

[Andreas Grapentin]

@Dmitry it could be worse dependent on the context of the negation. in a more complex example, the compiler might decide not to negate at all.

[Dmytro]

I agree, however op was asking explicitly on how to do explicit negation optimally, and from what I gather, is not concerned of optimizations with double negation.

[ams]

Rule 1 of compiled languages: don't lie to the compiler; it'll come back and bite you later. If you find the compiler does a poor job then submit a bug report to the developers. Optimize your algorithms, not your basic operations.

[Aniket Inge]

@Alexandre which computer architecture are you using? which compiler?

[Ed Heal]

Why go to the hassle of doing this in assembly language? Makes the code less readable (maintainable). The compiler will perform the necessary optimizations and will do a good job. If you are worried about this for optimization you would be more fruitful looking at the algorithm as a whole. IMHO - Micro-optimizations of this sort enable very little in savings and are a waste of time.

[vonbrand]

@EdHeal, see ams' Rule #1. If you start writing "clever" code, the compiler can't use its patterns for straightforward code, and will probably generate worse (or even incorrect) code. Plus you won't understand it a week later. It often means worse performance.

[Peter Cordes]

If you're using a compiler that doesn't emit the best possible code for a = -a; and a *= -1;, use a better compiler. (Or enable the correct options for your compiler, e.g. gcc -O3 -march=native.)

[Peter Cordes]

@Dmitry: using inline assembly can easily be worse; it defeats constant-propagation (which can happen after inlining in places you weren't expecting), and it prevents the compiler from understanding what's going on which defeats other optimizations. e.g. if you use a neg instruction in inline asm, it can't fold into later code that adds the negated value to something else. If you'd used a *= -1;, the compiler could just sub instead of neg / add. See gcc.gnu.org/wiki/DontUseInlineAsm.

[Dmytro]

I wrote that comment 4 years ago. You're right, any c or c++ compiler will certainly negate a number in the best possible way, since it's the thing c is best at. Inline assembly will be no better and likely worse, and if there is inline assembly, it'll be at most two instructions, operating on registers without any jumps, nothing could be faster than that other than a nop, which might basically be as fast.

[Aniket Inge]

gcc with no optimizations! gcc -c optimum.c -S -o optimum.s

[Mr Lister]

Stupid question, but how do you know which compiler the OP uses?

[Aniket Inge]

@MrLister any decent self-respecting compiler will produce the same(similar) code.

[Lundin]

And how do you know what CPU the OP uses?

[Mats Petersson]

That was my point - we don't know ANY of those things. But I would still expect the compiler to do a fair job, whatever compiler/processor it is.

[Peter Wood]

OP asks lots of questions about C#, winapi, winforms.

[Aniket Inge]

My guess, OP uses visual studio, x86 or x64(I don't have x64 yet) @PeterWood

[Lundin]

The point is: don't guess, don't assume, don't read minds :) The question was about C or C++ in general. But indeed it doesn't make any sense at all to attempt manual optimizations unless you have in-depth knowledge of the particular CPU. 99% of all programmers do not have better knowledge of such things than the person who wrote the compiler port for the specific CPU.

[Grijesh Chauhan]

I think good answer. What ever compiler OP got he can try with same approach. Additionally if OP bothers to know which faster between a = a*(-1); and a = -a; then he need to(has to) understand low level stuff like this. So I think best answer. Good Aniket!! Only lack of comments in asm code

[Grijesh Chauhan]

@Aniket added little comment i feel will be helpful for OP.

[Aniket Inge]

@GrijeshChauhan ah, re-add it man, I was editing at that time too I think.. I just edited my answer to include output for VC++2010

[Lundin]

@Aniket You should be able to see his edit in the edit history. It was movl $10, 12(%esp) // i = 10 and negl 12(%esp) // i = -i respectively. @GrijeshChauhan it is considered better to suggest such changes to the poster through comments rather than to edit the post yourself, as you would be changing the meaning of the contents.

[rici]

That would be an illustration of precisely why this sort of optimization is a bad idea. As written, it is both more operations and less readable. A decent compiler will help you with the first issue, but not the second one.

[Gauthier]

@rici and non-portable, as it relies on two's complement.

[PJTraill]

@Aniket: Were the MSVS 2012 compilations optimised? Perhaps you could indicate this – perhaps /Odtp means that, but it is not obvious! It might also be kind to present only the differences in the listings.

[Peter Cordes]

@PJTraill: Obviously all of these compiler outputs are with optimizations disabled. (And would optimize away to nothing with optimizations because of a poor choice of test-case.) MSVC is really really stupid with optimizations disabled, it doesn't even use a memory operand with imul to save doing a separate mov load. (i.e. imul eax, DWORD PTR _a$[ebp], -1). I put int mul(int a) { return a * -1; } on Godbolt so we can see the asm with gcc/clang/MSVC. It compiles the same as unary - with every compiler with optimization enabled, including non-x86.

[Peter Cordes]

@rici: It's more operations in the C abstract machine, but it still compiles to a neg with gcc/clang/MSVC godbolt.org/g/C3F3Qx (on 2's complement machines like x86 and ARM which provide these operations in one instruction). If you do it with unsigned (and only convert back to int after the bit manipulation), it has the interesting advantage of not being UB on INT_MIN, while -a or a * -1 would be signed overflow. That is the only advantage though. It's horrible for readability, and not portable.

[rici]

@peter: although i wrote that comment four and a half years ago, i think can stand by it. I did say that a decent compiler would optimize the operations, and so the fact that gcc, clang, etc. do so is entirely consistent with what I wrote. Why do you claim that -a is UB on unsigned values?

[Peter Cordes]

@rici: I claimed that for int a = INT_MIN, it's UB to do -a, but not to do (int)(~(unsigned)a + 1). Of course, now that I think about it, you could just do (int)-(unsigned)a to get the same result (the two's complement/unsigned negation, even on one's complement or sign/magnitude C++ implementations). So nvm, this has zero advantages. (Re: efficiency: I only said that this was not worse. Definitely not that it was better! As you say, it compiles the same as - and *= -1.)