Don't be intimidated by factorials

Factorial is an interesting function, but many people are afraid of it, so let's look at two problems related to Factorial:
1, given an integer N, N factorial N! How many zeros are there at the end? For example: N = 10, N! Is equal to 3, 628, 800 N factorial There are two zeros at the end of.
2. N factorial The position of the lowest 1 in the binary representation of.
Some people are going to think, "well, do I have to figure out N factorial?" The value of? What if it spills? In fact, if we think about it in terms of "which Numbers multiply to get to 10," the problem becomes easier.
First of all, if N factorial K times 10 to the M, and K is not divisible by 10, so N factorial We have M zeroes at the end. Let's think about N factorial. Prime factorization, N factorial. = (2^x) times (3^y) times (5^z)... Since 10 = 2 x 5, M is only related to X and Z. If you multiply each pair of 2 and 5, you can get a 10, so M = min (X, Z). It's not hard to see that X is greater than or equal to Z, because Numbers that are divisible by 2 occur much more frequently than Numbers that are divisible by 5, so let's simplify the formula to M is equal to Z.
According to the above analysis, as long as we calculate the value of Z, we can get N factorial. The number of zeros at the end.
[solution to problem 1]
The most direct way to calculate Z is to calculate I (I =1, 2...). The exponent of 5 in the factorization of N), and then sum:

ret = 0; 
for(i = 1; i <= N; i++) 
{ 
 j = i; 
 while(j % 5 ==0) 
 { 
  ret++;     //Count the number of factors in N factorial that are divisible by 5
  j /= 5; 
 }
}

[solution to problem 1 2]
Formula: Z = [N/5] +[N/5^2] +[N/5^3] +... (don't worry about it being an infinite operation, because there's always a K that makes 5 to the K > N, [N/5^K]=0.
In the formula, [N/5] means that a multiple of 5 in the number not greater than N contributes a 5, [N/5^2] means that a multiple of 5^2 in the number not greater than N contributes another 5,... The code is as follows:

ret = 0; 
while(N) 
{
 ret += N / 5; 
 N /= 5;
}

Problem number two asks for N factorial. The position of the lowest 1 in the binary representation of. Given an integer N, N factorial Where is the lowest bit of 1 in the binary representation? For example: given N = 3, N! Is equal to 6, so N factorial The binary representation of (1 010) is the lowest 1 in the second place.
In order to get a better solution, first of all, we have to transform the problem.
So let's see what happens when you divide a binary number by 2.
Divide a binary number by 2, and the actual process is as follows:
To determine whether the last binary bit is 0, if it is 0, the binary number is shifted to the right by one bit, that is, the quotient value (why); Conversely, if it is 1, the binary number is odd and cannot be divisible by 2 (which is why).
So, this problem is actually equivalent to taking N factorial. The number of prime factors of two plus one. So the answer is equal to N factorial. The number of prime factors of two plus one. Actually N factorial All of them are even, because all of them have a 2 in them, except for 1, because the factorial of 1 is 1, which is an odd number, and the factorial of everything else is even.
[solution 1 of problem 2]
Due to the N! N/2 + N/4 + N/8 + N/16 +... [1].
According to the above analysis, the specific algorithm is obtained, as shown below:

int lowestOnePos(int n) 
{ 
    int ret = 0;     //Statistical n! Is the number of prime factors of two
    while(n) 
    { 
        n >>= 1; 
        ret += n; 
    } 
    return ret+1;
}

[solution to problem 2]
N! The number of prime factors of two is also equal to N minus the number of ones in the binary representation of N. And we can also solve it by using this rule.
For example, suppose N = 11011, then N! N/2 + N/4 + N/8 + N/16 +...

 That is:  1101 + 110 + 11 + 1 
= ( 1000 + 100 + 1 )  
+ ( 100 + 10 )  
+ ( 10 + 1 )  
+ 1 
= ( 1000 + 100+ 10 + 1 ) + ( 100 + 10 + 1 ) + 1 
= 1111 + 111 + 1 
= ( 10000 -1 ) + ( 1000 - 1 ) + ( 10-1 ) + ( 1-1 )  
= 11011-N In binary representation 1 The number of  

summary
Any binary number N of length m can be expressed as N = b[1] + b[2] * 2 + b[3] * 22 +... + b[m] * 2(m-1), where b[I] represents the number (1 or 0) on the ith bit of this binary number. Therefore, if the lowest order b[1] is 1, N is odd; If it's even, and you divide it by 2, that's the same thing as moving the whole binary number one bit lower.
Related topics
Given the integer n, determine if it is a power of 2 > 0&& ((n& (n-1)) ==0).
--------------------------------------------------------------------------------
[1] this rule asks the reader to prove for himself (hint N/k, equal to 1, 2, 3,... , the number of Numbers divisible by k in N).