The given code fails for larger values even after changing variable from int to double to long

Question

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

Do not use pow for integer-based problems. The pow is a floating point function, and with that, you will inherit all the issues associated with floating point calculations (such as inexact results). — PaulMcKenzie
– PaulMcKenzie, Commented Nov 9, 2023 at 7:19
Just as a side note: ~number already gives you the binary complement in one single operation... And 'base 10' is misleading if you want to calculate binary complements, as there's a base10 complement as well: 647 gets 352 – and their bit patterns are not complements in binary… — Aconcagua
– Aconcagua, Commented Nov 9, 2023 at 7:28
Wait a second – you are trying to calculate a number that, in base 10, has the same digits as the original number in binary? That number will get much larger than the original one if that one is large, too, most likely won't fit into int, thus you suffer from overflow (undefined behaviour for signed integers!). long on many systems (e.g. windows – in contrast to e.g. 64-bit linux) has the same size as int so wouldn't help out either, instead try long long (or don't rely on system's sizes at all and try uint64_t from cstdint header. — Aconcagua
– Aconcagua, Commented Nov 9, 2023 at 7:35
Be aware, too, that, in general, if you are operating on bit patterns only then unsigned types are better choice, not suffering from left-shifting values into negative (UB actually, too) if values get too large. — Aconcagua
– Aconcagua, Commented Nov 9, 2023 at 7:36
Why do you calculate the result as a base 10 binary number? Why not just calculate the result directly? (a = a + b << i) — Alan Birtles
– Alan Birtles, Commented Nov 9, 2023 at 7:37

Aconcagua · Accepted Answer · 2023-11-09 08:44:12Z

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, ...).

10¹⁰ 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 2¹⁰ - 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 2²⁰ - 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 10¹⁵ precisely, thus 2¹⁶ - 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;
}

Collectives™ on Stack Overflow

The given code fails for larger values even after changing variable from int to double to long

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related