# Python – Bitwise subtraction in Python

low-levelpython

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?

#### Best Solution

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.