Início / coding / Perguntas / 79010887
Accepted
simply lemon
Asked: 2024-09-22 12:44:57 +0800 CST

Estouro ao tentar calcular o peso de Hemming em C++

  • 772

Estou tentando escrever um código curto que calcula o peso de Hemming de inteiros,

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

porém dá erro para 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

Não entendo como, nunca preciso fazer 1073741824 * 2 no meu cálculo. Além disso, meu código funciona se, em vez de a<=(float)n/2, eu apenas fizer a<=n/2.

c++

2 respostas

  1. Best Answer

    A diferença entre a<=(float)n/2e a<=n/2é que no primeiro, aé convertido para floatpara ser comparado com a floatexpressão (float)n/2.

    Durante essa conversão, alguma precisão é perdida porque a representação de 32 bits floatnão tem bits suficientes para representar 2147483645com precisão.
    Nesse caso, o valor float se torna 2147483648(o valor mais próximo que pode ser representado em a float) que altera o resultado da comparação.

    Você pode observar isso usando este exemplo mínimo:

    #include<iostream>

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

    Saída:

    2147483648.000000

    Demonstração ao vivo

    Uma observação lateral:
    um 64 bits doubletem bits suficientes para representar 2147483645, então se você alterar a conversão para , doubledeverá obter o mesmo resultado que sem a conversão (veja a demonstração mínima ).

    Você pode ver mais informações sobre as limitações das representações de ponto flutuante aqui: Qual é o primeiro inteiro que um float IEEE 754 é incapaz de representar exatamente? .

    • 4

  2. Você pode comparar o número de dígitos binários representáveis ​​para tipos numéricos:

    #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;

    Em uma plataforma típica, os valores podem ser 31 e 24. Isso significa que 1<<30está muito além da precisão do floattipo.

    A expressão a<=(float)n/2promove(converte) todos os valores inteiros (incluindo a) para float, antes de calcular o resultado. Se o valor de afor maior que (1<<24)-1, a conversão para float perde precisão, o que é considerado UB.

    Seu ambiente de compilação está executando um sanitizer antes de compilar o código e ele captura um problema antes mesmo de tentar compilar o código. Observe o termo UndefinedBehaviorSanitizer na saída. Seu código falhou antes mesmo de ser compilado. Isso também sinaliza que o ambiente de compilação não tolera nenhuma UB (que geralmente é ignorada pelo compilador em configurações domésticas/pessoais). Então você tem que aprender o básico de C++ (UB incluído), antes de tentar este desafio. Você pode evitar este aviso/erro específico validando seu número antes da conversão:

    #include <bit>

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

    ou simplesmente evite a causa não convertendo para float:

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

    Este código conta apenas o número de bits 1 em um número sem sinal. Dependendo da plataforma, as funções std em <bit>podem usar intrínsecos do compilador que reduzem o custo do cálculo a um único opcode. Se a entrada for supostamente , signedentão std::popcount(std::bit_cast<unsigned>(n))fornece o resultado para o intervalo completo de signed, sem UB.

    • 0

relate perguntas