不同进制数的表示形式

二进制：0b

八进制：0

十六进制：0x

int a = 0b001;
int b = 07;
int c = 0xa;
cout << a << endl; // 1
cout << b << endl; // 7
cout << c << endl; // 10

计算机中对数字的表示方法

相关概念

1. 原码：数值绝对值二进制表示+1位符号位（即最高位正数为0，负数为1）

2. 补码：正数补码=原码；

            负数补码=原码除符号位外的所有位取反后加1
   

	+5	-5
原码	0101	1101
补码	0101	1011

注意：0的原码，补码都是0；

      **计算机存储的都是补码**

移位操作

1. 逻辑移位：移位不考虑符号位，即不论左移还是右移，都补0

2. 算术移位：移位考虑符号位，即带符号位的移位

                   正数：无论左移还是右移都是补0；
   
                   负数：左移在右边补0，右移需要在左边补1
   

补充：如果要对负数做逻辑移位，可以****int转unsigned int

#include <limits.h>
int a = -1;
unsigned int b = a;
cout << (b >> 1) << endl;      // 2147483647
cout << ((b >> 1) == INT_MAX); // 1 (true)

参考：https://zhuanlan.zhihu/p/97749860

右移一位和除2的差异

1. 正数：无差异
2. 负数：偶数无差异；奇数有差异

int x = -1;
int a1 = 5;
int a2 = -5;
int b1 = 4;
int b2 = -4;
cout << x / 2 << "   " << (x >> 1) << endl;   //  0  -1
cout << a1 / 2 << "   " << (a1 >> 1) << endl; //  2   2
cout << a2 / 2 << "   " << (a2 >> 1) << endl; // -2  -3
cout << b1 / 2 << "   " << (b1 >> 1) << endl; //  2   2
cout << b2 / 2 << "   " << (b2 >> 1) << endl; // -2  -2

leetcode405 数字转换成16进制

class Solution {
public:
    string toHex(int num) {
        if (num == 0) return "0";
        // 技巧：将数值与字符联系起来
        string str = "0123456789abcdef";
        // 使用逻辑移位
        unsigned int n = num;
        string res = "";
        // 判断有效位移完
        while (n > 0) {
            // 只取低4位
            int idx = n & 0xf;
            res = str[idx] + res;
            n = n >> 4;
        }
        return res;
    }
};

ip地址转数字及前缀匹配

bool MatchDestIP(int m, string s, const string &dest)
{
    if (s == "0.0.0.0")
        return true;
    int ip = GetIntValue(s);
    int target = GetIntValue(dest);
    // 前缀匹配：前m个字符相同
    return ip >> (32 - m) == target >> (32 - m);
}

// ip地址字符串（s）转int
int GetIntValue(string s)
{
    long long res = 0;
    for (int i = 0; i < 4; ++i) {
        int pos = s.find_first_of(".");
        int num = stoi(s.substr(0, pos));
        res += num << ((3 - i) * 8);
        s = s.substr(pos + 1);
    }
    return res;
}

计算器系列

基本计算器【±( )’’】

class Solution {
public:
    int calculate(string s) {
        stack<int> ops;
        ops.push(1);
        int sign = ops.top();
        int res = 0;
        int i = 0;
        while (i < s.size()) {
            if (s[i] == ' ') {
                i++;
            } else if (s[i] == '+') {
                sign = ops.top();
                i++;
            } else if (s[i] == '-') {
                sign = -ops.top();
                i++;
            } else if (s[i] == '(') {
                ops.push(sign);
                i++;
            } else if (s[i] == ')') {
                ops.pop();
                i++;
            } else {
                long num = 0;
                while (i < s.size() && s[i] >= '0' && s[i] <= '9') {
                    num = num * 10 + s[i] - '0';
                    i++;
                }
                res += sign * num;
            }
        }
        return res;
    }
}；

基本计算器II 【±*/】

class Solution {
public:
    int calculate(string s) {
        vector<long long> numStack;
        char op = '+';
        long long num = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (IsNum(s[i])) {
                num = num * 10 + (s[i] - '0');
            }
            if (IsOP(s[i]) || i == s.size() -1) {
                switch (op) {
                    case '+':
                        numStack.push_back(num);
                        break;
                    case '-':
                        numStack.push_back(-num);
                        break;
                    case '*':
                        numStack.back() *= num;
                        break;
                    case '/':
                        numStack.back() /= num;
                        break;
                }
                op = s[i];
                num = 0;
            }
            
        }
        return accumulate(numStack.begin(), numStack.end(), 0);
    }
    bool IsNum(char ch) {
        return ch >= '0' && ch <= '9';
    }
    bool IsOP(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }
    int GetNum(char ch, int& i, string s) {
        int num = 0;
        for (; i < s.size() && IsNum(s[i]); ++i) {
            num =  num * 10 + (s[i] - '0');
        }
        return num;
    }
};