Вес Хэмминга: реализация и некоторые вопросы.

SashaMercury
Дата: 18.06.2015 07:03:37
Здравствуйте.
Речь идёт о двоичном представлении числа. Классические реализации известны

+
int popcount(long long x) {
    int res;
    for (res=0; x; res++)
        x &= x-1;
    return res;
}


или реализации основанные на принципе "разделяй и властвуй" описанные, например, в книге Генри Уоррена "Алгоритмические трюки для программиста"

int popcount2(int x)
{
	x = x - ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x + (x >> 4)) & 0x0F0F0F0F;
	x = x + (x >> 8);
	x = x + (x >> 16);
	x = x & 0x0000003F;
	return x;
}

и т.д.


Прочитал что существуют методы в Си и С++ аналогичного назначения. И если объект bitset и метод count() я нашёл в стандарте С++, то функции __builtin_popcount в стандарте языка Си нет. Хотя может быть не в той документации искал. Пользовались ли вы такими функциями и правильно ли я понимаю, их вызов требует меньшего времени по сравнению с классическими реализациями показанными выше ?

Интересно, существовали ли раньше методы шифрования использующие данную характеристику ?
m_Sla
Дата: 18.06.2015 09:10:36
Возможно таблицами быстрее будет
+

    char table[256] = { ... };
    uint32_t popcount2(uint32_t i)
    {
        union{
            uint32_t i;
            char c[4];
        }x;

        x.i = i;

        uint32_t res;

        res = table[ x.c[0] ];
        res += table[ x.c[1] ];
        res += table[ x.c[2] ];
        res += table[ x.c[3] ];

        return res;
    }

Barlone
Дата: 18.06.2015 09:20:20
__builtin_popcount - это "встроенная функция" для GCC только под х86, генерирует соответствующую машинную команду popcnt. Непереносимо на другие архитектуры/компиляторы, есть аналог для msvc
mayton
Дата: 18.06.2015 13:44:06
Из набора SSE4 есть такая штука.

Тут можно найти описание POPCNT.
https://software.intel.com/sites/default/files/c8/ab/17971-intel_20sse4_20programming_20reference.pdf
SashaMercury
Дата: 19.06.2015 03:37:08
Спасибо! Скоро протестирую.

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

int get_HW(long long x)
{
	int r = 0;
	while (x){
		x &= x - 1;
		++r;
	}
	return r;
}

long long test(long long x, FILE* out)
{
	for (int i = 0; i < 1<<7; ++i){
		fprintf(out, "i = %3i x = %3i HW = %3i\n", i, x, get_HW(x));
		x = x + get_HW(x);
	}
	return x;
}

int main()
{
	FILE* out = fopen("output.txt", "w");

	test(1,stdout);
	fclose(out);
	return 0;
}


Если поменять местами get_HW(x) и x то всё ок
SashaMercury
Дата: 19.06.2015 03:39:09
а, long long x затирает память под get_HW(). Прошу прощение
SashaMercury
Дата: 19.06.2015 07:45:03
Кстати. Почему данную характеристику иначе называют "population count" ?
MasterZiv
Дата: 19.06.2015 08:18:12
SashaMercury,

Видимо, сколько битиков живут в слове.

Что за формат такой %i ?
MasterZiv
Дата: 19.06.2015 08:23:23
MasterZiv,

Для x формат должен быть %ll
SashaMercury
Дата: 19.06.2015 08:41:46
MasterZiv
SashaMercury,

Видимо, сколько битиков живут в слове.

Что за формат такой %i ?


ну может быть :)
с форматом разобрался, спасибо :)