Python 中的按位减法

Question

这是 我昨天的问题：

CMS 善意地提供了这个在 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;
}

效果很好，然后我将其移植到 Python 中，如下所示：

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)

它们都适用于加法，而 C 程序适用于减法以及。 然而，Python 程序进入减法的无限循环。 我试图弄清楚这一点，并在此处发布该程序以进行进一步的实验： http://codepad.org/ pb8IuLnY

谁能告诉我为什么 C 处理这个问题的方式和 CPython 处理这个问题的方式会有区别吗？

Answer 1

正如我昨天在对 CMS 的回答的回复中指出的，左移负数在 C 中是未定义的行为，所以这甚至不能保证在 C 中工作（问题是如何处理有符号位，你会移动它吗？就像一个值位或者它不受转变的影响吗？标准委员会无法就行为达成一致，因此它未定义）。

当这种情况在 C 中发生时，它依赖于固定位宽整数，因此当您进行移位时，最左边的位会被推到末尾（它还需要将符号位视为用于移位目的的值位）。 C 中的所有整数类型都是固定位的，但 Python 数字可以是任意大。 在Python中左移一个数字只会导致它变得越来越大：

>>> 1 << 100
1267650600228229401496703205376L

你可以尝试这样的事情：

x = (a << 1) & 0xffffffff

要将结果限制为32位，问题是Python中的左移运算符不会移动a的符号位有符号数（这是使该特定解决方案发挥作用所需的一部分）。 可能有一种方法可以改变轮班操作员的行为，但我不知道如何做。

Answer 2

负数移位在 python 和 C 之间没有一致的解释。

Answer 3

如果i、j是两个整数：

加法：

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

Answer 4

我注意到您假设 python 处理数字的方式与 C 相同。
这并不完全正确。 这意味着 C 的 int 数字具有 16 位的固定长度。 有关 C 数据类型的详细信息，您可以参考 en.wikipedia.org 上的 C_data_types
另一方面，据说 Python 的 int 数字实际上具有无限长度。
添加正整数可能会以同样的方式工作。 但负整数的减法或加法不应该是简单的映射转换。
理解这一点的一个简单方法是一个关于负数的小例子：
想象一下 3 位的固定长度整数表示：
#无符号#

• 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
• < code>110 : -2
• 111 : -1

这很酷，因为你可以看到 1-3=1+(-3), -3 是101 如果无符号，则为 5。 所以 1+5=6, 6 : 110 : -2。 这意味着 1-3=-2。
当溢出时它也会变得有问题：

• -4 + -1 = 3而不是-5，因为它超出了范围！
• 3 + 1 = -4 不是 4，因为它超出了范围！

正如您所见，这适用于固定长度，但在 Python 中却行不通。

Answer 5

对于任何仍然感兴趣的人，要解决 python 中的问题，只需添加一个新的 case 并切换函数内 x 和 y 的顺序，并返回负值，虽然这在函数中添加了“-”，但这提供了一种方法使用按位运算符。 对于仍然希望在以下问题中使用运算符“-”进行争论的人，我可以认为对于 2 - 6 的情况，正确的答案是 -4，其中答案中存在“-”，因此可以添加当x小于y时。 希望这可以帮助。

#使用位运算符将两个整数相减
#参考：https://www.geeksforgeeks.org /不使用算术运算符减去两个数字/

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