每日算法之a+b和尾部零的算法

落日映苍穹つ 2022-05-28 13:23 185阅读 0赞

# 一、a+b问题 #

a=1，b=2，不使用加减乘除，来实现a+b的效果。（可以使用位操作符）

算法思路：  
①1+1=0,0+0=0，1+0=1，可以看出和异或产生的效果类似。  
②上面的加法虽然可以用异或来实现，但是还有1+1的进位问题，可以用另一种方式解决，比方说：1+1=0，可以通过1&1，为0，同时，将其左移一位即可获取进位。  
③接着就是将①和②的结果加起来即可。

public int aplusb(int a, int b) {
            // 核心思想通过递归实现
            if(b == 0)
                return a;
            int sum = a ^ b;
            int carry = (a & b)<<1;
            return aplusb(sum,carry);
     }

# 二、尾部的零 #

设计一个算法，计算出n阶乘中尾部零的个数

我的思路是（不对）：①先算出n阶乘，接着对某个数计算尾部0的个数。

public long trailingZeros(long n) {
            long s = factorial(n) ;
            long x = 10 ;
            long count = 0 ;
            try {
                while(s%x==0){
                    count++ ;
                    x = x * 10 ;
                }
            }catch (Exception e){
                e.printStackTrace();
            }
            return count;
        }
    
        public long factorial(long n){
            if(n==0){
                return 1 ;
            }
            return n * factorial( n -1 ) ;
        }

存在的问题：比较小的数据还能正常运行，一旦数据大的话，求阶乘就会出问题。

其实这个题目真正做法不应该是这样,核心在于什么样的数相乘会产生尾部为0，重点在5，只要是个偶数乘以5都可以产生尾部为0的数，而且如果产生了第一个0，后面不管乘以什么数这个0都不会消失，后续只会叠加，所以说只要遍历n、n/5….即可。

public long trailingZeros(long n) {
           long num = 0 ;
           while(n>0){
               num += n/5 ;
               n=n/5 ;
           }
           return num ;
        }