побитовое Вычитание в Python

Question

Это является продолжением до my question yesterday:

CMS любезно предоставил этот пример использования битовых операторов для сложения двух чисел в 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; 
} 

Он отлично работает, а затем я портировал это на Python следующим образом:

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) 

Они оба работают для добавления, а программа C также работает для вычитания. Однако программа Python вводит бесконечный цикл для вычитания. Я пытаюсь разобраться в этом и разместил программу здесь для дальнейших экспериментов: http://codepad.org/pb8IuLnY

Может ли кто-нибудь посоветовать, почему существует разница между тем, как C обрабатывает это и способ, которым обрабатывает CPython?

Answer 1

Shifting отрицательных чисел не имеет непротиворечивую интерпретацию между питон и С.

Answer 2

Как я указал в своем ответе на CMS «ответ вчера сдвига влево отрицательное число не определено поведение в C, так это ISN» t даже гарантированно работает на C (проблема в том, как обрабатывать подписанный бит, вы смещаете его как бит ценности или на него не влияет сдвиг? Комитет по стандартам не мог согласиться с поведением, поэтому он остался неопределенным).

Когда это происходит для работы в C, он полагается на фиксированные целые числа бит, так что крайний левый бит сбрасывается с конца, когда вы выполняете сдвиг (для этого также требуется, чтобы бит знака считался битом значения для сдвига цели). Все целые типы в C являются фиксированными битами, но числа Python могут быть сколь угодно большими. Левый сдвиг число в Python просто заставляет его продолжать получать больше:

>>> 1 << 100 
1267650600228229401496703205376L 

Вы могли бы попробовать что-то вроде этого:

x = (a << 1) & 0xffffffff 

Чтобы ограничить результат до 32 бит, проблема заключается в том, что левый оператор сдвига в Python не сдвигает знаковый бит подписанного числа (что является частью того, что требуется для того, чтобы это конкретное решение работало). Возможно, есть способ изменить поведение оператора сдвига, но я не знаю, как это сделать.

Answer 3

если i, j два целых числа:

аддитивные:

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

Answer 4

Я заметил, что Вы предполагаете, что питон работы с числами так же, как это делает C.
Это не совсем так. Значение int int numbres имеет фиксированную длину 16 бит. Для получения подробной информации о типах C вы можете обратиться к C_data_types on en.wikipedia.org
С другой стороны, Pyhton имеет практически бесконечную длину для чисел int.
Добавление положительных целых чисел может работать одинаково. Но вычитание или добавление отрицательных целых чисел не должно быть простым преобразованием отображения.
Простой способ понять это небольшой пример на отрицательных чисел: Представьте фиксированную длину целое представление 3 бита:

Unsigned

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

Подпись:

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

Это работает здорово, потому что вы может видеть, что 1-3=1+(-3), -3 - 101 это 5, если без знака. Таким образом, 1+5=6, 6: 110: -2. Это означает, что 1-3=-2.
он также становится багги при переполнении: - -4 + -1 = 3 нет -5 потому что это вне допустимого диапазона! - 3 + 1 = -4 нет 4 потому что это вне допустимого диапазона!

Как вы можете видеть, это работает для фиксированной длины, но в Python это не работает.