-1
\$\begingroup\$

Here is my code:

package com.app;

public class Solution {

    // Suppose the operation ~ doesn't exist
    public int invertBinaryNumber(int n) {
        int singleOne = 1;
        int singleZero = 0xfffffffe;
        while (singleOne != 0) {
            if ((n & singleOne) == 0) {
                n |= singleOne;
            } else {
                n &= (singleZero);
            }
            singleZero <<= 1;
            singleZero |= 1;
            singleOne <<= 1;
        }
        return n;
    }

}

And there are a few tests:

package com.app;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class SolutionTest {

    @Test
    void one() {
        Solution solution = new Solution();
        assertEquals(~1, solution.invertBinaryNumber(1));
    }

    @Test
    void even() {
        Solution solution = new Solution();
        assertEquals(~12, solution.invertBinaryNumber(12));
    }

    @Test
    void odd() {
        Solution solution = new Solution();
        assertEquals(~37, solution.invertBinaryNumber(37));
    }

    @Test
    void intMax() {
        Solution solution = new Solution();
        assertEquals(~Integer.MAX_VALUE, solution.invertBinaryNumber(Integer.MAX_VALUE));
    }

    @Test
    void intMin() {
        Solution solution = new Solution();
        assertEquals(~Integer.MIN_VALUE, solution.invertBinaryNumber(Integer.MIN_VALUE));
    }

}

The problem seems to be pretty easy. However, it took me some time to make it work with negative numbers and some edge cases. So I'd greatly appreciate if you noticed any bugs in my code.

\$\endgroup\$
  • \$\begingroup\$ are you required to invert the bits one by one? Or does the challenge allow you to use default arithmetic operations? \$\endgroup\$ – Vogel612 Nov 4 '18 at 10:48
  • \$\begingroup\$ @Vogel612 suppose I can use any operations except for ~ \$\endgroup\$ – Maksim Dmitriev Nov 4 '18 at 14:06
  • \$\begingroup\$ I'm not sure whether this code is working as expected or not? Could you clarify? \$\endgroup\$ – t3chb0t Nov 4 '18 at 15:06
4
\$\begingroup\$

The code works, which I have double-checked with an exhaustive test. An exhaustive test for this takes a while, but not an unreasonable amount of time, so that can be used just to be 100% certain. Using a few manually-entered test cases is not as reliable for obvious reasons.

There are many simpler ways to do it without a loop, just a couple of operations. For example:

  • XOR by -1: n ^ -1. XOR inverts those bits indicated by the mask, so if the mask indicates all bits it simply inverts all bits.
  • Subtract from -1: -1 - n. Consider the single bit case, subtracting a single bit from 1 would flip it: either subtract 0 and leave 1, or subtract 1 and leave 0. This principle extends trivially to more bits, there is never a borrow so there are no complicated cases to consider. An other way to look at it is using an identity such as x - y = ~(~x + y), then we have -1 - n = ~(~-1 + n) = ~(0 + n) = ~n.
  • Negate and decrement: -n - 1. Negation is defined as -x = ~x + 1 (at least that is one of the definitions), so if we just undo the +1 step we get the plain complement.
  • Increment and negate: -(n + 1). Using the alternative definition of negation, -x = ~(x - 1), cancel the - 1 to get a complement.
\$\endgroup\$
  • \$\begingroup\$ Choice of tests is important - there's a good start in the question, including some of the important boundary cases. I'd also expect to see 0 and some small negative numbers in the test set. You wouldn't want to run the full integer range as a unit test once this is part of a bigger system, of course, but as a one-off, I think that's a great idea. \$\endgroup\$ – Toby Speight Nov 5 '18 at 10:17
2
\$\begingroup\$

To flip a bit, XOR it with 1. To flip all bits, XOR the number with a mask consisting entirely of 1 bits.

Make your function static so that you don't need to instantiate Solution to call it.

public class Solution {
    public static int invertBinaryNumber(int n) {
        return n ^ -1;
    }
}
\$\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.