Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / C++ [игнор отключен] [закрыт для гостей] / Вес Хэмминга: реализация и некоторые вопросы. / 25 сообщений из 59, страница 1 из 3
18.06.2015, 07:03
    #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
18.06.2015, 09:10
    #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
18.06.2015, 09:20
    #38986491
Barlone
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вес Хэмминга: реализация и некоторые вопросы.
__builtin_popcount - это "встроенная функция" для GCC только под х86, генерирует соответствующую машинную команду popcnt . Непереносимо на другие архитектуры/компиляторы, есть аналог для msvc
...
Рейтинг: 0 / 0
18.06.2015, 13:44
    #38986888
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вес Хэмминга: реализация и некоторые вопросы.
Из набора SSE4 есть такая штука.

Тут можно найти описание POPCNT.
https://software.intel.com/sites/default/files/c8/ab/17971-intel_20sse4_20programming_20reference.pdf
...
Рейтинг: 0 / 0
19.06.2015, 03:37
    #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
19.06.2015, 03:39
    #38987404
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вес Хэмминга: реализация и некоторые вопросы.
а, long long x затирает память под get_HW(). Прошу прощение
...
Рейтинг: 0 / 0
19.06.2015, 07:45
    #38987426
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вес Хэмминга: реализация и некоторые вопросы.
Кстати. Почему данную характеристику иначе называют "population count" ?
...
Рейтинг: 0 / 0
19.06.2015, 08:18
    #38987431
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вес Хэмминга: реализация и некоторые вопросы.
SashaMercury,

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

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

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

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

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

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

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

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

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

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

это все решается. Хранятся промежуточные массивы которые принадлежат всем возможным последовательностям, т.е. каждый слой шириной 10^8 элементов хранится массив из 30 элементов с некоторыми характеристиками. Например так. Остальной ерунда, и дело техники. Но это очень некрасивый способ, и мне очень не хочется его использовать. Наверняка должно быть хорошее решение.
...
Рейтинг: 0 / 0
23.06.2015, 04:47
    #38990245
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вес Хэмминга: реализация и некоторые вопросы.
Кстати, __popcnt64 не работает в MVS Express 2013. Возможно из-за версии express, т.к.__popcnt и popcnt16 работают.
...
Рейтинг: 0 / 0
23.06.2015, 07:18
    #38990255
Barlone
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вес Хэмминга: реализация и некоторые вопросы.
SashaMercury, __popcnt64 не работает на 32х битной платформе, только в х64. Не знаю как 2013, но раньше Express действительно не поддерживал компиляцию под 64 бита.
...
Рейтинг: 0 / 0
23.06.2015, 07:19
    #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
23.06.2015, 07:55
    #38990264
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вес Хэмминга: реализация и некоторые вопросы.
Barlone,

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

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

а нужно за секунду :) хотя наверняка можно быстрее
...
Рейтинг: 0 / 0
23.06.2015, 08:06
    #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
23.06.2015, 08:21
    #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
Форумы / C++ [игнор отключен] [закрыт для гостей] / Вес Хэмминга: реализация и некоторые вопросы. / 25 сообщений из 59, страница 1 из 3
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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