n&(n-1)的用法
import java.util.Scanner;
import javax.swing.text.StyledEditorKit.BoldAction;
/**
*
* @author zhaokun
*
*/
public class count1 {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while (cin.hasNext()) {
int n = cin.nextInt();
//int count = countBinary1(n);
//System.out.println(count);
//isPower2(n);
countCalc(n,5);
}
}
//使用n&(n-1)求某个数二进制的个数
public static Integer countBinary1(int n){
int count = 0;
while(n!=0){
n&=(n-1);
count++;
}
return count;
}
//使用n&(n-1)用来判断某数是否是2的次幂
public static void isPower2(int n){
if((n>0) && ((n&(n-1)))==0){
System.out.println("n是2的次幂");
}else{
System.out.println("n不是2的次幂");
}
}
//计算N!中质因数2的个数
/* 容易得出N!质因数2的个数 = [N / 2] + [N / 2^2] + [N / 2^3] + ....
下面通过一个简单的例子来推导一下过程:N = 10101(二进制表示)
现在我们跟踪最高位的1,不考虑其他位假定为0,
则在
[N / 2] 01000
[N / 4] 00100
[N / 8] 00010
[N / 8] 00001
则所有相加等于01111 = 10000 - 1
由此推及其他位可得:(10101)!的质因数2的个数为10000 - 1 + 00100 - 1 + 00001 - 1 = 10101 - 3(二进制表示中1的个数)
推及一般N!的质因数2的个数为N - (N二进制表示中1的个数)
*/
//求n中质因数的个数
public static void countCalc(int n ,int x){//n 为n!的n x 为要求的质因数
long cnt=0;
for(long i=x;i<=n;i=i*x){
cnt += n/i;
}
System.out.println(cnt);
}
}