主页 / coding / 问题 / 79010887
Accepted
simply lemon
Asked: 2024-09-22 12:44:57 +0800 CST

在 C++ 中尝试计算 Hemming 重量时发生溢出

  • 772

我正在尝试编写一个简短的代码来计算整数的 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，它给出了错误：

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。

c++

2 个回答

  1. Best Answer

    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 浮点数无法准确表示的第一个整数是什么？。

    • 4

  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，则转换为浮点数会损失精度，这被视为 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 的位数。根据平台的不同，中的 std 函数<bit>可能会使用编译器内在函数，将计算成本归结为单个操作码。如果输入应该是，signed则std::popcount(std::bit_cast<unsigned>(n))给出全范围的结果signed，没有 UB。

    • 0

相关问题