Given an integer number, invert its bits. You cannot use the ~ operator

Question

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.

Answer 1

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.

Answer 2

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