This was the problem statement.
*Complement of Base 10 Integer
The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.
For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2. Given an integer n, return its complemet*
I saw some solutions to this proble using bit masking, which is something I will get to, but first I want to know why this code given below does not work?
It works for smaller values, but for input: 299475 output: 224816 Expected Output: 224812
And the problem seems to persist for greater values.
#include <math.h>
class Solution {
#include <math.h>
public:
int bitwiseComplement(int n) {
long a = 0;
int i = 0;
if ( n == 0) {
return 1;
}
while ( n != 0 ) {
int b = n & 1;
if ( b == 1) {
b = 0;
}
else if (b == 0){
b = 1;
}
n = n >> 1;
a = a + (b * pow(10, i));
i++;
}
long sol = 0;
int k = 0;
while ( a != 0) {
int b = a % 10;
sol = sol + (b * pow(2, k));
k++;
a = a/10;
}
return sol;}
};
Obviously you are calculating a number of which the decimal representation looks like the binary representation of the original number.
The problem with is that these numbers are much larger than the original ones (e.g. 8 gets 1000, 16 10000, ...).
1010 already won't fit into 32 bits any more (assuming int – signed or unsigned – having that size on your system) – so largest number you can safely convert this way without losing information is 210 - 1 = 1023, any number larger will provoke overflow – and even worse: as you opted for signed integers actually undefined behaviour.
Now long on many systems (e.g. 32-bit linux or windows – in contrast to e.g. 64-bit linux) has the same size as int, so it doesn't help out either in that case; you might possibly try unsigned long long instead or, for not having to rely on OS-specific sizes, uint64_t from <cstdint> header. The largest power of 10 that still fits into then is 19, so the largest number you still can calculate its representation of is now 220 - 1 = 1 048 575. But that's still pretty small…
Now double, in contrast, has even worse precision than an equally sized signed integer as it uses one bit for the sign and 11 bits for an exponent, remaining 52 bits for the mantissa, so 53 bits for the value, including the implicit one, thus allowing to represent 1015 precisely, thus 216 - 1 = 65535 is the maximum value you can calculate the representation of.
Solution to this problem is skipping the intermediate representation in base-10 and calculate the base 2 complement directly:
unsigned int bit = 0;
while(n) // uint32_t!
{
c |= !(n & 1) << bit++; // or 1 - (n & 1), if you prefer...
n >>= 1;
}