I’m trying to write a short code that calculates the Hamming weight of integers:
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);
}
}
};
However it gives error for 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
I don’t understand how, I never need to do 1073741824 * 2 in my calculation. Also my code works if instead of a<=(float)n/2
, I just do a<=n/2
.
19
The difference between a<=(float)n/2
and a<=n/2
is that in the former, a
is converted to float
to be compared with the float
expression (float)n/2
.
During this conversion some precision is lost because the 32 bit float
representation does not have enough bits to represent 2147483645
accurately.
In this case the float value becomes 2147483648
(the closest value that can be represented in a float
) which changes the comparisson outcome.
You can observe this using this minimal example:
#include<iostream>
int main() {
int n = 2147483645;
float f = n;
std::cout << std::fixed << f;
}
Output:
2147483648.000000
Live demo
A side note:
A 64 bit double
does have enough bits to represent 2147483645
, so if you change the cast to double
you should get the same result as without the cast (see minimal demo).
You can see some more info about limitations of floating point repesentations here: Which is the first integer that an IEEE 754 float is incapable of representing exactly?.
You can compare the number of representable binary digits for numeric types:
#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;
On a typical platform, the values might be 31 and 24. This means that 1<<30
is well beyond the precision of float
type.
The expression a<=(float)n/2
promotes(converts) all the integer values (including a
) to float
, before calculating the result. If the value of a
is larger than (1<<24)-1
, the conversion to float looses precision, which is considered UB.
Your compile environment is running a sanitizer prior to compiling the code and it captures a problem before even trying to compile the code. Mind the term UndefinedBehaviorSanitizer in the output. Your code failed before even being compiled. This also signals you that the compile environment doesn’t tolerate any UB (which is usually ignored by the compiler in home/personal setups). So you have to learn C++ basics (UB included), before trying this challenge.
You can avoid this particular warning/error by validating your number before conversion:
#include <bit>
unsigned int a = 1;
while((std::bit_width(a) < float_meta.digits)
&& (a<=(float)n/2))
{/**/};
or just avoid the cause by not converting to float
:
#include <bit>
unsigned hammingWeight(unsigned n) {
return std::popcount(n);
};
This code only counts the number of 1 bits in an unsigned number. Depending on the platform, std functions in <bit>
may use compiler intrinsics that boil the calculation cost down to a single opcode. If the input is supposed to be signed
then std::popcount(std::bit_cast<unsigned>(n))
gives the result for full range of signed
, with No UB.