Быстрый способ узнать вычислительную четность битвектора

StackOverflow https://stackoverflow.com//questions/22062709

  •  23-12-2019
  •  | 
  •  

Вопрос

Я работаю с битвекторами в C.Мои битвекторы unsigned long longх.Для большого количества векторов мне нужно знать, есть ли четность, т.е.количество бит, равное 1, является четным или нечетным.

Точное значение не имеет значения, важен только паритет.Мне было интересно, есть ли что-нибудь быстрее, чем вычисление количества единиц и проверка.Я пытался что-то придумать, но ничего не нашел.

Короткий пример того, как я хочу, чтобы это работало:

void checkIntersection(unsigned long long int setA, unsigned long long int setB){
    if(isEven(setA & setB)){
        //do something
    }
}
Это было полезно?

Решение

С помощью техники «разделяй и властвуй»:

uint64_t a = value;
a ^= (a >> 32);            // Fold the 32 MSB over the 32 LSB
a ^= (a >> 16);            // reducing the problem by 50%
a ^= (a >> 8);             // <-- this can be a good break even point
..
return lookup_table[a & 0xff];  // 16 or 256 entries are typically good
..

Процедуру складывания можно применять до конца:

a ^= (a >> 1);
return a & 1;

В IA флаг четности можно получить напрямую после сокращения до 8 бит.

a ^= (a >> 4); это еще один хороший момент, чтобы прекратить деление, поскольку некоторые архитектуры процессоров могут предоставлять параллельные справочные таблицы. uint8_t LUT[16] встроен в регистры XXM (или NEON).Или просто потенциальные промахи в кэше LUT с 256 записями могут просто перегрузить вычислительную задачу одного дополнительного раунда.Естественно, лучше всего измерить, какой размер LUT является оптимальным в данной архитектуре.

Эта последняя таблица на самом деле состоит только из 16 бит и может быть эмулирована с помощью последовательности:

return ((TRUTH_TABLE_FOR_PARITY) >> (a & 15)) & 1;

где бит Н магической константы, приведенной выше, кодирует логическое значение для Паритет (Н).

Другие советы

Вы можете предвкушать в массиве четность для всех возможных комбинаций битов в байте: 

bool pre[256] = { 0, 1, 1, 0, 1, ....}
.

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

bool parity (long long unsigned x)
{   
    bool parity = 0;
    while(x)
    {   
        parity ^= pre[x&0xff];
        x>>=8;
    }
    return parity;
}
.

Отказ от ответственности: Я не проверил код, это просто идея.

Довольно легко.Что-то вроде 

unsigned population(unsigned long long x) {
  x = ((x >> 1) & 0x5555555555555555) + (x & 0x5555555555555555);
  x = ((x >> 2) & 0x3333333333333333) + (x & 0x3333333333333333);
  x = ((x >> 4) & 0x0f0f0f0f0f0f0f0f) + (x & 0x0f0f0f0f0f0f0f0f);
  x = (x >> 8) + x;  // Don't need to mask, because 64 < 0xff
  x = (x >> 16) + x;
  x = (x >> 32) + x;
  return x & 0xff;
}
.

должен работать.Кроме того, некоторые процессоры имеют инструкции по численности населения (я не думаю, что X86, разум).

Если вам нравится такая вещь, вы должны проверить книгу Hacker's Venglight от Генри С. Уоррена, JR.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top