la forma más rápida de negar un número


Estaba pensando esta mañana aquí, cuál sería la forma más rápida de revertir un número de positivo a negativo y de negativo a positivo, por supuesto, la forma más simple podría ser:

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

O

int a = 10;
a = -a;

Pero entonces, pensé, tomo eso para hacer esto, usando los comandos shift y punteros ... Que realmente sería posible cambiar el signo de un valor, utilizando comandos shift operadores y memoria?

Author: Peter Wood, 2013-02-27

7 answers

El primero produce:

    .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

El segundo produce:

    .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

Misma salida! No hay diferencia en el código de ensamblaje producido.

--------------------------EDITAR, OP RESPUESTAS QUE UTILIZA VC++2012, INTEL ARCH-------------------

Compilado usando 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

Y con segundo enfoque (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
 21
Author: Aniket Inge,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-02-27 12:46:45

Use algo que sea legible, como

a *= -1;

O

a = -a;

Deje el resto al optimizador.

 37
Author: Armen Tsirunyan,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-02-27 11:56:08

Las otras respuestas han indicado correctamente que la legibilidad importa más:

  • Debe olvidarse de la velocidad y elegir el idioma que encuentre más legible.
  • Casi todos los compiladores (con optimizaciones habilitadas) entienden que a = -a y a *= -1 son exactamente iguales y emitirán cualquier asm que decidan que será más eficiente en la CPU de destino, independientemente de cómo lo escriba. (por ejemplo, Godbolt compiler explorer para x86 gcc/MSVC/clang, y ARM gcc.)
    • Pero aunque MSVS 2012 (solo en modo de depuración) usa una instrucción para cada uno, toman 1 ciclo para = -a y 3 para *= -1 en CPU Intel recientes, usando una instrucción real imul.
  • Cualquier intento de hacerlo más rápido hará que sea mucho menos legible y fácilmente podría hacerlo más lento.
  • Si necesita optimizar, debe comenzar por analizar el código generado y el rendimiento.


Hay sin embargo una ventaja práctica a la *= -1 modismo: solo tienes que escribir el lado izquierdo una vez, solo se evalúa una vez - ¡y el lector solo tiene que leerlo una vez! Esto es relevante cuando el LHS es largo, complejo o costoso o puede tener efectos secundarios:

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

Y una vez que uno ha adoptado un idioma, uno tiende a quedarse con él en otras situaciones.

 5
Author: PJTraill,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-11-09 03:53:36

Suponiendo que el procesador es al menos algo competente y tiene sizeof(int) == sizeof(Cpu_register), entonces un "make this number negative" será una sola instrucción (generalmente llamada neg) [bueno, puede necesitar el valor de carga y almacenamiento también, pero si está utilizando la variable para cualquier otra cosa, puede permanecer después de la carga, y solo se almacenará más tarde...]

Multiplicarse por -1 es probablemente más lento que a = -a;, pero la mayoría de los compiladores competentes deberían ser capaces de hacer ambos equivalentes.

Así que, solo escribe el código claramente, y el resto debe cuidarse solo. Negar un número no es una operación difícil en la mayoría de los procesadores. Si está usando algún processsor inusual, entonces mire la salida del compilador, y vea lo que hace.

 3
Author: Mats Petersson,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-02-27 12:03:57

También 0-n

Gcc emite la instrucción " neg " para los cuatro casos: - n, 0-n, n * -1, y ~n + 1

 3
Author: Jeremy,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-02-28 17:57:16

Solución usando lenguaje de alto nivel

Preguntas como estas son populares en entrevistas y en el mundo de la programación competitiva .

Aterricé aquí investigando más solución para la negación de un número sin usar el operador - o+.

Para esto :

  1. complementar un número usando ~ operador
  2. Luego agregue 1 al número obtenido en el paso 1 usando la lógica de media sumadora:
> int addNumbers(int x, int y)
>       {
>                    if(y==0)  return x; // carry is 0 
>                    return addNumbers(x^y,(x&y)<<1);
>         }

Aquí x^y realiza la adición de bits y las manijas x e y llevan la operación

 1
Author: Divyanshu Jimmy,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-01-25 10:47:45

Puedes probar

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

Pero no debería preocuparse por eso, porque compilador lo hace de la mejor manera.

 -2
Author: Alexander,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-02-27 12:02:14