2008-12-14 40 views
9

Este es un seguimiento de my question yesterday:bit a bit de sustracción en Python

CMS proporcionado amablemente este ejemplo del uso de los operadores bit a bit para sumar dos números en C:

#include<stdio.h> 

int add(int x, int y) { 
    int a, b; 
    do { 
     a = x & y; 
     b = x^y; 
     x = a << 1; 
     y = b; 
    } while (a); 
    return b; 
} 

int main(void){ 
    printf("6 + 3 = %d", add(6,3)); 
    printf("6 - 3 = %d", add(6,-3)); 
    return 0; 
} 

Funciona muy bien y luego portado a Python de la siguiente manera:

def add(x, y): 
    while True: 
     a = x & y 
     b = x^y 
     x = a << 1 
     y = b 
     if a == 0: 
      break 
    return b 

print "6 + 3 = %d" % add(6,3) 
print "6 - 3 = %d" % add(6,-3) 

Ambos trabajan para la suma y el programa C también funciona para la resta. Sin embargo, el programa Python ingresa un bucle infinito para la resta. Estoy tratando de llegar al fondo de esto y he publicado el programa aquí para una mayor experimentación: http://codepad.org/pb8IuLnY

¿Alguien puede decir por qué habría una diferencia entre la forma en que C maneja esto y la forma en que CPython maneja esto?

Respuesta

2

Cambiando los números negativos no tiene una interpretación coherente entre Python y C.

9

Como señalé en mi respuesta a CMS respuesta ayer, izquierda cambiando un número negativo es un comportamiento indefinido en C por lo que este ISN ' Incluso se garantiza que funciona en C (el problema es cómo manejar el bit con signo, ¿lo cambias como un bit de valor o no se ve afectado por un cambio? El comité de estándares no pudo ponerse de acuerdo sobre un comportamiento, por lo que quedó sin definir)

Cuando sucede que esto funciona en C, depende de enteros de ancho de bits fijo, de modo que el bit más a la izquierda se desplaza al final cuando realiza un cambio (también requiere que el bit de signo se trate como un bit de valor para el desplazamiento propósitos). Todos los tipos de enteros en C son de bits fijos, pero los de Python pueden ser arbitrariamente grandes. La izquierda que cambia de un número en Python simplemente hace que se mantenga cada vez más grande:

>>> 1 << 100 
1267650600228229401496703205376L 

Usted podría intentar algo como esto:

x = (a << 1) & 0xffffffff 

Para limitar el resultado de 32 bits, el problema es que la El operador de desplazamiento a la izquierda en Python no desplaza el bit de signo de un número firmado (que es parte de lo que se requiere para que esta solución en particular funcione). Puede haber una manera de cambiar el comportamiento del operador de cambio, pero no sé cómo.

+0

Gracias por la información. ¿Esto significa que no es posible la resta a bit? Todo lo que he leído en línea sugiere convertirlo en un problema de suma bit a bit tomando el complemento de dos del segundo operando. – user23126

+0

Creo que necesitaría cambiar el comportamiento del operador de desplazamiento a la izquierda, vea mi respuesta editada. –

+0

El desplazamiento a la izquierda se define en términos de multiplicación en Python (http://docs.python.org/reference/expressions.html#shifting-operations), por lo que creo que deberá buscar otro enfoque si quiere que esto funcione con números negativos. . –

1

si i, j son dos números enteros:

adición de:

printf("%d",(i^j)|((i&j)<<1)); 
+0

No creo que esto funcione. –

0

me he dado cuenta de que está asumiendo que las obras de pitón con los números de la misma manera que lo hace C.
Eso no es del todo cierto. Significado C's int numbres tiene una longitud fija de 16 bits. Para obtener información detallada sobre los tipos de datos C, puede consultar C_data_types on en.wikipedia.org
Pyhton, por otro lado, se dice que tiene una longitud prácticamente infinita para números enteros.
Agregar enteros positivos puede funcionar de la misma manera. Pero restar o agregar enteros negativos no debe ser una simple traducción de mapeo.
Una manera fácil de entender que esto es un pequeño ejemplo en números negativos: imaginar una representación entera de longitud fija de 3 bits:

sin signo

  • 000: 0
  • 001: 1
  • 010: 2
  • 011: 3
  • 100: 4
  • 101: 5
  • 110: 6
  • 111: 7

firmado:

  • 000: 0
  • 001: 1
  • 010: 2
  • 011: 3
  • 100: -4
  • 101: -3
  • 110: -2
  • 111: -1

Esto funciona bien porque se puede ver que 1-3=1+(-3), -3 es 101 que es 5 si no está firmado. Entonces 1+5=6, 6: 110: -2. Esto significa que 1-3=-2.
también se vuelve defectuoso cuando se desborda: - -4 + -1 = 3 ¡no -5 porque está fuera de rango! - 3 + 1 = -4 ¡no 4 porque está fuera de rango!

Como puede ver, esto funciona para longitud fija pero no funciona de esta manera en Python.