powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Вес Хэмминга: реализация и некоторые вопросы.
25 сообщений из 59, страница 1 из 3
Вес Хэмминга: реализация и некоторые вопросы.
    #38986435
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.
Речь идёт о двоичном представлении числа. Классические реализации известны

Код: plaintext
1.
2.
3.
4.
5.
6.
int popcount(long long x) {
    int res;
    for (res=0; x; res++)
        x &= x-1;
    return res;
}



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

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
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 в стандарте языка Си нет. Хотя может быть не в той документации искал. Пользовались ли вы такими функциями и правильно ли я понимаю, их вызов требует меньшего времени по сравнению с классическими реализациями показанными выше ?

Интересно, существовали ли раньше методы шифрования использующие данную характеристику ?
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38986480
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Возможно таблицами быстрее будет

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
    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;
    }


...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38986491
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
__builtin_popcount - это "встроенная функция" для GCC только под х86, генерирует соответствующую машинную команду popcnt . Непереносимо на другие архитектуры/компиляторы, есть аналог для msvc
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38986888
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Из набора SSE4 есть такая штука.

Тут можно найти описание POPCNT.
https://software.intel.com/sites/default/files/c8/ab/17971-intel_20sse4_20programming_20reference.pdf
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38987402
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Спасибо! Скоро протестирую.

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

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
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 то всё ок
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38987404
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
а, long long x затирает память под get_HW(). Прошу прощение
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38987426
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати. Почему данную характеристику иначе называют "population count" ?
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38987431
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

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

Что за формат такой %i ?
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38987434
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MasterZiv,

Для x формат должен быть %ll
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38987446
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MasterZivSashaMercury,

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

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

ну может быть :)
с форматом разобрался, спасибо :)
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38987865
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MasterZivЧто за формат такой %i ?

Отвечу сам себе, посмотрев в документации:
%i - полный аналог %d.
Я этого не знал, всю жизнь использовал %d и не жужжал.
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38987977
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MasterZivMasterZivЧто за формат такой %i ?

Отвечу сам себе, посмотрев в документации:
%i - полный аналог %d.
Я этого не знал, всю жизнь использовал %d и не жужжал.

я подумал что это был риторический вопрос в контексте "что за i если должно быть lli" :)
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38989336
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.
На прошлой неделе стал решать такую задачу .
Вообще говоря, требуется найти m элемент такой последовательности . Приводится слабая оценка . Например при m= это приближение даёт 5120, а должно быть 5981.
В целом, я представляю как решить эту задачу. Но данное решение требует предварительные вычисления(объём которых больше, чем мне хочется) и не кажется мне хорошим/красивым/правильным(с точки зрения как реализации, так и алгоритма). Может быть у кого-нибудь есть идеи как лучше подступиться к решению данной задачи?
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38989352
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вычисление 100000000 значений у меня занимает 0,7сек
весь диапазон 2*10^9 делим на 20 частей и заранее вычисляем 20 значений ключа
не очень красиво, но тест пройдет
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38989355
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
m_Slaвычисление 100000000 значений у меня занимает 0,7сек
весь диапазон 2*10^9 делим на 20 частей и заранее вычисляем 20 значений ключа
не очень красиво, но тест пройдет

Если делить по 100 000 000 то потребуется порядка 300 участков. Собственно это и пришло в голову. Кроме того, возникнут нюансу связанные с тем, что первое число не всегда 1. Они конечно решаются, но слишком много предварительных вычислений в итоге.
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38989360
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
не подойдет вариант
первое число может быть 4, его вообще в последовательности нет
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38989362
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
m_Slaне подойдет вариант
первое число может быть 4, его вообще в последовательности нет

это все решается. Хранятся промежуточные массивы которые принадлежат всем возможным последовательностям, т.е. каждый слой шириной 10^8 элементов хранится массив из 30 элементов с некоторыми характеристиками. Например так. Остальной ерунда, и дело техники. Но это очень некрасивый способ, и мне очень не хочется его использовать. Наверняка должно быть хорошее решение.
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38990245
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати, __popcnt64 не работает в MVS Express 2013. Возможно из-за версии express, т.к.__popcnt и popcnt16 работают.
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38990255
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury, __popcnt64 не работает на 32х битной платформе, только в х64. Не знаю как 2013, но раньше Express действительно не поддерживал компиляцию под 64 бита.
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38990256
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вычислить значение ключа через 2 000 000 000 минут
на С (mingw) считает за 20,2 сек
на asm считает 4,2 сек
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
	; fasm 1.71.39

	format PE console
	include 'win32axp.inc'

	.data

	format_string  db 'key(HEX) = %04X%04X',9,'%d.%d sek',0
	output_string  db 256 dup ( 0 )

	SystemTimeBegin SYSTEMTIME
	SystemTimeEnd	SYSTEMTIME
	FileTimeBegin	dd 0, 0
	FileTimeEnd	dd 0, 0

	key dd 0, 0

	.code
start:

	; Для расчета быстродействия запрашиваем системное время начала цикла
	invoke GetSystemTime, SystemTimeBegin

	; расчет ключа 64 бита
	;   начальное значение 1
	;   вычислить значение ключа через 2000000000 минут
	mov edi, 2000000000
	xor ecx, ecx
	mov ebx, 1
 @@:
	; key = key + popcount(key)
	; ebx - младшие 32 бита key
	; eсx - старшие 32 бита key

	; popcount 64 бита
	popcnt eax, ebx
	popcnt edx, ecx
	add eax, edx

	; key + popcount(key)
	add ebx, eax
	adc ecx, 0

	dec edi
	jnz @b
	mov [key], ebx
	mov [key + 4], ecx

	; Для расчета быстродействия запрашиваем системное время окончания цикла
	invoke GetSystemTime, SystemTimeEnd

	; для удобства расчета переводим SYSTEMTIME в FILETIME
	invoke SystemTimeToFileTime, SystemTimeBegin, FileTimeBegin
	invoke SystemTimeToFileTime, SystemTimeEnd, FileTimeEnd
	; TimeEnd - TimeBegin
	; eax - секунды
	; edx - миллисек
	mov eax, [FileTimeEnd]
	mov edx, [FileTimeEnd + 4]
	sub eax, [FileTimeBegin]
	sbb edx, [FileTimeBegin + 4]
	mov ebx, 10000000
	div ebx

	cinvoke wsprintfA, output_string, format_string, [key + 4], [key], eax, edx
	invoke MessageBoxA, 0, output_string, 'Test', MB_OK

	invoke ExitProcess,0
	.end start

...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38990264
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Barlone,

IDE такой функции не знает. У меня 64 битная платформа.
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38990266
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
m_Sla,

а нужно за секунду :)
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38990269
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SSm_Sla,

а нужно за секунду :) хотя наверняка можно быстрее
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38990271
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
popcount2() из первого поста быстро работает
Код: plaintext
1.
2.
3.
4.
5.
	long long x = 1;
	while(x < 2000000000) {
		x += popcount2(x);
	}
	printf("x=%llu  time: %d ms\n", x, clock());



результатx=2000000010 time: 620 ms
...
Рейтинг: 0 / 0
Вес Хэмминга: реализация и некоторые вопросы.
    #38990272
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вариант m_Sla с таблицей 17785880 немного быстрее
тест popcount3()x=2000000010 time: 460 ms
popcount3()
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
int popcount3(int x)
{
	static int table[256] ={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,
							2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
							2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,
							4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
							2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,
							3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
							4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};
    union{
        unsigned int i;
        unsigned char c[4];
    }u;

    u.i = x;

    int res;

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

    return res;

}

...
Рейтинг: 0 / 0
25 сообщений из 59, страница 1 из 3
Форумы / C++ [игнор отключен] [закрыт для гостей] / Вес Хэмминга: реализация и некоторые вопросы.
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]