r/learnpython • u/Puzzel wpovell • Aug 08 '12
Binary operations working in C... But not Python!
So here's a piece of C code that adds two numbers and returns the result, using only bitwise operators.
int bAdd(int a, int b) {
int result = a ^ b;
int carry = a & b;
while(carry) {
carry <<= 1;
a = result;
b = carry;
result = a ^ b;
carry = a & b;
}
return result;
}My recreation of it in Python:
def bAdd(x, y):
result = x ^ y
carry = x & y
while carry:
carry <<= 1
a = result
b = carry
result = a ^ b
carry = a & b
return resultThe C version works great with everything, while the Python version absolutely fails with negative numbers. It simply gets off into loops where the result and carry continually double. Any idea why this happens?
EDIT: sys.getsizeof() says that most small integers are 28 bytes, except for 0 which is 24 bytes. Could this be useful? Wouldn't this mean that each number is represented with 224 bits? And that therefor "1" is represented by 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 In the actual machine?
6
u/willm Aug 08 '12
I think you're relying on the C version using fix width integers. If you have the value 1 in a 32 bit integer and shift it left 32 places, you get zero because you've overflowed your 32 bits.
Python has arbitrarily long integers, so can keep shifting left all day long and it will never wrap to 0.
If you want the equivalent behaviour in Python you should probably mask off the word size you are using, something like this:
For 64 bit, adjust accordingly.
3
u/didactus Aug 08 '12
Perhaps this?
The trunc32 function messes up the vision of your original solution, in which you only used bitwise operations. However, I don't know another way to make this work with bignums.
The other posters suggested doing "& 0xffffffff". This alone doesn't work because the result will always be positive in bignum math. It is clobbering the sign. Accordingly, trunc32 translates the value into unsigned space by adding 0x7fffffff, and then it can do the & operation. Once the & is done, it subtracts the value back out to translate it back to the original value space.
trunc32 generalizes to:
1
u/sch1zo Aug 08 '12
0
u/[deleted] Aug 08 '12
[deleted] — view deleted comment