Co to znaczy, że bitowe XOR sumy i dwóch addendów są ujemne?

Na przykład, istnieją 3 zmienne typu long, dodajemy a i b i dostać s:Co to znaczy, że bitowe XOR sumy i dwóch addendów są ujemne?

long a, b, s; 
... 
s = a + b

co teraz robi ((s^a) < 0 && (s^b) < 0) oznacza?

widziałem czek takiego w source code Pythona:

if (PyInt_CheckExact(v) && PyInt_CheckExact(w)) { 
     /* INLINE: int + int */ 
     register long a, b, i; 
     a = PyInt_AS_LONG(v); 
     b = PyInt_AS_LONG(w); 
     i = a + b; 
     if ((i^a) < 0 && (i^b) < 0) 
      goto slow_iadd; 
     x = PyInt_FromLong(i); 
    }

Źródło

2015-06-25 satoru

Ten kod jest niepoprawny.

Zakładając zwyczajowe zasady 2's-dopełnienie bitowe XOR dla podpisanych liczb całkowitych, a następnie

(s^a) < 0

jest w przypadku, gdy s i a mają swoje bity znak ustawiony na wartości przeciwne. Zatem

((s^a) < 0 && (s^b) < 0)

wskazuje s ma podpisać różni się od obu a i b, który musi mieć znak równości (udając 0 jest dodatnia). Jeśli dodałeś dwie liczby całkowite równego znaku i otrzymałeś wynik z innego znaku, to musiało nastąpić przepełnienie, więc jest to sprawdzanie przepełnienia.

Jeśli przyjmiemy, że podpisane przepełnienie opakowaniach, to s ma przeciwny znak od a i b dokładnie, gdy wystąpiło przepełnienie. Jednak podpisane przepełnienie jest niezdefiniowanym zachowaniem. Obliczanie s jest już błędne; musimy sprawdzić, czy wystąpi przepełnienie bez faktycznego wykonywania operacji.

Python nie powinien tego robić. Można zobaczyć, co to ma do zrobienia w Python 2 source code for int.__add__:

/* casts in the line below avoid undefined behaviour on overflow */ 
x = (long)((unsigned long)a + b); 
if ((x^a) >= 0 || (x^b) >= 0)

To ma oddanych do unsigned aby zdefiniowane zachowanie przepełnienia. Odrzucona do niepodpisanej poprawka została wprowadzona w 5 różnych miejscach w wyniku issue 7406 na śledzenie błędów Pythona, ale wygląda na to, że przegapili miejsce, lub być może zmieniono od tego czasu INPLACE_ADD. Zostawiłem wiadomość w trackerze.

Źródło

2015-06-25 02:42:43 user2357112

Co masz na myśli przez "podpisane przepełnienie to niezdefiniowane zachowanie"? – satoru

@satoru: Jakiej części nie rozumiesz? Podpisane przepełnienie lub niezdefiniowane zachowanie? Wypisane przepełnienie występuje, gdy wykonujesz operację na podpisanym sygnale i przepełniasz. Niezdefiniowane zachowanie polega na tym, że standard C pozwala implementacji robić cokolwiek, aż do [wciągania demonów przez nos (włącznie) (http: //www.catb.org/jargon/html/N/nosal-demons.html). – user2357112

Dodałem link do pliku, z którego znalazłem ten fragment. – satoru

ja nie wiem, jak to jest możliwe.

Jeśli (s^a) < 0, wówczas nieco znakiem obu s lub a musi być 1, więc albo s lub a (ale nie jednocześnie) musi być ujemny. To samo dotyczy s i b. Tak więc albo s jest ujemny i oba a i b są dodatnie, albo s jest dodatnie i oba są ujemne. Obie sytuacje wydają się niemożliwe.

O ile nie przeliczysz liczby całkowitej/niedomiaru, oczywiście.

Źródło

2015-06-25 02:39:10

Co to znaczy, że bitowe XOR sumy i dwóch addendów są ujemne?

Odpowiedz

Powiązane problemy