分类位运算下的文章

数字范围按位与

问题描述

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

示例 1:
输入: [5,7]
输出: 4

示例 2:
输入: [0,1]
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bitwise-and-of-numbers-range

思路

当一个数+1时，总会有这么一个规律“某一位后的数字，全部被置为相反数”。举个例子：

010111 + 1 = 011000，则010111 & 011000 = 010000。那么，x & (x+1) 后几位相反数的“与操作”，结果总为0。
所以，当(m,m+1,...n-1,n)进行连续“与操作”时，会按照上述规律被抵消很大一部分，而只剩下n的前缀部分，最后只需将n归位。举个例子：
m = 5(0101), n = 7 (0111)。不停右移，得到n前缀部分为01，最后归位前缀得res=0100=4

来源：李一一
链接：https://blog.csdn.net/smile_watermelon/article/details/47320381

题解

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int count=0;
        for(;m!=n;count++){
            m>>=1;
            n>>=1;
        }
        int ret;
        ret=n<<count;
        return ret;
    }
};

两数相除

问题描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:
输入: dividend = 10, divisor = 3
输出: 3

示例 2:
输入: dividend = 7, divisor = -3
输出: -2

说明:
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/divide-two-integers

思路

首先对特殊情况进行判断，当dividend==0，直接return 0；
在计算的过程中不考虑符号的问题，要对除数和被除数进行取绝对值，因此要先其转化为long long类型，防止溢出
将除数放大count倍，在这个过程中保证lldividend>=lldivisor
被除数依次减去被除数的count倍，右移 count 循环执行减法，直到被除数为0 或者 coun = 0；
判断符号，得到真实的result
如果result超过INT_MAX，则返回INT_MAX，否则返回result。

题解

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend==0) return 0;
        long long lldividend=dividend;
        lldividend=abs(lldividend);
        long long lldivisor=divisor;
        lldivisor=abs(lldivisor);
        long long count=1,result=0;
        while (lldividend>=lldivisor<<1){
            lldivisor<<=1;
            count<<=1;
        }
        while (count>=1&&lldividend>0){
            if(lldividend>=lldivisor){
                lldividend-=lldivisor;
                result+=count;
            }
            lldivisor>>=1;
            count>>=1;
        }
        if(dividend>0&&divisor<0||dividend<0&&divisor>0){
            result=-result;
        }
        if(result>INT_MAX) return INT_MAX;
        else return (int)result;
    }
};

字符串相加

问题描述

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

注意：
num1 和num2 的长度都小于 5100.
num1 和num2 都只包含数字 0-9.
num1 和num2 都不包含任何前导零。
你不能使用任何內建 BigInteger 库，也不能直接将输入的字符串转换为整数形式。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-strings

思路

和两数相加的思路一样

题解

class Solution {
public:
    string addStrings(string num1, string num2) {
        int len1=num1.length();
        int len2=num2.length();
        string ret="";
        int array=0;
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        if(len1<len2){
            for(int i=0;i<len1;i++){
                ret+=to_string(((int)(num1[i]-'0')+(int)(num2[i]-'0')+array)%10);
                array=((int)(num1[i]-'0')+(int)(num2[i]-'0')+array)/10;
            }
            for(int i=len1;i<len2;i++){
                ret+=to_string(((int)(num2[i]-'0')+array)%10);
                array=(array+(int)(num2[i])-'0')/10;
            }
            if(array==1){
                ret+="1";
            }

        }else if(len1>len2){
            for(int i=0;i<len2;i++){
                ret+=to_string(((int)(num1[i]-'0')+(int)(num2[i]-'0')+array)%10);
                array=((int)(num1[i]-'0')+(int)(num2[i]-'0')+array)/10;
            }
            for(int i=len2;i<len1;i++){
                ret+=to_string(((int)(num1[i]-'0')+array)%10);
                array=(array+(int)(num1[i])-'0')/10;
            }
            if(array==1){
                ret+="1";
            }

        } else{
            for(int i=0;i<len2;i++){
                ret+=to_string(((int)(num1[i]-'0')+(int)(num2[i]-'0')+array)%10);
                array=((num1[i]-'0')+(int)(num2[i]-'0')+array)/10;
            }
            if(array==1){
                ret+="1";
            }
        }
        reverse(ret.begin(),ret.end());
        return  ret;
    }
};

看到一个很简单的实现。感觉自己还是很菜很菜的，向大佬学习...

class Solution {
public:
    string addStrings(string num1, string num2) {
        int m = num1.size(), n = num2.size();
        int i = m - 1, j = n - 1, carry = 0;
        string ret = "";
        while (j >= 0 || i >= 0 || carry != 0) {
            if (i >= 0) carry += num1[i--] - '0';
            if (j >= 0) carry += num2[j--] - '0';
            ret += carry % 10 + '0';
            carry /= 10;
        }

        // 翻转字符串
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

作者：autuanliu
链接：https://leetcode-cn.com/problems/two-sum/solution/shu-shi-ji-suan-by-autuanliu/

字符串相乘

问题描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"

说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/multiply-strings

思路

字符串num1的长度是m，字符串num2的长度是n，两个字符串相乘的结果的长度肯定不会超过m+n；因此结果ret的大小申请为m+n，并将每一个字符都初始化为0；

然后根据竖式计算的计算方法，可以得出
ret[i+j+1]=((ret[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0')) %10 +'0';
其中 (ret[i + j + 1] - '0')是之前的进位。
ret[i + j] = ( (ret[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0')/10;
为进位

因为最开始ret申请的大小为n+m，如果num1和num2比较小的话，前边肯定有0空余，因此需要从第一个不为'0'的位置开始截取出返回结果ret。

题解

class Solution {
public:
    string multiply(string num1, string num2) {
        int m = num1.length(), n = num2.length();
        string ret(m + n, '0');  // 所有的进位初始化为 '0'
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                // 进位和乘积的和，当前要加上上一步计算的进位
                int sum = (ret[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0');
                ret[i + j + 1] = (sum % 10) + '0';  // 保存当前计算的数字(低位)
                ret[i + j] += sum / 10;  // 更新当前进位(高位)
            }
        }

        // 从第一个不为 '0' 的字符开始是有效结果或者结果是个位数
        for (int i = 0; i < ret.length(); i++) {
            if (ret[i] != '0')
                return ret.substr(i);  // 从 i 到最后的子字符串
        }
        return "0";
    }
};

分类位运算下的文章