Topic source

• leetcode

Title Description

Topic analysis

The difficulty lies in how to deal with negative numbers

Pre knowledge

(1) Why does one hexadecimal number correspond to four binary numbers?

• • ... it can be understood that there are 16 digits in hexadecimal (because the number of digits is called radix, represented by R, called r-ary), that is, there are 16 characters represented by one hexadecimal number N - bit binary code can represent two different characters to the nth power If a hexadecimal number is represented by a binary number, the n-bit binary number needs to represent 16 characters, so the n-th power of two is equal to 16 and N is equal to four Therefore, one hexadecimal number can be represented by four binary numbers, that is, one hexadecimal number corresponds to four binary numbers

(2) Unsigned right shift

• Unsigned right shift means that the sign problem is not considered when moving right, that is, whether moving right is a positive number or a negative number, the highest bit is supplemented by 0. When the ">" sign is shifted to the right in the normal operation, that is, when the ">" sign is shifted to the right in the normal operation, when the ">" sign is shifted to the right, it is simply shifted to the right in the normal operation, that is to say, when the ">" sign is shifted to the right in the normal operation.
• In java, the unsigned shift right operator "> > >" is provided to distinguish it from the ordinary "> >". However, there is no such operator in c + +, and the implementation method in c + + is also very simple. First convert the number to be unsigned right to unsigned type, and then perform ordinary right shift.

thinking

• First convert the 32-bit integer of type int to binary

• Because the binary bit corresponding to a hexadecimal number is 4 bits, there is the following mapping relationship

• Negative number scenario: for example, the hexadecimal bit of - 1, the operation of negative number depends on complement, and the original code should be converted to complement first

realization

Step 1: we need to record the mapping first
Step 2: we need to perform int -- > binary -- > hexadecimal

Question: how to convert binary to hexadecimal?

• The binary is grouped and processed every 4 bits
• How do you get four? Use 1111 and &. For ex amp le, the decimal corresponding to 1111 is 1 * 2 ^ 3 + 1 * 2 ^ 2 + 1 * 2 ^ 1 + 1 * 2 ^ 0 = 8 + 4 + 2 + 1 = 15,

• After the first four bits are processed, considering the negative number, it should move four bits to the right without sign to process the next four bits
  • If it is a signed right shift, the negative number will fill the high position with 1, resulting in an endless loop (the signed right shift of the negative number will fill the high position with 1, and the unsigned right shift of the high position will always fill 0)
    

public String toHex(int num) {
        if (num == 0) return "0";
        char[] hexChars = {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};

        String res = "";
        while (num != 0) {
            int index = num & 15;  //Get the 4-digit index. 15 is the decimal system of 1111
            res = hexChars[index] + res; //Because it is processed from low to high, it is spliced to the front
            num >>>= 4;  //Note: considering the negative number, it should be unsigned right shift, otherwise it will be signed right shift, the high position will always be filled with 1, and the loop will be closed
        }
        return res;
    }

Analog + binary conversion

First of all, we can use the general idea of base conversion to do it, and constantly cycle the operations of num% k and num / k to construct each bit of k base.

But we need to deal with the problem of "complement": for the num of negative numbers, we need to add the complement to the num first 2 32 2^{32} 232
And then carry out hexadecimal conversion.

class Solution {
public:
    string toHex(int num){
        if(num == 0){
            return "0";
        }
        std::string ans;
        long conv_num = num;
        if(conv_num < 0){
            conv_num = (long)(std::pow(2, 32) + conv_num);
        }
        while (conv_num != 0){
            long u = conv_num % 16;
            conv_num /= 16;
            char c;
            if(u >= 10){
                c = (char)(u - 10 + 'a');
            }else{
                c = (char)(u + '0');
            }
            ans.push_back(c);
        }
        std::reverse(ans.begin(), ans.end());
        return ans;
    }
};

You only need to change the parameter type of the topic to unsigned int, so you don't have to consider the strange shifts of negative numbers 23333

class Solution {
public:
    string toHex(int num){
        constexpr auto str = "0123456789abcdef";
        string ans;
        unsigned int conv_num = num;
        while (conv_num){
            ans = str[conv_num & 0xf] + ans;
            conv_num >>= 4;
        }
        return ans.empty() ? "0" : ans;
    }
};

[note] the core idea is to use bit operation. Every four bits correspond to one hexadecimal digit.

• Use 0xf(00... 01111b) to obtain the lower 4 bits of num.

• Arithmetic displacement, in which the positive number moves to the right and the left is supplemented by 0, and the negative number moves to the right and the left is supplemented by 1.

• The displacement operation cannot guarantee num==0, and 32-bit int is required (corresponding to hexadecimal less than or equal to 8 bits).

class Solution {
public:
    string toHex(int num){
        if(num == 0){
            return "0";
        }
        string hex = "0123456789abcdef", ans = "";
        while (num != 0 && ans.size() < 8){
            ans = hex[num & 0xf] + ans;
            num >>= 4;
        }

        return ans;
    }
};

Bit operation

The topic requires that the given integer num is converted into hexadecimal number, and the negative integer is calculated by complement.

• In the complement operation, the highest bit represents the sign bit, the sign bit is 0, which represents a positive integer and 0, and the sign bit is 1, which represents a negative integer
• The binary number of a 32-bit signed integer has 32 bits
• Since one hexadecimal number corresponds to a 4-bit binary number, the hexadecimal number of a 32-bit signed integer has 8 bits

We can divide the binary number of num into 8 groups according to 4 bits, and convert each group into the corresponding hexadecimal number in turn to get the hexadecimal number of num.

Assuming that the 8 groups of binary numbers from low to high are group 0 to group 7, for group I, the value of this group can be obtained through (Num > > (4 * I)) & 0xf, and its value range is 0 to 15 (i.e. hexadecimal f). Convert the values of each group to hexadecimal numbers as follows:

• For 0 to 9, the number itself is hexadecimal
• For 10 to 15, convert it to the corresponding number in a to f

For negative integers, leading zeros do not appear because the highest order must not be 0. Leading zeros may occur for 0 and positive integers. Avoid leading zeros as follows:

• If num == 0, 0 is returned directly
• If num > 0, when traversing the values of each group, it is spliced into hexadecimal numbers from the first value that is not 0

class Solution {
public:
    string toHex(int num) {
        if (num == 0) {
            return "0";
        }
        string sb;
        for (int i = 7; i >= 0; i --) {
            int val = (num >> (4 * i)) & 0xf;
            if (sb.length() > 0 || val > 0) {  //Let's explain "leading zero" here. For example, enter: 26 and the result is: 1a. Worry about: 01a this result. In addition, yif (sb. Length() > 0 | Val > 0) {solves the problem that there will be no 0 at the beginning and can be 0 in the middle. It is well written.
                char digit = val < 10 ? (char) ('0' + val) : (char) ('a' + val - 10);
                sb.push_back(digit);
            }
        }
        return sb;
    }
};