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.

• Vogel612: are you required to invert the bits one by one? Or does the challenge allow you to use default arithmetic operations?
• Maksim Dmitriev: @Vogel612 suppose I can use any operations except for ~
• t3chb0t: I'm not sure whether this code is working as expected or not? Could you clarify?

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.

• Toby Speight: 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.

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