Побитовое вычитание в Python - PullRequest
Новая
       13

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

9 голосов
/ 14 декабря 2008

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

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)

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

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

Ответы [ 4 ]

9 голосов
/ 14 декабря 2008

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

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

>>> 1 << 100
1267650600228229401496703205376L

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

x = (a << 1) & 0xffffffff

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

2 голосов
/ 14 декабря 2008

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

1 голос
/ 15 августа 2010

если i, j - это два целых числа:

дополнение: 

printf("%d",(i^j)|((i&j)<<1));
0 голосов
/ 11 июня 2015

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

...