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?

Authenticity

Answer 1

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.

Parsimony

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. – Authenticity

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

Left shift is defined in terms of multiplication in Python (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. – Parsimony

Answer 2

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

Blouin

Answer 3

if i, j are two integers:

addition:

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

Beaumont

Answer 4

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.

Messidor

Answer 5

For anyone are still interested, to resolve issue in python, just add a new case and switch the order of x and y inside the function, and return the negative value, though this put "-" in the function, but this presented a way using bit-wise operator. For anyone still wish to argue using operator "-" in the following question, I could argue that for the case of 2 - 6, the right answer is -4 where "-" exists in the answer, so it might be okay to add it when x is smaller than y. Hope this helps.

#A substract to substract two integers using bits operators #refer to: https://www.geeksforgeeks.org/subtract-two-numbers-without-using-arithmetic-operators/

def subtractBits(x, y):
xRAW = x
yRAW = y
if x < y:
    x = y
    y = xRAW

# Iterate till there
# is no carry
while (y != 0):
 
    # borrow contains common
    # set bits of y and unset
    # bits of x
    borrow = (~x) & y
     
    # Subtraction of bits of x
    # and y where at least one
    # of the bits is not set
    x = x ^ y

    # Borrow is shifted by one
    # so that subtracting it from
    # x gives the required sum
    y = borrow << 1

if xRAW < yRAW:
    return -x
else:
    return x

print(subtractBits(100, 50))
print(subtractBits(1, 3))
print(subtractBits(40, 0))
print(subtractBits(0, 40))
print(subtractBits(5, 5))

Hybridism