Bitwise subtraction in Python

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?

From stackoverflow

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

• 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.

  Robert Gamble : I think you would need to change the behavior of the left-shift operator, see my edited response.

  Robert Gamble : 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.

• if i,j are two integers: addition

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