wake-up-neo.net

schnellste Weg, um eine Zahl zu negieren

Ich habe heute morgen hier nachgedacht, was der schnellste Weg wäre, eine Reihe von Positiven in Negative umzuwandeln und von Negativ zu Positiv. Der einfachste Weg könnte natürlich sein:

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

oder

int a = 10;
a = -a;

Aber dann, dachte ich, nehme ich das mit den Befehlen shift und pointers ... Ist es wirklich möglich, das Vorzeichen eines Werts zu ändern, mit den Befehlen shift operator und memory?

c++cintelvisual-c++-2012
31
Alexandre

Der erste produziert:

    .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

Die zweite produziert:

    .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

Gleiche Ausgabe! Kein Unterschied im produzierten Montagecode.

-------------------------- BEARBEITEN, OP-ANTWORTEN, DIE ER VC++ 2012, INTEL Arch verwendet ----------- --------

Kompiliert mit 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

und mit dem zweiten Ansatz (a = a * -1)

; 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
22
Aniket Inge

Verwenden Sie etwas, das lesbar ist, wie z

a *= -1;

oder

a = -a;

Überlassen Sie den Rest dem Optimierer.

37
Armen Tsirunyan

Die anderen Antworten haben zu Recht darauf hingewiesen, dass Lesbarkeit mehr zählt:

  • Sie sollten die Geschwindigkeit vergessen und die Redewendung wählen, die Sie am lesbarsten finden.
  • Fast alle Compiler (mit aktivierten Optimierungen) wissen, dass a = -a und a *= -1 genau gleich sind und geben aus, was auch immer sie auf der Ziel-CPU am effizientesten finden, unabhängig davon, wie Sie sie schreiben. (z. B. Godbolt Compiler Explorer für x86 gcc/MSVC/clang und ARM gcc.)
    • Obwohl MSVS 2012 (nur im Debug-Modus) eine Anweisung für jede verwendet, dauert es jedoch für einen 1-Code für = -a und 3 für *= -1 auf aktuellen Intel-CPUs, wobei eine tatsächliche imul-Anweisung verwendet wird.
  • Jeder Versuch, es schneller zu machen, macht es weitaus weniger lesbar und kann es leicht verlangsamen.
  • Wenn Sie optimieren müssen, sollten Sie zunächst den generierten Code und die Leistung analysieren.


Es gibt jedoch einen praktischen Vorteil gegenüber der *= -1-Idiom: Sie müssen nur die linke Seite einmal schreiben, sie wird nur einmal ausgewertet - und der Leser muss sie nur einmal lesen! Dies ist relevant, wenn die LHS lang, komplex oder teuer ist oder Nebenwirkungen haben kann:

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

Und wenn man erst einmal ein Idiom angenommen hat, bleibt man in anderen Situationen dran.

6
PJTraill

Auch 0 - n

Gcc gibt die "neg" -Anweisung für alle vier Fälle aus: -n, 0 - n, n * -1 und ~ n + 1

3
Jeremy

Angenommen, der Prozessor ist zumindest etwas kompetent und hat sizeof(int) == sizeof(Cpu_register), dann ist ein "diese Zahl negativ machen" eine einzelne Anweisung (normalerweise als neg bezeichnet) Alles andere kann es nach dem Laden bleiben und erst später gespeichert werden ...]

Das Multiplizieren mit -1 ist wahrscheinlich langsamer als a = -a;, aber die meisten kompetenten Compiler sollten in der Lage sein, beide gleichwertig zu machen. 

Schreiben Sie also einfach den Code klar und der Rest sollte für sich sorgen. Das Negieren einer Zahl ist bei den meisten Prozessoren nicht schwierig. Wenn Sie einen ungewöhnlichen Prozessorsor verwenden, schauen Sie sich die Compiler-Ausgabe an und sehen Sie, was sie tut.

3
Mats Petersson

Lösung mit Hochsprache

Fragen wie diese sind in Interviews und in der Programmierwelt von Wettbewerbern sehr beliebt.

Ich bin hier gelandet, um nach einer Lösung für die Negation einer Zahl zu suchen, ohne den Operator - oder + zu verwenden. 

Dafür :

  1. zahl mit dem Operator ~ ergänzen 
  2. Dann addiere 1 zu der in Schritt 1 erhaltenen Zahl unter Verwendung der Halbaddiererlogik:
> int addNumbers(int x, int y)
>       {
>                    if(y==0)  return x; // carry is 0 
>                    return addNumbers(x^y,(x&y)<<1);
>         }

Hier führt x ^ y die Addition von Bits durch und die x & y-Handle-Carry-Operation 

1
Divyanshu Jimmy