尝试用 C++ 计算包边重量时发生溢出

Question

我正在尝试编写一个简短的代码来计算整数的 Hemming 权重，

class Solution {
public:
    int hammingWeight(int n) {
        if(n==0){
            return 0;
        }else{
            int a=1;
            while(a<=(float)n/2){
                a*=2;
            }
            return 1+hammingWeight(n-a);
        }
        
    }
};

但是它给出了 n=2147483645 的错误：

第 9 行：字符 18：运行时错误：有符号整数溢出：1073741824 * 2 无法以“int”类型表示（solution.cpp） 摘要：UndefinedBehaviorSanitizer：未定义行为解决方案.cpp：9：18

我不明白怎么做，我在计算中从来不需要做 1073741824 * 2 。如果我不做

a<=(float)n/2

，而是做

a<=n/2

，我的代码也可以工作。

Answer 1

a<=(float)n/2

和

a<=n/2

之间的区别在于，前者将

a

转换为

float

以与

float

表达式

(float)n/2

进行比较。

在此转换过程中，一些精度会丢失，因为 32 位

float

表示没有足够的位来准确表示

2147483645

。
在这种情况下，浮点值变为

2147483648

（可以用

float

表示的最接近的值），这会改变比较结果。

您可以使用这个最小的示例来观察这一点：

#include<iostream>

int main() {
    int n = 2147483645;
    float f = n;
    std::cout << std::fixed << f;
}

输出：

2147483648.000000