Побитовое вычитание в Python

Это продолжение мой вопрос вчера:

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 обрабатывает это?


person user23126    schedule 14.12.2008    source источник


Ответы (4)


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

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

>>> 1 << 100
1267650600228229401496703205376L

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

x = (a << 1) & 0xffffffff

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

person Robert Gamble    schedule 14.12.2008
comment
Спасибо за информацию. Означает ли это, что побитовое вычитание невозможно? Все, что я читал в Интернете, предлагает превратить это в задачу побитового сложения, взяв дополнение второго операнда до двух. - person user23126; 14.12.2008
comment
Я думаю, вам нужно изменить поведение оператора сдвига влево, см. мой отредактированный ответ. - person Robert Gamble; 14.12.2008
comment
Сдвиг влево определяется в терминах умножения в Python (docs.python.org/reference /expressions.html#shifting-operations), поэтому я думаю, вам нужно будет найти другой подход, если вы хотите, чтобы это работало с отрицательными числами. - person Robert Gamble; 14.12.2008

Сдвиг отрицательных чисел не имеет согласованной интерпретации между python и C.

person Douglas Leeder    schedule 14.12.2008

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

добавление:

printf("%d",(i^j)|((i&j)<<1));
person nithin    schedule 15.08.2010

Я заметил, что вы предполагаете, что python работает с числами так же, как C.
Это не совсем так. Значение чисел int C имеет фиксированную длину 16 бит. Для получения подробной информации о типах данных C вы можете обратиться к C_data_types на en.wikipedia.org
С другой стороны, Python, как говорят, имеет практически бесконечную длину для целых чисел.
Добавление положительных целых чисел может работать таким же образом. Но вычитание или добавление отрицательных целых чисел не должно быть простым переводом отображения.
Простой способ понять это - небольшой пример с отрицательными числами: представьте целочисленное представление фиксированной длины из 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 это не работает.

person DuniC    schedule 11.06.2015