不要被阶乘吓倒

来源：编程之美 2.2

题目：1.给定一个整数N，求N!末尾有多少个0

2.求N！的二进制表示中最低位1的位置

对于第一个问题，书中也给出了两种解答方法，第二种是最好的，想明白为什么这样做后就很简单了。

/**
 * 1.给定一个整数N，求N!末尾有多少个0 2.求N！的二进制表示中最低位1的位置
 */
public class Factorial2_2 {
	
	public static void main(String[] args){
		int num=100;
		System.out.println(zeroCount1(num));
		System.out.println(zeroCount2(num));
	}

	// 解法一，有多少个0，其实可以转化成求因式分解后5的指数是多少
	public static int zeroCount1(int n) {
		int res = 0;
		int i, j;
		for (i = 1; i <= n; i++) {
			j = i;
			while (j % 5 == 0) {
				res++;
				j /= 5;
			}
		}
		return res;
	}
	
	//解法二，连续的k个数有且仅有1个数可以被k整除，如2，3，4，5，6肯定只有一个5可以被5带除
	//如n=100时，可以把100，99，98....1五个五个分成一组，能分多少组就说明有多个数能被5整除
	//接着计算有多少个数能被25，125...整除
	//这就是书中给出的公式来源：Z = [N/5] +[N/5^2] +[N/5^3] + …
	//（不用担心这会是一个无穷的运算，因为总存在一个K，使得5^K > N，[N/5^K]=0。）
	public static int zeroCount2(int n) {
		int res = 0;
		while(n>0){
			res+=n/5;
			n/=5;
		}
		return res;
	}

}

 

第二个问题的解法和第一个问题差不多，只不过是求2的质因数个数

//第二个问题实际上可以转化成求n!中含有质因数2的个数，最后加上1即可，解法和求5的是一致的
	public static int lowestOne1(int n){
		int res=0;
		while(n>0){			
			n>>=1;
			res+=n;			
		}
		return res+1;
	}
	//N!含有质因数2的个数，还等于N减去N的二进制表示中1的数目
	//这个思路比较难想~~
	public static int lowestOne2(int n){
		return n-count3(n)+1;
	}
	//整数二进制表示中1的个数，只需循环1的个数次即可
	//每次循环都把最低位的1去掉了
	public static int count3(int  a){
		int count=0;
		while(a>0){			
			count++;
			a&=(a-1);//通过&运算把最低位的1变成0
		}
		return count;
	}

 

扩展问题：给定整数n，判断它是否为2的方幂

这个问题比较简单，只要是2的方幂的数，二进制表示都只有一个1，前面讲过n&(n-1)会把最低位的1变成0，因此只需要判断n&(n-1)是否为0即可：

	//判断整数n是否为2的方幂
	public static boolean isMiTwo(int n){
		if(n>0&&((n&(n-1))==0))return true;
		return false;
	}