4
\$\begingroup\$

This is the code I came up with.

I added comments to make the solution more verbose.

int findComplement(int num) {
    // b is the answer which will be returned
    int b = 0;

    // One bit will be taken at a time from num, will be inverted and stored in n for adding to result
    int n = 0;

    // k will be used to shift bit to be inserted in correct position
    int k = 0;

    while(num){
        // Invert bit of current number
        n = !(num & 1);

        // Shift the given number one bit right to accesss next bit in next iteration
        num = num >>1 ;

        // Add the inverted bit after shifting
        b = b + (n<<k);

        // Increment the number by which to shift next bit
        k++;
    }
    return b;
}

Is there any redundant statment in my code which can be removed? Or any other better logic to invert bits of a given integer

\$\endgroup\$
3
  • 6
    \$\begingroup\$ Are you re-inventing the binary not operator (~)? \$\endgroup\$
    – Martin R
    Aug 10 '19 at 17:37
  • \$\begingroup\$ I don't want to sound dumb, But honestly, I did not know that ~ operator existed which inverts all bits of a given integer. \$\endgroup\$
    – KshitijV97
    Aug 10 '19 at 18:10
  • 1
    \$\begingroup\$ Many easy ways. ~num or -1 - num, or 0xFFFFFFFF - num, or 0xFFFFFFFF ^ num or (-1) ^ num. Doing it one bit at a time is most definitely the hard way. \$\endgroup\$
    – AJNeufeld
    Aug 10 '19 at 19:17
3
\$\begingroup\$

int n = 0; This initialization is not used. It could simply be int n;, or could be int n = !(num & 1); inside the loop, to restrict the scope of n.


This loop:

int k = 0;
while (num) {
    ...
    k++;
}

could be written as:

for(int k = 0; num; k++) {
    ...
}

Since you are doing bit manipulation, instead of using addition, you should probably use a “binary or” operation to merge the bit into your accumulator:

    b = b | (n << k);

or simply:

    b |= n << k;

Bug

You are not inverting the most significant zero bits. Assuming an 8-bit word size, the binary compliment of 9 (0b00001001) should be 0b11110110, not 0b00000110. And the compliment of that should return to the original number (0b00001001), but instead yields 0b00000001.


And, as mentioned by @Martin R, you could simply return ~num;

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.