Поиск большинства соответствующих битов

Question

Я пытаюсь найти эффективный способ получить большинство соответствующих бит в группе целых чисел одного и того же размера. К примеру, в заданных целых числах:

12 => 1 1 0 0 
9 => 1 0 0 1 
9 => 1 0 0 1 
3 => 0 0 1 1 

большинство битых (колонки разумных) можно представить в виде:

 1 0 0 1 

Если есть равное количество 1-х и (колонка стрелки) 0, он должен 1. Я хотел бы достичь этого, используя целые числа, не переведя целое число в двоичную строку, если это возможно.

Answer 1

В C, это может быть что-то вроде этого:

unsigned arr[] = { 12, 9, 9, 3 };  // values to loop through 
unsigned len = sizeof(arr)/sizeof(arr[0]); // # of values 
unsigned result = 0;     // collect result here 
unsigned bits = sizeof(arr[0]) * 8; // number of bits to consider 
unsigned threshold = len/2 + ((len & 1) ? 1 : 0); // minimum # of 1 to get a 1 
unsigned bit = 1 << (bits - 1);  // bit mask; point to most significant bit position 

for (unsigned pos = 0; pos < bits; pos++) { 
    unsigned ones = 0; 
    for (unsigned i = 0; i < len; i++) { 
     if ((bit & arr[i]) != 0) { 
      ones++; 
     } 
    } 

    result = (result << 1) + ((ones >= threshold) ? 1 : 0); 
    bit = bit >> 1; 
} 

printf("\n%d\n", result); 

Внешний контур сдвигает битовую маску из наиболее незначимых к наименее значимым концу. Внутренняя петля подсчитывает биты, установленные на 1. Если 1 бит превышает пороговое значение, в результат сдвигается 1. В противном случае значение 0 сдвигается. В конце результат имеет большинство бит в соответствии с запросом.

Это может быть дополнительно оптимизировано, но не должно обеспечивать удобочитаемость.

---

Упрощенная для специального случая LEN == 4

unsigned arr[] = { 12, 9, 9, 3 };  // values to loop through 
unsigned len = sizeof(arr)/sizeof(arr[0]); // # of values 
unsigned result = 0;     // collect result here 

// for len==4, majority means that 2 or more bits are 1 
for (unsigned i = 0; i < len - 1; i++) 
    for (unsigned j = i + 1; j < len; j++) { 
     result = result | (arr[i] & arr[j]); 
    } 

printf("\n%d\n", result);