Bitwise subtraction in Python

Question

This is a follow-up to my question yesterday:

CMS kindly provided this example of using bitwise operators to add two numbers in 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;
}

It works great and I then ported it to Python as follows:

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)

They both work for addition and the C program works for subtraction as well. However, the Python program enters an infinite loop for subtraction. I am trying to get to the bottom of this and have posted the program here for further experimentation: http://codepad.org/pb8IuLnY

Can anyone advise why there would be a difference between the way C handles this and the way CPython handles this?

Robert Gamble · Answer 1 · 2008-12-14T17:32:17.740

As I pointed out in my response to CMS' answer yesterday, left-shifting a negative number is undefined behavior in C so this isn't even guaranteed to work in C (the problem is how to handle the signed bit, do you shift it like a value bit or is it not affected by a shift? The standards committee couldn't agree on a behavior so it was left undefined).

When this happens to work in C it relies on fixed bit-width integers so that the leftmost bit gets pushed off the end when you do a shift (it also requires the sign bit to be treated as a value bit for shifting purposes). All integer types in C are fixed-bit but Python numbers can be arbitrarily large. Left-shifting a number in Python just causes it to keep getting larger:

>>> 1 << 100
1267650600228229401496703205376L

You could try something like this:

x = (a << 1) & 0xffffffff

To limit the result to 32-bits, the problem is that the left shift operator in Python doesn't shift the sign bit of a signed number (which is part of what is required to make this particular solution work). There might be a way to change the behavior of the shift operator but I don't know how.

Thanks for the info. Does this mean that bitwise subtraction is not possible? Everything I've read online suggests turning it into a bitwise addition problem by taking the two's complement of the second operand. — user23126, Dec 14 '08 at 17:12
I think you would need to change the behavior of the left-shift operator, see my edited response. — Robert Gamble, Dec 14 '08 at 17:33
Left shift is defined in terms of multiplication in Python (http://docs.python.org/reference/expressions.html#shifting-operations) so I think you will need to find another approach if want this to work with negative numbers. — Robert Gamble, Dec 14 '08 at 18:20

score 2 · Answer 2 · answered Dec 14 '08 at 17:04

2

Shifting negative numbers doesn't have consistent interpretation between python and C.

answered Dec 14 '08 at 17:04

Douglas Leeder

50,599
9
90
136

score 1 · Answer 3 · edited Aug 21 '12 at 11:33

1

if i, j are two integers:

addition:

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

edited Aug 21 '12 at 11:33

Rostyslav Dzinko

38,056
5
48
60

answered Aug 15 '10 at 13:43

nithin

11
1

score 0 · Answer 4 · edited Jul 05 '20 at 21:47

I've noticed that you're assuming that python works with numbers the same way as C does.
Thats not entirely true. Meaning C's int numbers have a fixed length of 16 bits. For detailed info on C datatypes you can refer to C_data_types on en.wikipedia.org
Python, on the other hand, is said to have a virtually infinite length for int numbers.
Adding positive integers may work the same way. But subtracting or adding negative integers shouldn't be a simple mapping translation.
An easy way to understand this is a little example on negative numbers: Imagine a fixed length integer representation of 3 bits:
#Unsigned#

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

#Signed:#

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

This works cool because you can see that 1-3=1+(-3), -3 is 101 that's 5 if unsigned. So 1+5=6, 6 : 110 : -2. This means that 1-3=-2.
it also becomes buggy when overflowing:

-4 + -1 = 3 not -5 because it's out of range!
3 + 1 = -4 not 4 because it's out of range!

As you may see this works for fixed length but it doesn't work this way in Python.

Bitwise subtraction in Python

4 Answers4