Leetcode Problem 1009 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 complement.

My solution -

class Solution {
public:
    int bitwiseComplement(int n) {
        int k=1;
        if(n==0){
            return k;
        }
        long int binary=0,i=0;
        while(n){
            long int bit=n&1;
            if(bit==0){
                bit=1;
            }
            else{
                bit=0;
            }
            binary=(bit*pow(10,i))+binary;
            n=n>>1;
            i++;
        }
        long int ans=0,j=0;
        while(binary!=0){
            long int digit=binary%10;
            ans=digit*pow(2,j)+ans;
            j++;
            binary=binary/10;
        }
        
        
        return ans;
        
    }
};

What is my mistake here?
All my testcases ran successfully but When input is 299475, Output is 224816, Expected output is 224812.
Please help me.

As others in the comments have suggested, there's the bit-flip operator ~ that inverses all the bits in an integer

A number like "5" is this in binary. Assuming a 32-bit integer.

0000000 0000000 0000000 0000101

And so applying this:

int n = 5;
n = ~5;

Produces this for n:

11111111 11111111 11111111 11111010

oops, that's like -6, not 2 like the problem wanted. You need to re-twiddle those leading 1 bits and stop when you encounter the first 0 (from left to right).

Putting it altogether.

int bitwiseComplement(int n) {

    if (n == 0)
    {
        return 1; // special case
    }

    int i = ~n;
    size_t bits = sizeof(n) * 8;

    // it's always a good idea to do bit-twiddling exercises
    // in the unsigned space - especially for the right shift
    unsigned int mask = 1 << (bits-1);  // this should be 0x80000000
    while (mask & i)                    // while the bit in u matching the bit in mask are both set
    {
        i = mask ^ i;                   // toggle the bit in u to zero
        mask = mask >> 1;               // mask gets shifted (e.g. 0x80000000 to 0x40000000)
    }
    return i;
}

c++20 added many useful bit-related functions. If you can find one that produces the convenient base 111...111 (with appropriate number of ones) then you can xor (^=) your original number. Such a number is easily produced by subtracting 1 from the result of std::bit_ceil.

It's more reliable to cast to unsigned. You'll also need an up-to-date compiler.

Sadly, n=0 is a special case.

#include <iostream>
#include <bit>
 
int bitwiseComplement( int n )
{ 
   return n ? n ^= std::bit_ceil( n + 1u ) - 1 : 1;
}

int main()
{
   std::cout << bitwiseComplement( 299475 );
}

Output:

224812

selbie's answer is very good. Also, that answer shows that using the ~ operator requires further work to be done. Here is another solution that works. It is somewhat simpler with less number of binary operations.

class Solution {
public:
    int bitwiseComplement(int n) {
        
        if(n==0){
            return 1;
        }
        int comp_op=0;
        int i=0;
        while(n){
            int bit=n&1;
            int add_val = 0;
            if (bit == 0)
                add_val = 1<<i;
            comp_op += add_val;
            n >>= 1;
            i++;
        }
        return comp_op;
    }
};

selbie's point about doing bit twiddling operations with unsigned integers is very true. In this case, the Leet Code problem let's us assume that the number is non-negative (0 <= n < 10^9). Also, the problem statement is not clear what to do when n = 0. The above code is accepted by Leet Code and we could assume that 1 is the expected output when n = 0. Also, they mention that problem 1009 is the same as another one (leetcode.com/problems/number-complement), where the range of n is 1 <= n < 2^31, which is unambiguous.

If in a bit-twiddling problem, n can be negative, a while loop progressing and exiting based on n>>1 is not a good idea. We should progress the while loop based on number of bits in the representation of the number as it is done in selbie's answer. However, if this Leet Code problem has to be re-framed to allow negative input numbers, the statement of the problem has to be refined carefully and clearly, as to what to expect as output.

As per Aconcagua's comments below,

int bit=n&1;
int add_val = 0;
if (bit == 0)
    add_val = 1<<i;
comp_op += add_val;

can be compactly implemented as,

comp_op |= (!(n&1)) << i;