Question Lead: A friend wrote:
On the 21st, I was arranged at 4:30 interview, and a technician gave me an interview. After asked some simple questions, he gave me a programming topic, the topic is like this: (Due to the specific interview I am more cumbersome, I extract my core idea to break down ...)
1) Write a function calculation When the parameter is N (N large), the value of 1-2 3-4 5-6 7 ... n is, my heart is clear! I didn't expect it as simple, I am a little bit of a bit of a bit! So I quickly gave my solution: long fn (long n) {long temp = 0; INT I, FLAG = 1; if (n <= 0) {Printf ("Error: n Must> 0); EXIT 1);} for (i = 1; i <= n; i ) {temp = Temp Flag * i; flag = (- 1) * flag;} return temp;}
Get it! When I looked at the interviewer with the eyes of expectation, he smiled and said to me, the execution result is definitely no problem! However, when N is big, this program is very efficient. In the development of embedded systems, the operational efficiency of the program is important, which can make CPUs to execute a directive, and he let me see this program. What can be modified, optimize the program! After listening to these words, my mood became a bit heavy, I didn't expect his requirements very strict, and after I have strictly analyze the procedure, I have given improved programs!
Long fn (long n) {long Temp = 0; INT J = 1, I = 1, FLAG = 1; if (n <= 0) {Printf ("Error: N Must> 0); EXIT (1);} While (j <= n) {TEMP = Temp i; i = -i; i> 0? i : I -; J ;} Return Temp;} Although I dare not guarantee that this algorithm is optimal, but Compared to the previous program, I change all statements involved in multiplication to implement the addition instruction, which has only reached the requirements of the topic and the calculation time is shortened! And the cost is just an integer variable! But I am now The confidence has been hit, I will interview the people of the people, he still smiled and said to me: "Good, this program is really effective in efficiency! "I am in my heart! But he will then say that this program still can't reach his request, I want to give better programs! Heaven! There is also an optimization! I really collapsed, I thought for a while, I will Ask him to give his program! Then he is very refreshing to give his program! Long fn (long n) {if (n <= 0) {printf ("error: n must> 0); exit (1) } IF (0 == n% 2) Return (N / 2) * (- 1); else return (N / 2) * (- 1) n;} Funny, I stunned, I didn't expect him to be this Meaning, don't you write this simple code, but why didn't I think it is in that? He said there is no mistake. When the N is very large, the difference between the three procedures run is simply different! When I just wanted to say something, he first opened: "Don't think that the CPU calculation speed will push all the questions to it, and the programmer should optimize the code and optimize the code. We can do it yourself. Never let the CPU do, because the CPU is serving our users, not for our programmer! "How brusal language, I don't want to say anymore.
-------------------------------------------------- ----------------------------- Taking the question, I think the program is still the first. Optimization should only be necessary when necessary Do. There is no optimized solution in the topic (actually not the best in the end). It is not necessary to write so good.
The most important thing is readable and can be understood. Instead of the machine.
Light said that it is a fake style, practice one.
#include
INT FN_READABLE (INT N) {if (n <0) {return 0;} int sum = 0;
// odd number plus FOR (int i = 1; i INT FN_BEST (INT N); RETURN (N & 0x1)? (N >> 1) 1: - (n >> 1);} int main () {Printf ("SUM IS% D,% DN ", FN_Readable (100001), FN_BEST (100001)); Printf (" SUM IS% D,% DN ", Fn_Readable (100002), Fn_Best (100002)); Printf (" SUM IS% D,% DN ", fn_readable (100003), fn_best (100003)); Return 0;} I am not measured, fn_beest is how fast. However, its assembly code is like this. Only four instructions are only more instructions. It should be more fast. Test Al, 1JE SHORT $ 1,1INC EAX $ 148: Sar Eax, 1NEG EAX Simply talk about the idea (1-2) (3-4) ...- 1 ^ (n) * n This formula will everyone will be an even number, fn = -1 * n / 2n is odd, fn = - 1 * (n-1) / 2 n This is the solution of the interviewer. Didn't finish it. N is an even number when setting x = N / 2, so the fn = -1 * x = -xn is odd when setting x = (n-1) / 2, so n = 2x 1Fn = -1 * (2X 1 ) - 1) / 2 (2X 1) = x 1 N / 2 and (N-1) / 2 and N >> 2 are the simplest method of the equivalent to judge the minimum bit is one, that is, N & 0x1, the result is IF (N & 0x1) odd number ( N >> 2) 1ELSE even - (n >> 2)
