用 python 编程的 32 位整数中有多少个“1”

Question

我已经成功运行 C++ 中的代码，代码如下：

int countOnes(int num) {
    int count =0;
    while (num) {
        count ++;
        num = num & (num-1);
    }
    return count;
}

但它在 Python 版本中不起作用：

def countOnes(num):
    count = 0
    while(num):
        count += 1
        num = num&(num-1)
    return count

num = -1(0Xffffffff)时好像卡住了，为什么在C++里能用，在python里不行？

Answer 1

Python 没有“32 位整数”。它的整数是任意（读取：无限）长度。这意味着 -1 不是不是 0xffffffff，而是无限长的 1 二进制序列。

Answer 2

此函数在两种语言中的工作方式不同的原因是它们具有不同的基本数字类型。在 C++ 中，int 实际上通常是二进制补码表示形式中的 32 位整数，尽管语言标准允许其他表示形式。然而，在 Python 中，标准数字类型具有任意精度。

循环的继续标准是 num 不为零。如果它没有终止，让我们添加一些调试以查看会发生什么：

def countOnes(num):
    count = 0
    while(num):
        count += 1
        num = num&(num-1)
        print(num) # <-- inspect what happens to num
    return count

让我们看看不同输入的结果：

>>> countOnes(1)
0
1
>>> countOnes(7)
6
4
0
3

然而，对于 -1，事情很快就会失控：

>>> countOnes(-1)
-2
-4
-8
-16
-32
-64
-128
-256
-512
-1024
-2048
-4096
...

num不断减少。由于数字类型具有任意大小，数字只会不断增长。

为了模拟C整数的固定精度，可以限制num为32位：

def countOnes(num):
    num = num & 0xffffffff # <-- Limit num to 32 bits
    count = 0
    while(num):
        count += 1
        num = num&(num-1)
    return count

有了调试输出，countOnes(-1) 的输出现在是：

>>> countOnes(-1)                         
4294967294
4294967292
4294967288
4294967280
4294967264
4294967232
4294967168
4294967040
4294966784
4294966272
4294965248
4294963200
4294959104
4294950912
4294934528
4294901760
4294836224
4294705152
4294443008
4293918720
4292870144
4290772992
4286578688
4278190080
4261412864
4227858432
4160749568
4026531840
3758096384
3221225472
2147483648
0
32

随心所欲:)

Answer 3

您可以创建 32 位表示限制

def countOnes(num):
    num = num % (1 << 32)
    count = 0
    while(num):
        count += 1
        num = num&(num-1)
    return count

用 python 编程的 32 位整数中有多少个“1”

how many '1' in a 32-bits integer programmed with python

python

c++

bit-manipulation