This is the second day of my participation in the August Text Challenge.More challenges in August

The title is as follows:

Every non-negative integer N has its binary representation. For example, 5 can be represented as binary “101”, 11 as binary “1011”, and so on. Note that there is no leading zero in any binary representation other than N = 0. The binary inverse represents changing every 1 to 0 and every 0 to 1. For example, the binary inverse of the binary number “101” is “010”. Given a decimal number N, return the decimal integer corresponding to the inverse of its binary representation.

For example, if the binary of 5 is 101, the inverse of the binary is 010, and the corresponding decimal integer is 2. Therefore, if you enter the integer 5, you should get the integer 2.

So the first input integer can be converted to binary, and then the binary inverse form, and finally converted to decimal through the inverse code.

How do you do that in code? We can analyze it first:

For the decimal number 11, the binary conversion process is shown in the figure above. Divide 11 by 2 to get the quotient 5, remainder 1. When you divide 5 by 2, you get 2, remainder 1; Finally, divide 2 by 2, you get 1, remainder 0, binary 1011. It follows that by constantly dividing the input number by 2 until the remainder stops at 0, the quotient of the last division concatenates all the remainder from bottom to top to get binary, as follows:

However, in the implementation of the code, we can only divide from the top down, and we can’t know the quotient and remainder of the following in advance. The solution is also very simple: Use a StringBuilder, put the remainder of each division by 2 into The StringBuilder, and reverse the StringBuilder after the division. Then insert the quotient of the last division into the head of the StringBuilder to get the binary.

Once you get the binary, you need to convert the binary to inverse, just loop over the binary number, and replace it with 1 when it’s 0; When it is 1, it is replaced by 0.

The binary in this form is then converted to base 10, and the conversion is very simple: 0 * 2 ^ 3 + 1 * 2 ^ 2 + 0 * 2 ^ 1 + 0 * 2 ^ 0 = 0 + 4 + 0 + 1 = 5, so the final result is 5.

So how do you do that in code? By simply iterating through the binary number and multiplying each digit, for example, the first 0 in 0100 needs to be multiplied by 2 to the third power, and the second 1 needs to be multiplied by 2 to the second power, which can be achieved by subtracting the length of the string by 1 and subtracting the current digit number.

Finally, the code is as follows:

public class Solution {

    public static int bitwiseComplement(int n) {
        // Convert base 10 to base 2
        StringBuilder sb = new StringBuilder();
        while (n / 2! =0) {
            int num = n % 2; // Find the remainder
            sb.append(num); // Save the remainder to StringBuilder
            n = n / 2; / / out
        }
        // Inverts the string and inserts the quotient of the last division at the head of the string
        String binaryNum = sb.reverse().insert(0, n).toString();
        // Convert binary to inverse form
        char[] chars = binaryNum.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '0') {
                // If the value is 0, the value is 1
                chars[i] = '1';
            } else if (chars[i] == '1') {
                // If the value is 1, the value is 0
                chars[i] = '0'; }}// Convert the binary representation back to decimal
        int result = 0;
        for (int i = 0; i < chars.length; i++) {
            // Convert characters to numbers
            int num = Integer.parseInt(chars[i] + "");
            result += num * Math.pow(2, chars.length - 1 - i);
        }
        returnresult; }}Copy the code

Submit to LeetCode:

In fact, there is a very clever solution to this problem, we know that the binary inverse form is converted from the source code, just take the inverse of each bit of the source code, so it can actually get the inverse by all 1 xor with the corresponding binary bits, for example:

The binary source code of 11 is 1011, the whole 1 binary that makes it xor equal, because the rule of xor is same is 0, and different is 1, then the 1 in the source code will be 0 because it is the same, and the 0 in the source code will be 1 because it is different, so it ends up with 0100.

So the next problem is to figure out the number, because you need all 1s of the same number to xor, and we can look for the pattern, for the integer 11, you need all 1s of four digits to xor binary, and 1111 is 15 in decimal; For the integer 5, we need the all-1 binary of three digits to be xor, and the decimal representation of 111 is 7. From this, we conclude that if the all-1 binary is greater than the input integer, then the number of digits must be the same.

We can start with the binary number 1 with only 1 bit. When there is only 1 bit of binary number 1, the corresponding decimal number is 1. When there is a two-bit binary number 11, the corresponding decimal number is 3. When there is a 3-bit binary number 111, the corresponding decimal number is 7. When there is a 4-bit binary number 1111, the corresponding decimal number is 15. The pattern is pretty obvious. This is equal to the previous number to the second power plus 1, which is 2n + 1.

The resulting code:

public static void main(String[] args) {
    double num = 1;
    while (num < 11) {// End the loop when num is greater than 11
        num = num * 2 + 1; // Multiply the base of the previous num by 2 + 1
    }
    System.out.println(num);
}
Copy the code

num = num * 2 + 1; Num = (num << 1) + 1 (num << 1) + 1 (num << 1) + 1 (num << 1) + 1 (num << 1) + 1)

This gives the value that needs to be xor, and then xor directly with the input integer:

class Solution {
    public int bitwiseComplement(int N) {
        int num = 1;
        while(num < N){
            num = (num << 1) + 1;
        }
        returnnum ^ N; }}Copy the code

Submit to LeetCode: