Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.
Note:
- The given integer is guaranteed to fit within the range of a 32-bit signed integer.
- You could assume no leading zero bit in the integer’s binary representation.
Example 1:
1 2 3 |
Input: 5 Output: 2 Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2. |
Example 2:
1 2 3 |
Input: 1 Output: 0 Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0. |
Solution
1 2 3 4 5 6 7 |
public class NumberComplementSolution { public int findComplement(int num) { int mask = (Integer.highestOneBit(num) << 1) - 1; num = ~num; return num & mask; } } |
If you have still not understood the solution, the below debugging will help you understand better.
Debug the solution
1 2 3 4 5 6 7 8 9 10 11 12 |
public static void main(String[] args) { int i = 5; System.out.println("Binary Reprsentation of "+ i + " : " + Integer.toBinaryString(i)); int highestOneBit = Integer.highestOneBit(i); System.out.println("Highest one bit : " + Integer.toBinaryString(highestOneBit)); int shiftBit = highestOneBit << 1; System.out.println("Shift bit : " + Integer.toBinaryString(shiftBit)); int mask = shiftBit - 1; System.out.println("Mask is : " + Integer.toBinaryString(mask)); System.out.println("Invert " + i + " : " + Integer.toBinaryString(~i)); System.out.println("Final result : " + Integer.toBinaryString(~i & mask)); } |
Output
1 2 3 4 5 6 |
Binary Reprsentation of 5 : 101 Highest one bit : 100 Shift bit : 1000 Mask is : 111 Invert 5 : 11111111111111111111111111111010 Final result : 10 |
You may also like Java interview questions
References
https://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#highestOneBit(int)
https://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#toBinaryString(int)