Fastest way to find if N numbers are even or odd

Question

I want to find if 'N' numbers are even or odd in the fastest way possible.

Here's the following code which produces the desired output, but I do not know how efficient it is.

int main() {
int N,x;
scanf("%d",&N);
while(N--){
   scanf("%d",&x);
    x&1 ? cout << "No" << endl : cout << "Yes" << endl;
}
return 0;

Can this code be improved in any way to get faster results?

Answer 1

Given that 99.9% of time is spent in scanf, cout and waiting for user input then there isn't much you can do about performance (but see notes).

What it may be improved is readability of your code. First of all your're mixing C style I/O (scanf) with C++ I/O (std::cout). Let's move to C++ std::cin.

Do not ever add using namespace std; (Why is “using namespace std” considered bad practice?)

In C++ there is no need to declare all variables at the top of your method.

I think ternary operator ?: is usually used for its result, not for side-effects of called code (here you're ignoring returned values). At first this usage is confusing for caller.

If you have a loop I think for is more clear (in intent) than while. Do not worry about extra variable, compiler will optimize it for you.

int main()
{
    int numbersToRead;
    std::cin >> numbersToRead;

    for (int i=0; i < numbersToRead; ++i)
    {
       int number;
       std::cin >> number;

       bool isEven = (number & 1) == 0;
       std::cout << (isEven  ? "Yes" : "No") << std::endl;
    }

    return 0;
}

This example is pretty small but for more complex code you may want to extract some functions:

int main()
{
    for (int i=readNumberOfValuesToRead(); i > 0; --i)
       std::cout << (isEven(readValue()) ? "No" : "Yes") << std::endl;

    return 0;
}

If you're already using Boost you may use boost::irange (let me also show that you may/should move formatting to a proper manipulator (for simplicity in this example I use standard one which prints true/false instead of Yes/No):

int main()
{
    std::cout << std::boolalpha;
    for (auto i : boost::irange(0, readNumberOfValuesToRead()))
       std::cout << isEven(readValue()) << std::endl;

    return 0;
}

I'd stop here (but read notes) for this code however if your scenario is (or it will be) more complex you will probably need to introduce more classes: ValuesReader base class (with a StandardInputValuesReader concrete class) to read values from an input stream and ValuesWriter (same...) to write output somewhere (using a ValueProcessor or ValueConverter and a custom stream manipulator?) Also remember that proper classes will make your life incredibly more easy during testing (because an abstract base class can be easily mocked while to read from std::cin you need much more code in your tests - and they can't be well-tested in isolation.)

EDIT

Few notes:

• As Snowhawk04 noted I/O synchronization (between C and C++ functions) may slow down execution (or it may even not).
• (number & 1) == 0 and (number % 2) == 0 seem to have the same performance (and generated assembly output), at least on GCC. Pick the one you feel more comfortable with.
• Flushing output buffer (because of newline) may make it slower (but again consider that you're waiting user input). A different approach may help (concatenate results into std::string or std::stringstream and then write just once to std::cout). It's not a good approach if your application is interactive but it may be viable if it's intended to be used from command line with I/O redirection.

Just a proof of concept:

int main() 
{
    std::ostringstream output;
    output << std::boolalpha;
    for (int i : boost::irange(0, readNumberOfValuesToRead(), 0))
        output << isEven(readValue()) << std::endl;

    std::cout << output.str();

    return 0;
}

• Someone noted '\n' instead of std::endl will prevent flushing. '\n' has some performance benefits but you won't have a single flush because we're also reading from std::cin. The use of std::stringstream is the way to avoid flushing. Note that it is implementation dependent if this useless flush() will impact performance or not for std::cout (when std::cout.sync_with_stdio(false) is called.) In general I'd suggest to use it (measure...) but still stay on std::stringstream if you want to avoid multiple flushes (not for interactive use.)
• I am just half joking but for a non-interactive use if you really need to squeeze maximum performance from this program then you may want to write it in C (in practice dropping C++ I/O and strings...)

Answer 2

Don't use std::endl, use a "\n" character. endl not only prints a new line, but it also flushes the buffers. This ensures that you see the text immediately after the endl is printed. However, in this case you don't need that. If you want speed, use "\n". It will buffer as much as it feels like internally.

Answer 3

You'd probably be faster asking for a single user input than in each iteration.

E.g. ask "list of values: " 1,54,42,67,123,69 (you can either recalculate N, or ask N to be the first number).

For example, in C,

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 128

int main(void)
{
  char input[SIZE];
  char value[SIZE];
  int a,b;
  int v, isOdd;

  printf("Enter the list of numbers separated by a comma: ");
  scanf("%s",&input);

  a = 0;

  do
  {
    b = strcspn(&input[a],",\n");

    if (b<a)
    {
      v = atoi(&input[a]);
    }
    else
    {
      memcpy(value,&input[a],b);
      v = atoi(value);
    }

    isOdd = (v&1);
    printf("%d: %s\n",v,(isOdd==0)?"yes":"no");
    a += b+1;
  } while (input[a] != '\n');

  return 0;
}

which gives

Enter the list of numbers separated by a comma: 1,2,3,4
1: no
2: yes
3: no
4: yes