Java工作利器之常用工具类(二)——数字工具类-大数乘法、加法、减法运算

  1. 云栖社区>
  2. 博客>
  3. 正文

Java工作利器之常用工具类(二)——数字工具类-大数乘法、加法、减法运算

龙轩8023 2015-11-16 10:45:16 浏览479
展开阅读全文

上篇分享了一下数字转汉字的小功能,这里再分享一下大数相乘、相加、相减的功能。其他的不做过多的铺垫了,我先讲一下各个功能的计算原理。


Ⅰ. 乘法运算

为什么先说乘法运算——因为我先做了乘法运算。其实思路也是很多的,但是最终我参考了网络上的一种计算方案,然后做了很多的修改。感觉这个在思路上应该是比较简单的。
简单点说:把数拆分成整数小数分别进行乘法运算,然后将结果放入一个特定长度的数组中,在放入是要计算存放的偏移位置,最后再对这个进行处理(进位、标记等),得到最终的结果。
是不是有点晕。请我详细说一下吧:
  1. 首先还得把数都拆成整数+小数,然后采用的是(x1+x2)(y1+y2)=x1y1+x1y2+x2y1+x2y2。这种方式来计算的,这样来算,都变成了整数的运算了。要简单很多。但是4个结果怎么累加起来计算呢,这就是第二步。
  2. 要申明一个int数组,长度=整数长度和+小数长度和+1(小数点占1位)。通过实验,我们可以看到任意2个整数相乘结果都不会超过这2个数的长度和。
  3. 人为计算乘法的时候就是按右向左一位一位的计算的(低位对齐),所以为了对齐低位,我们将整数和小数全部反转,并且转化为char数组,方便运算。然后进行4次乘法。
  4. 按位进行乘法运算,采用双层for循环完成这个操作。这里最为天才的idea就是——不进位。当然必须得弄清楚整数相乘放在数组的哪些个位置、小数相乘存放的开始位置,以及整数和小数相乘结果存放的开始位置。
  5. 处理结果集合,将>=10的做进位处理。
  6. 这一步也是很有才的想法——对小数点位置进行标记,而不是直接替换成“.”(int数组也不能直接设定(/ □ \))。
  7. 有了第6步的想法,就有了第7步的做法,处理整数部分头部的0和小数部分末尾的0,都是无效数字,这里同样采用标记的方式来处理
  8. 最后将结果集合进行反转输出,遇到小数点标记和无效0标记直接替换和跳过。

这就是基本的思路了。后面又再次基础上加上了负数的判断、数字格式的判断等,自己看注释就可以明白了。

代码如下:

    //标记为小数点
    private static final int DOT=-99;
    //标记为无效数字
    private static final int INVALID=-100;

    /**
     * 大数乘法
     * 
     * @param a    第一个数
     * @param b    第二个数
     * @return    最终结果
     */
    public static String multiply(String a, String b){
        //检查数字格式
        checkNum(a);
        checkNum(b);

        //标记最终结果是否为负值
        boolean minus=false;

        //判断是否有带着-号
        if(a.startsWith("-") || b.startsWith("-")){
            //判断是否全带着-号
            if(a.startsWith("-") && b.startsWith("-")){
            }else{
                //只有1个带着-号,则结果为负值
                minus=true;
            }
            if(a.startsWith("-")){
                a = a.substring(1);
            }
            if(b.startsWith("-")){
                b = b.substring(1);
            }
        }

        //获取a,b的整数和小数部分
        String a_int = getInt(a);
        String a_fraction = getFraction(a);
        String b_int = getInt(b);
        String b_fraction = getFraction(b);

        //计算小数部分的总长度
        int len_fraction = a_fraction.length() +b_fraction.length() ;

        //a,b两个数乘积的最大位数不会超过总位数之和+小数点(1位)
        int len = len_fraction +a_int.length()+b_int.length()+1;

        //创建结果数组
        int[] result = new int[len];//默认全为0

        //为了方便计算,去掉小数点(最后在结果中加上小数点)
        //并将高低位对调(反转是为了低位对齐),最终转化为char数组
        char[] s_a_int = reverseStr(a_int);
        char[] s_a_fraction = reverseStr(a_fraction);
        char[] s_b_int = reverseStr(b_int);
        char[] s_b_fraction = reverseStr(b_fraction);

        //将a、b都拆分成整数+小数,然后
        //采用(x1+x2)(y1+y2)=x1y1+x1y2+x2y1+x2y2公式,分别计算乘积
        multiply(s_a_int, s_b_int, len_fraction, result);
        multiply(s_a_int, s_b_fraction, (len_fraction-s_b_fraction.length), result);
        multiply(s_b_int, s_a_fraction, (len_fraction-s_a_fraction.length), result);
        multiply(s_a_fraction, s_b_fraction, 0, result);

        // 处理结果集合,如果是大于10的就向前一位进位,本身进行除10取余
        accumulateResultArrays(result);

        //标记小数点位置
        markDot(len_fraction, result);

        //切掉无用的0
        cutUnusedZero(len_fraction, result);

        //然后将数据反转
        return (minus?"-":"") + reverseResult(result);
    }

    /**
     * 反转字符串,并转化为数组
     * 
     * @param s        原字符串
     * @return
     */
    private static char[] reverseStr(String s) {
        return new StringBuffer(s).reverse().toString().toCharArray();
    }

    /**
     * 计算2个数的每一位的乘积,放入到对应的结果数组中(未进位)
     * 
     * @param a    第一个数
     * @param b    第二个数
     * @param start    开始放入的偏移位置
     * @param result    结果数组
     */
    private static void multiply(char[] a, char[] b, int start , int[] result){
        // 计算结果集合
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b.length; j++) {
                result[i + j + start] += (int) (a[i] - '0') * (int) (b[j] - '0');
            }
        }
    }

    /**
     * 累加每一位,超过10则然后进位
     * 
     * @param result    结果数组
     */
    private static void accumulateResultArrays(int[] result) {
        for (int i = 0; i < result.length; i++) {
            if (result[i] >= 10) {
                result[i + 1] += result[i] / 10;
                result[i] %= 10;
            }
        }
    }

    /**
     * 标记小数点位置
     * 
     * @param len_fraction    小数长度
     * @param result    结果数组(反转的)
     */
    private static void markDot(int len_fraction, int[] result) {
        if(len_fraction>0){
            //标记小数点位置
            for (int i = result.length-1 ; i > len_fraction; i--) {
                result[i] = result[i-1];
            }
            result[len_fraction]=DOT;//标记小数点位置
        }
    }

    /**
     * 去掉不必要的0(包括整数最前面的和小数最后面的0)
     * 
     * @param len_fraction    小数长度
     * @param result        结果数组
     */
    private static void cutUnusedZero(int len_fraction, int[] result) {
        //去掉小数部分不必要的0
        boolean flag_0_fraction = true;//标记一直是0
        for (int i =0; i< len_fraction; i++) {
            if(flag_0_fraction && result[i]==0){
                result[i]=INVALID;//为0时标记为无效
            }else{
                flag_0_fraction=false;
                break;
            }
        }

        //去掉整数部分的0
        boolean flag_0_int=true;
        for (int i =result.length-1; i > len_fraction || (len_fraction==0 && i==0); i--) {
            if(flag_0_int && result[i]==0){
                result[i]=INVALID;//为0时标记为无效
            }else{
                flag_0_int=false;//遇到不为0时,停止。
                break;
            }
        }
        if(flag_0_int){//整数部分全为0
            result[len_fraction+1]=0;
            if(flag_0_fraction){//同时,小数部分也全为0
                result[len_fraction]=INVALID;//不需要小数点了,所以置为无效
            }
        }else{//整数部分不为0
            if(flag_0_fraction && len_fraction>0){//小数部分全为0
                result[len_fraction]=INVALID;//不需要小数点了,所以置为无效
            }
        }
    }

    /**
     * 反转结果,替换小数点,跳过无效的0
     * 
     * @param result        结果数组
     * @return
     */
    private static String reverseResult(int[] result) {
        //反转
        StringBuffer sb = new StringBuffer();
        for (int i = result.length - 1; i >= 0; i--) {
            if(result[i]>INVALID){
                sb.append(result[i]==DOT ? "." : result[i]);
            }
        }
        return sb.toString();
    }

我们继续说第二个。

Ⅱ. 加法运算

有了上面的思路做铺垫,下面的加法和减法基本上都可以秒懂了。负数及数字格式的判断就直接略过了。直接说最基本的思路。
  1. 前两步同乘法运算。拆分整数+小数,声明一个int数组存放结果。长度为a b整数最大的长度+1+小数最大长度+1(小数点位)。因为加法最多位数比最大长度大1,所以有一个+1。
  2. 结果是整数和+小数和,整数要低位对齐,所以要反转,小数则不用反转。
  3. 用一个for循环来计算2个整数或者小数的和,同样不进位。
  4. 剩下的同乘法4-8步。

代码放在最后看吧。接着来说说减法。

Ⅲ. 减法运算

其实减法跟加法在代码上看,更类似。详细说一下:(忽略负数及数字格式的判断)
  1. 前三步同加法运算。拆分整数+小数,声明一个int数组存放结果。长度为a b整数最大的长度+小数最大长度+1(小数点位)。结果是整数差+小数差。
  2. 还是用一个for循环计算2个数的差,这里不是不进位了,而是不借位
  3. 处理结果结合跟加法和乘法不一样,加法和乘法都是进位,这里是借位,所以处理不太一样。
  4. 剩下同加法。

具体代码如下:
    /**
     * 大数加法
     * 
     * @param a    第一个数
     * @param b    第二个数
     * @return    最终结果
     */
    public static String add(String a, String b){
        //检查数字格式
        checkNum(a);
        checkNum(b);

        //标记最终结果是否为负值
        boolean minus=false;

        //判断是否有带着-号
        if(a.startsWith("-") || b.startsWith("-")){
            //判断是否全带着-号
            if(a.startsWith("-") && b.startsWith("-")){
                //2个都带着-号,结果肯定为负值
                minus=true;
                if(a.startsWith("-")){
                    a = a.substring(1);
                }
                if(b.startsWith("-")){
                    b = b.substring(1);
                }
            }else{
                //如果只有一个是负值,则调用减法来完成操作
                if(a.startsWith("-")){//a是负数
                    a = a.substring(1);
                    return subduct(b, a);
                }else{
                    b = b.substring(1);
                    return subduct(a, b);
                }

            }
        }

        //获取a,b的整数和小数部分
        String a_int = getInt(a);
        String a_fraction = getFraction(a);
        String b_int = getInt(b);
        String b_fraction = getFraction(b);

        //计算小数部分最大长度
        int len_fraction = Math.max(a_fraction.length(), b_fraction.length());

        //计算整数部分最大长度
        int len_int = Math.max(a_int.length(), b_int.length())+1;

        //a,b两个数整数最大长度和小数最大长度之和+小数点(1位)
        int len = len_fraction + len_int+1;

        //创建结果数组
        int[] result = new int[len];//默认全为0

        //为了方便计算,去掉小数点(最后在结果中加上小数点)
        //将【整数部分】高低位对调(反转是为了低位对齐),最终转化为char数组
        //小数部分不用调整
        char[] s_a_int = reverseStr(a_int);
        char[] s_b_int = reverseStr(b_int);
        char[] s_a_fraction = a_fraction.toCharArray();
        char[] s_b_fraction = b_fraction.toCharArray();

        //采用整数+整数,小数+小数的方式运算
        add(s_a_int, s_b_int, len_fraction, result);
        add(s_a_fraction, s_b_fraction, 1-len_fraction, result);

        // 处理结果集合,如果是大于10的就向前一位进位,本身进行除10取余
        accumulateResultArrays(result);

        //标记小数点位置
        markDot(len_fraction, result);

        //切掉无用的0
        cutUnusedZero(len_fraction, result);

        //然后将数据反转
        return (minus ? "-" : "")+reverseResult(result);
    }

    /**
     * 计算2个数的每一位的和,放入到对应的结果数组中(未进位)
     * 
     * @param a    第一个数
     * @param b    第二个数
     * @param start    开始放入的偏移位置
     * @param result    结果数组
     */
    private static void add(char[] a, char[] b, int start , int[] result){
        char[] c=null;
        //保证a是位数多的,如果b长度大于a,则交换a,b
        if(b.length>a.length){
            c=a;
            a=b;
            b=c;
        }
        // 计算结果集合,a的位数>=b的位数
        int i = 0, j=0;
        for (; i < a.length && j< b.length; i++,j++) {
            result[Math.abs(i + start)] += (int) (a[i] - '0') + (int) (b[j] - '0');
        }
        //如果a没有处理完毕,直接把a剩下的值赋值给结果数组即可
        for (; i < a.length; i++) {
            result[Math.abs(i + start)] += (int) (a[i] - '0');
        }
        if(c!=null){//如果交换过,则再交换回来
            c=a;
            a=b;
            b=c;
        }
        c=null;
    }

    /**
     * 大数减法
     * 
     * @param a    第一个数
     * @param b    第二个数
     * @return    最终结果
     */
    public static String subduct(String a, String b){
        //检查数字格式
        checkNum(a);
        checkNum(b);

        //标记最终结果是否为负值
        boolean minus=false;

        //判断是否有带着-号
        if(a.startsWith("-") || b.startsWith("-")){
            //判断是否全带着-号
            if(a.startsWith("-") && b.startsWith("-")){
                //2个都带着-号
                if(a.startsWith("-")){
                    a = a.substring(1);
                }
                if(b.startsWith("-")){
                    b = b.substring(1);
                }
                return subduct(b, a);
            }else{
                //如果只有一个是负值,则调用加法来完成操作
                if(a.startsWith("-")){//a是负值,b是非负值
                    return add(a, "-"+b);//2个负值的加法运算
                }else{//b是负值
                    b = b.substring(1);
                    return add(a, b);//2个正值的加法运算
                }
            }
        }

        //获取a,b的整数和小数部分
        String a_int = getInt(a);
        String a_fraction = getFraction(a);
        String b_int = getInt(b);
        String b_fraction = getFraction(b);

        boolean isSame = false;
        //判断大小
        if(b_int.length()>a_int.length()){
            //如果b>a
            return "-"+subduct(b, a);
        }else if(b_int.length()==a_int.length()){
            char[] s_a = a_int.toCharArray();
            char[] s_b = b_int.toCharArray();
            for (int i = 0; i < s_a.length; i++) {
                if(s_b[i]>s_a[i]){
                    minus=true;
                    isSame=false;
                    break;
                }else if(s_b[i]<s_a[i]){
                    isSame=false;
                    break;
                }else{
                    isSame = true;
                }
            }
            if(isSame){//整数部分全部相同,对比小数部分
                s_a = a_fraction.toCharArray();
                s_b = b_fraction.toCharArray();
                for (int i = 0; i < Math.min(s_a.length, s_b.length); i++) {
                    if(s_b[i]>s_a[i]){
                        minus=true;
                        isSame=false;
                        break;
                    }else if(s_b[i]<s_a[i]){
                        isSame=false;
                        break;
                    }else{
                        isSame = true;
                    }
                }
                if(isSame){//前部分全相同
                    if(s_b.length>s_a.length){//前部分全相同,b小数位数多,则 b>a
                        return "-"+subduct(b, a);
                    }else if(s_b.length == s_a.length){
                        return "0";
                    }
                }else if(minus){//如果b>a
                    return "-"+subduct(b, a);
                }
            }
        }


        //计算小数部分最大长度
        int len_fraction = Math.max(a_fraction.length(), b_fraction.length());

        //计算整数部分最大长度
        int len_int = Math.max(a_int.length(), b_int.length());

        //a,b两个数整数最大长度和小数最大长度之和+小数点(1位)
        int len = len_fraction + len_int+1;

        //创建结果数组
        int[] result = new int[len];//默认全为0

        //为了方便计算,去掉小数点(最后在结果中加上小数点)
        //将【整数部分】高低位对调(反转是为了低位对齐),最终转化为char数组
        //小数部分不用调整
        char[] s_a_int = reverseStr(a_int);
        char[] s_b_int = reverseStr(b_int);
        char[] s_a_fraction = a_fraction.toCharArray();
        char[] s_b_fraction = b_fraction.toCharArray();

        //采用整数+整数,小数+小数的方式运算
        subduct(s_a_int, s_b_int, len_fraction, result);
        subduct(s_a_fraction, s_b_fraction, 1-len_fraction, result);

        // 处理结果集合,如果是大于10的就向前一位进位,本身进行除10取余
        subductResultArrays(result);

        //标记小数点位置
        markDot(len_fraction, result);

        //切掉无用的0
        cutUnusedZero(len_fraction, result);

        //然后将数据反转
        return (minus ? "-" : "")+reverseResult(result);
    }

    /**
     * 计算2个数的每一位的差,放入到对应的结果数组中(未进位)
     * 
     * @param a    第一个数
     * @param b    第二个数
     * @param start    开始放入的偏移位置
     * @param result    结果数组
     */
    private static void subduct(char[] a, char[] b, int start , int[] result){
        // 计算结果集合,a的位数>=b的位数
        int i = 0, j=0;
        for (; i < a.length && j< b.length; i++,j++) {
            result[Math.abs(i + start)] +=((int) (a[i] - '0') - (int) (b[j] - '0'));
        }
        //如果a没有处理完毕,直接把a剩下的值赋值给结果数组即可
        for (; i < a.length; i++) {
            result[Math.abs(i + start)] +=((int) (a[i] - '0'));
        }
        //如果a没有处理完毕,直接把a剩下的值赋值给结果数组即可
        for (; i < b.length; i++) {
            result[Math.abs(i + start)] +=-((int) (b[i] - '0'));
        }
    }

    /**
     * 检查每一位,小于0(不含标记的小数点未和无效的0)则然后向高位借位。
     * 
     * @param result    结果数组
     */
    private static void subductResultArrays(int[] result) {
        for (int i = 0; i < result.length-1; i++) {
            if (result[i] < 0 && result[i]>DOT) {
                result[i + 1]--;
                result[i] += 10;
            }
        }
    }
写个main方法测试一下吧:
    public static void main(String[] args) {
        String a = "9213213210.4508";
        String b = "12323245512512100.4500081";
        String r = multiply(a, b);
        System.out.println(a+"*"+b+"="+r);
        String r1 = add(a, b);
        System.out.println(a+"+"+b+"="+r1);
        String r2 = subduct(a, b);
        System.out.println(a+"-"+b+"="+r2);
    }

测试结果如下:

网友评论

登录后评论
0/500
评论
龙轩8023
+ 关注