Какой самый быстрый способ для битовых операций вычислить паритет?

Question

Мое решение: (для каждого бита входного блока есть такая строка)

*parity ^= (((x[0] >> 30) & 0x00000001) * 0xc3e0d69f);

Все типы являются uint32.Эта строка принимает второй бит ввода x, сдвигает его на младший бит и устанавливает все остальные биты в ноль.Затем 32-битная четность XORed с соответствующим набором четности, установленным для этого бита.

Я обнаружил, что это решение умножения является самым быстрым способом сделать это условное XOR.Есть ли более быстрый способ?

Answer 1

См. Здесь для некоторых аккуратных хаков для вычисления четности слова, байта и т. Д.

Answer 2

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

Общее правило: для x в{0, 1} x * N == - x & N

это потому что -x для 0все биты сброшены, а для 1 - -1, в котором все биты установлены.

Таким образом, исходная строка кода может быть переписана как:

*parity ^= (-((x[0] >> 30) & 0x00000001) & 0xc3e0d69f);

Какие две операции вычислены за меньшее время, чем умножениена многих микропроцессорах, но вы должны проверить это.

Также код может воспользоваться преимуществом сдвига со знаком вправо

*parity ^= (((int32_t)x[0] << 1 >> 31) & 0xc3e0d69f);

Первое смещение rshifts 30-й бит в 31-й, который является знаковым битом, а затем второйрасширить знак бита на всех остальных, так как смещение вправо на большинстве машин действует как пол ( x / 2 ^N ), таким образом, заполненный сдвинутый бит в знаке бит (abc...yz>>3 == aaaabc...yz).

Но эти уловки определены как неопределенное поведение в стандарте C и, таким образом, не переносимо .Используйте их осторожно.

Answer 3

Некоторые процессоры сделают это за вас.См. X86 флаг четности .

Answer 4

Если я правильно понимаю вопрос, вы делаете

for (i = 0; i < 32; i++)
    *parity ^= (((x[0] >> i) & 1) * SOME_CONST[i]); 

Если это так, то лучше использовать таблицы поиска:

for (i = 0; i < 4; i++)
    *parity ^= PARITY_LUT[i][ (x[0] >> (i*8)) & 0xFF];

Это будет стоить 256 КБ, но будет многобыстрее.