Как узнать, есть ли четное или нечетное число 1 бит

Возможно, не самый быстрый, но он работает и довольно прост:

int evenNumberOfOnes(unsigned int num)
{
    int n=0;
    while(num > 0) {
        n ^= num;
        num = num >> 1;
    }
    return n & 1;
}

Спасибо @EricPostpischil за советы по улучшению.

Один из способов сделать это — подсчитать количество битов и проверить младший бит, чтобы увидеть, является ли значение нечетным или четным, 1 или 0 соответственно. Учитывая 32-битное целое число, мы можем подсчитать количество 1 в его двоичном представлении, Вес Хэмминга с помощью некоторых хитрых битовых манипуляций. Уже есть хороший ответ о том, как найти вес Хэмминга здесь, и это тоже говорит об эффективности.

Возьмем этот алгоритм нахождения веса Хэмминга путем сложения с боковым накоплением. hasOddCount возвращает 1, если x имеет нечетное количество 1s.

int hasOddCount(int x) {
    int first = 0x11 | (0x11 << 8);
    int second = first | (first << 16);
    int mask = 0xf | (0xf << 8);
    int count = 0;
    int sum = second & x;
    sum = (x>>1 & second) + sum;
    sum = (x>>2 & second) + sum;
    sum = (x>>3 & second) + sum;

    sum = sum + (sum >> 16);

    sum = ((sum & mask) + (mask & (sum >> 4)));
    count = (((sum >> 8) + sum) & 0x3f);

    //count is the Hamming weight, & by 0x1 to see if it's odd
    return count & 0x1;
}

Я уверен, что это не наименьший возможный код, но он короткий и понятный;

#include <stdio.h>

int main(int argc, const char * argv[]) {
    unsigned x;
    int count;

    scanf("%u\n",&x);

    for(count=0;x;x>>=1)
        if(x&1)
            ++count;

    puts(count&1?"odd":"even");

    return(0);
}

Кстати: я пишу код с уровнем алкоголя в крови 0,05, я не проверял это, и завтра мне может быть неловко, если я неправильно понял эту простую задачу. Пожалуйста, не вводите этот код во что-либо, использующее термоядерное оружие или беспилотные автомобили.

РЕДАКТИРОВАТЬ: Увидев ответы других, которые также могут быть правильными &| сложный; Самый быстрый код действительно будет зависеть от архитектуры. Модуль очень быстр только на некоторых процессорах, на других он будет потреблять много циклов. Все смещается примерно за одни и те же несколько циклов.

int parity(int n) {
   int p = 0;

   for (;n;n>>=1) {
      p = (n&1) ? 1-p : p;
   }

   return p;
}

вернет ноль, если количество единиц в аргументе n четно. Простой тест:

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

int main() {
   srand(time(NULL));
   for (int i=0;i<100;i++) {   
      int n = rand();
      printf("%d has an %s number of 1's \n", n, parity(n)  ? "odd" : "even");
   }
}

Я публикую это как новый ответ, так как он немного хакерский и немного отличается от моего другого ответа.

int evenNumberOfOnesFast(unsigned int num)
{
    unsigned char *b;
    b = (unsigned char *)#
    unsigned char par[4]={0};

    for(int i=0; i<8; i++) {
        for( int j=0; j<4; j++) {
            par[j]^=b[j];
            b[j]=b[j] >> 1;
        }
    }
    return (par[0] ^ par[1] ^ par[2] ^ par[3]) & 1;
}

Здесь я предполагаю, что int составляет 4 байта. Я надеялся, что это позволит процессору делать некоторые вещи параллельно в конвейере. Я не уверен, что это так, но это было примерно в два раза быстрее, чем моя предыдущая версия.

Вот основная функция для проверки:

#define N 10000000
int main()
{
    int * arr = malloc(N*sizeof(*arr));
    int * par = malloc(N*sizeof(*par));

    // Random values to prevent optimizer from just removing the code                                              
    srand(time(NULL));

    for(int i=0; i<N; i++)
        arr[i]=rand();

    // Correctness check                                                                                           
    for(int i=0; i<N; i++)
        if(evenNumberOfOnes(arr[i]) != evenNumberOfOnesFast(arr[i])) {
            perror ("Error");
            exit(EXIT_FAILURE);
        }

    clock_t begin, end;
    double time_spent;

    begin = clock();

    for(int i=0; i<N; i++)
        par[i]=evenNumberOfOnes(arr[i]);

    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf(" Time: %f\n", time_spent);

    begin = clock();

    for(int i=0; i<N; i++)
        par[i]=evenNumberOfOnesFast(arr[i]);

    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf(" Time: %f\n", time_spent);
}

И результат:

$ cc r.c -O3 -Wall -Wextra
$ ./a.out 
 Time: 0.201635
 Time: 0.093152

Тем не менее, я также протестировал решение hasOddCount, предоставленное @Miket25, и на самом деле оно примерно в десять раз быстрее, чем мой быстрый вариант.