Simplest way to calculate amount of even numbers in given range

What is the simplest way to calculate the amount of even numbers in a range of unsigned integers?

An example: if range is [0...4] then the answer is 3 (0,2,4)

I'm having hard time to think of any s开发者_JAVA百科imple way. The only solution I came up involved couple of if-statements. Is there a simple line of code that can do this without if-statements or ternary operators?

---

int even = (0 == begin % 2) ? (end - begin) / 2 + 1 : (end - begin + 1) / 2;

Which can be converted into:

int even = (end - begin + (begin % 2)) / 2 + (1 - (begin % 2));

EDIT: This can further simplified into:

int even = (end - begin + 2 - (begin % 2)) / 2;

EDIT2: Because of the in my opinion somewhat incorrect definition of integer division in C (integer division truncates downwards for positive numbers and upwards for negative numbers) this formula won't work when begin is a negative odd number.

EDIT3: User 'iPhone beginner' correctly observes that if begin % 2 is replaced with begin & 1 this will work correctly for all ranges.

---

Hint 1: The modulo operator will return the remainder of the current number
Hint 2: You don't need a for loop
Hint 3: A range is continuous
Hint 4: The number of even numbers in a continuous range are half even (sometimes half + 1, sometimes half - 1)
Hint 5: Building on Hint1: Consider also what (being + end + 1) % 2 gives
Hint 6: Most or all of the answers in this thread are wrong
Hint 7: Make sure you try your solution with negative number ranges
Hint 8: Make sure you try your solution with ranges spanning both negative and positive numbers

---

Answer is to use binary AND.

so a number is represented in memory in 0 and 1. lets say 4 and 5.

4 = 0000 0100

5 = 0000 0101

and every even number has a zero in the end and every odd number has 1 in the end;

in c '1' means true and '0' means false.

so: lets code;

function isEven(int num){
     return ((num & 0x01) == 0) ? 1 : 0;
}

Here 0x01 means 0000 0001. so we are anding 0x01 with the given number.

imagine no is 5

5    |0000 0101 

0x01 |0000 0001

---------------

      0000 0001

so answer will be '1'.

imagine no is 4

4    |0000 0100 

0x01 |0000 0001

---------------

      0000 0000

so answer will be '0'.

now,

return ((num & 0x01) == 0) ? 1 : 0;

it is expanded in :

if((num & 0x01) == 0){// means  the number is even
      return 1;
}else{//means no is odd
      return 0;
}

So this is all.

End is binary operatiors are very important in compititive programming world.

happy coding.

first answer here.

EDIT 1:

Total no of evens are

totalEvens = ((end - start) / 2 + ((((end - start) & 0x01 ) == 0) ? 0 : 1 ));

here (end - start)/2 gives the half of total numbers.

this works if one is even and one is odd.

but,

((((end - start) & 0x01 ) == 0) ? 0 : 1 )

can just replaced by (!isEven(end-start))

So, if the total number is even then dont add 1 else add 1.

this completely works.

---

int start, stop;
start = 0;
stop = 9;
printf("%d",(stop-start)/2+((!(start%2) || !(stop%2)) ? 1 : 0));

Where start and stop can hold any value. No need to iterate to to determine this number.

---

The count of even numbers between 0 and n is [n/2] + 1. Therefore the count of even numbers between (n + 1) and m is ([m/2] + 1) - ([n/2] + 1) = [m/2] - [n/2].

For count of even numbers between m and n the answer therefore would be [m/2] - [(n - 1)/2].

The [x] is taken to the direction of -\infty. Beware that the usual C integer division is not doing right in our case: a/2 is rounded towards zero, not -\infty, so the result will be not [a/2] for teh case of negative a.

This should be the simplest calculation; works for negative numbers, too. (Needs however that m >= n.) Doesn't contain ifs and ?:s.

If you don't consider negative numbers, you can use just m/2 - (n+1)/2 + 1, otherwise floor(m/2.0) - floor((n-1)/2.0)

---

This'll do the trick, even for ranges with negative numbers.

int even = (last - first + 2 - Math.abs(first % 2) - Math.abs(last % 2)) / 2;

Tested with the following code:

public static void main(String[] args) {
    int[][] numbers = {{0, 4}, {0, 5}, {1, 4}, {1, 5}, {4, 4}, {5, 5},
                       {-1, 0}, {-5, 0}, {-4, 5}, {-5, 5}, {-4, -4}, {-5, -5}};

    for (int[] pair : numbers) {
        int first = pair[0];
        int last = pair[1];
        int even = (last - first + 2 - Math.abs(first % 2) - Math.abs(last % 2)) / 2;
        System.out.println("[" + first + ", " + last + "] -> " + even);
    }
}

Output:

[0, 4] -> 3
[0, 5] -> 3
[1, 4] -> 2
[1, 5] -> 2
[4, 4] -> 1
[5, 5] -> 0
[-1, 0] -> 1
[-5, 0] -> 3
[-4, 5] -> 5
[-5, 5] -> 5
[-4, -4] -> 1
[-5, -5] -> 0

---

I'm a bit surprised that iteration was tried to solve this. The minimum number of even numbers possible in a range is equal to half of the length of the array of numbers, or, rangeEnd - rangeStart.
Add 1 if the first or last number is even.

So the method is: (using javascript)

function evenInRange(rangeStart, rangeEnd)
{
  return
    Math.floor(rangeEnd - rangeStart) + 
    ((rangeStart % 2 == 0) || (rangeEnd % 2 == 0) ? 1 : 0)
}


Tests:
0 1 2 3 4 5 6 7 8
8 - 0 = 8
8 / 2 = 4
4 + 1 = 5
Even numbers in range:
0 2 4 6 8

11 12 13 14 15 16 17 18 19 20
20 - 11 = 9
9 / 2 = 4
4 + 1 = 5
Even numbers in range
12 14 16 18 20

1 2 3
3 - 1 = 2
2 / 2 = 1
1 + 0 = 1
Even numbers in range
2

2 3 4 5
5 - 2 = 3
3 / 2 = 1
1 + 1 = 2
Even numbers in range
2 4

2 3 4 5 6
6 - 2 = 4
4 / 2 = 2
2 + 1 = 3
Even numbers in range
2 4 6

---

The range is always [2a+b, 2c+d] with b,d = {0,1}. Make a table:

b d | #even
0 0 | c-a+1
0 1 | c-a+1
1 0 | c-a
1 1 | c-a+1

Now a = min/2, b = min % 2, c = max/2 and d = max % 2.

So int nEven = max/2 - min/2 + 1 - (min%2).

---

I'd say

(max - min + 1 + (min % 2)) / 2

Edit: Erm okay for some reason I thought that (min % 2) returns 1 for even numbers.... :). The correct version is

(max - min + 1 + 1 - (min % 2)) / 2

or rather

(max - min + 2 - (min % 2)) / 2

---

The first even number in the range is: (begin + 1) & ~1 (round begin up to even number).

The last even number in the range is: end & ~1 (round end down to even number).

The total number of even numbers in the range is therefore: (end & ~1) - ((begin + 1) & ~1) + 1.

int num_evens = (end & ~1) - ((begin + 1) & ~1) + 1;

---

Let's look at this logically ...

We have four cases ...

odd -> odd     eg.  1 -> 3  answer: 1
odd -> even    eg.  1 -> 4  answer: 2
even -> odd    eg.  0 -> 3  answer: 2
even -> even   eg.  0 -> 4  answer: 3

The first three cases can be handled simply as ...

(1 + last - first) / 2

The fourth case does not fall quite so nicely into this, but we can fudge around a little bit for it quite easily ...

answer = (1 + last - first) / 2;
if (both first and last are even)
    answer++;

Hope this helps.

---

Oh well, why not:

#include <cassert>

int ecount( int begin, int end ) {
    assert( begin <= end );
    int size = (end - begin) + 1;
    if ( size % 2 == 0  || begin % 2 == 1 ) {
        return size / 2;
    }
    else {
        return size / 2 + 1;
    }
}

int main() {
    assert( ecount( 1, 5 ) == 2 );
    assert( ecount( 1, 6 ) == 3 );
    assert( ecount( 2, 6 ) == 3 );
    assert( ecount( 1, 1 ) == 0 );
    assert( ecount( 2, 2 ) == 1 );
}

---

The answer:

(max - min + 2 - (max % 2) - (min % 2)) / 2

A short explanation:

• even..even yields (length + 1) / 2
• even..odd yields length / 2
• odd..even yields length / 2

• odd..odd yields (length - 1) / 2

• length = max - min + 1

Therefore, the answer is (length - 1) / 2 plus 1/2 for even min plus 1/2 for even max. Note that (length - 1) / 2 == (max - min) / 2, and the "bonuses" are (1 - (min % 2)) / 2 and (1 - (max % 2)) / 2. Sum this all up and simplify to obtain the answer above.

---

In terms of start and length:

(length >> 1) + (1 & ~start & length)

half the length plus 1 if start is even and length is odd.

In terms of start and end:

((end - start + 1) >> 1) + (1 & ~start & ~end)

half the length plus 1 if start is even and end is even.

---

This does not require any conditions at all:

evencount = floor((max - min)/2) + 1

---

Pseudo code (i'm no C coder):

count = 0;
foreach(i in range){
    if(i % 2 == 0){
      count++;
    }
}