分类 位运算 下的文章

数字范围按位与

问题描述

给定范围 [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";
    }
};