尝试在 C++ 中计算汉明权重时发生溢出

Question

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

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 的错误：

Line 9: Char 18: runtime error: signed integer overflow: 1073741824 * 2 cannot be represented in type 'int' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior solution.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

现场演示

旁注：
64 位

double

确实有足够的位来表示

2147483645

，因此，如果将转换更改为

double

，您应该得到与没有转换相同的结果（请参阅最小演示）。

您可以在此处查看有关浮点表示限制的更多信息：哪个是 IEEE 754 浮点数无法准确表示的第一个整数？。

Answer 2

您可以比较数字类型可表示的二进制位数：

#include <limits>

constexpr std::numeric_limits<float> float_meta;
constexpr std::numeric_limits<int> int_meta;

std::cout<< "integer binary digits: " << int_meta.digits;
std::cout<< "float mantissa digits: " << float_meta.digits;

在典型的平台上，这些值可能是 31 和 24。这意味着

1<<30

远远超出了

float

类型的精度。

表达式

a<=(float)n/2

在计算结果之前将所有整数值（包括

a

）提升（转换）为

float

。如果

a

的值大于

(1<<24)-1

，则转换为 float 会失去精度，这被认为是 UB。

您的编译环境在编译代码之前正在运行清理程序，并且它甚至在尝试编译代码之前就捕获了问题。请注意输出中的术语 UndefinedBehaviorSanitizer。您的代码在编译之前就失败了。这也表明编译环境不允许任何 UB（通常在家庭/个人设置中被编译器忽略）。因此，在尝试此挑战之前，您必须学习 C++ 基础知识（包括 UB）。 您可以通过在转换前验证您的号码来避免此特定警告/错误：

#include <bit>

unsigned int a = 1;
while((std::bit_width(a) < float_meta.digits)
   && (a<=(float)n/2))
{/**/};

或者只是通过不转换为

float

来避免原因：

#include <bit>
unsigned hammingWeight(unsigned n) {
    return std::popcount(n);
};

此代码仅计算无符号数中 1 位的数量。根据平台的不同，

<bit>

中的std函数可能会使用编译器内部函数，将计算成本简化为单个操作码。如果输入应该是

signed

，则

std::popcount(std::bit_cast<unsigned>(n))

给出全范围

signed

的结果，无 UB。