Project Euler #2 - C

I believe this is probably the most straightforward problem I have encountered on PE thus far. 


Question:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution:

The one thing NOT  to do is to try to solve this recursively. Your stack will get gigantic and your program will probably crash. Luckily, this is an easy one to solve using a simple for loop.

#include <stdio.h>

int main (void)

{

int num1 = 1;

int num2 = 2;

int num3 = 0;

int sum = 2;

while (1)

{

num3 = num1+num2; 

if (num3 > 4000000)

break;

if (!(num3 & 0x1))

{

printf("adding %d\n", num3);

sum += num3;

}

num1 = num2; 

num2 = num3; 

}

printf ("Sum of even fibonacci numbers less than 4,000,000 is %d\n", sum);

return 1; 

}

Like I said, pretty straightforward. The variables num1 and num2 hold the prior two values used to compute num3, the next fibonacci number. Then, break out of the loop when num3 exceeds 4,000,000. The only trick I use here is the way I find out whether num3 is even. Rather than going with the obvious  


num3 % 2


and checking if there is a remainder, deciding whether a number is even or odd can be done much quicker by simply checking whether the LSB (least significant bit) is 1. Since the LSB = 2^0 = 1, this number will ONLY be odd when the LSB == 1. Thus, 


!(num3 & 0x1)


evaluates to 1 when the num3 is even and 0 when num3 is odd. 


Compile, and voila! The answer is before your eyes.