10

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?

5 Answers 5

9

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.

3
  • 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, 2008 at 17:12
  • I think you would need to change the behavior of the left-shift operator, see my edited response. Dec 14, 2008 at 17:33
  • 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. Dec 14, 2008 at 18:20
2

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

1

if i, j are two integers:

addition:

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

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.

0

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))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.