For your specific case where you initially have 0 and 1, the following might be faster. You'll have to bench mark it. You probably can't do much better with plain C though; you may need to dive into assembly if you want to take advantage of "x86 trickery" that may exist.

for(int i = 0; i < size ; i++){
  array[i] *= 123456;
}

EDIT:

Benchmark code:

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

size_t diff(struct timespec *start, struct timespec *end)
{
  return (end->tv_sec - start->tv_sec)*1000000000 + end->tv_nsec - start->tv_nsec;
}

int main(void)
{
  const size_t size = 1000000;
  int array[size];

  for(size_t i=0; i<size; ++i) {
    array[i] = rand() & 1;
  }

  struct timespec start, stop;

  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
  for(size_t i=0; i<size; ++i) {
    array[i] *= 123456;
    //if(array[i]) array[i] = 123456;
  }
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &stop);

  printf("size: %zu\t nsec: %09zu\n", size, diff(&start, &stop));
}

my results:

Computer: quad core AMD Phenom @2.5GHz, Linux, GCC 4.7, compiled with

$ gcc arr.c -std=gnu99 -lrt -O3 -march=native

• if version: ~5-10ms
• *= version: ~1.3ms

You can convert int to char* using itoa() and iterate over it to check does it contain number. If it does, get 4's position and replace it with 5.

I know you didnt work with strings, but it can be helpful in your case. Simple code:

#include <string.h>
#include <iostream>
#include <stdlib.h>
int main(){
  int numer;
  std::cin>>numer;
  char* str;
  itoa(numer, str, 10);
  for(int i = 0; i < strlen(str); i++){
    if(str[i] == '4') str[i]='5';
  }
}