Сокращение расстояния Хэмминга

@Molotoff · Регистрация: 21.07.2009

Добрый день, уважаемые форумчане.
Есть у меня следующая ситуация: имеем два массива одинаковой длины типа unsigned int, например arr1[2] и arr2[2] (на самом деле размерность может быть любой).
Необходимо сократить расстояние Хэмминга между этими двумя наборами чисел, т.е., имеем, например, следующие числа
arr1 656546345 15632489
arr2 606214697 78559272
которые в двоичном коде выглядят как
arr1 0010 0111 0010 0010 0001 1010 0010 1001 0000 0000 1110 1110 1000 1000 0110 1001
arr2 0010 0100 0010 0010 0001 1010 0010 1001 0000 0100 1010 1110 1011 1000 0010 1000
Расстояние Хэмминга в данном случае - число отличающихся бит массива arr1 от arr2 (здесь оно равно 8-ми). Причем, это должен быть один или n бит, выбранные случайным образом, т.е. не обязательно менять первый отличающийся бит, это может быть и 5-й и 10-й и т.д.
На ум приходит только не очень эффективный способ:
взять единицу и случайным образом ее двигать влево-вправо, пока не будет найден отличающийся бит и не будет заменен на противоположный.
Вопрос: можно ли как-то более эффективнее с точки зрения скорости выполнения сделать или тут без вариантов?
P.S. Почему нужно оптимизировать по скорости выполнения - эта операция будет повторяться много раз, что скажется на общем времени выполнения программы.

Вернуться к обсуждению:
Сокращение расстояния Хэмминга

Следующий ответ

Другие темы раздела
C++ Нажно написать программу на языке програм С "моделирование движения" https://www.cyberforum.ru/ cpp/ thread228251.html Нужно написать программу моделирующую движение спутника вокруг планеты. Грубо говоря написать программу в которой будет один объект вращаться вокруг второго. Писать можно любыми способами но:...	C++ Про CRC32 Народ, кто шарит в CRC, помогите. Прогу надо доделать или переделать, может у кого-нибудь рабочий вариант есть? Тестировалось в MV C++ 6. Bulder C++ 6. Borland 3.1. везде одни и теже ошибки...
C++ Работа с изображениями Добрый день! Есть тут знающие как работать с изображениями (Масштабировать, скопировать/вставить, обрезать). А то что-то не могу ни как разобраться. Может книги какие кто знает :)	C++ Программа завершения процесса Возможно ли написать программу, чтобы завершить процесс mail.ru agenta? Да, и если возможно, из другого пк. (через сетку). Если есть такая, выложите пожалуйста, очень надо. https://www.cyberforum.ru/ cpp/ thread227392.html
C++ Не получается разрешить доступ к интернету https://www.cyberforum.ru/ cpp/ thread226820.html Не получается разрешить доступ к интернету через LAN другому компьютеру	Irrlicht C++ Доброго времени суток. Проблема состоит в том, что при загрузке движка Irrlicht все в порядке, а при прописывании программе через какой путь ей надо пройти, чтобы обратиться к классу, показывает,...
C++ Получить индекс типа в mpl::map`е всем привет. есть mpl карта типов(key -> value). нужно получить индекс типа имея только ключ. где-то накосячил. но непойму где. #include <iostream> #include <boost/mpl/distance.hpp>...	C++ Отвечает за стиль программы - Code Blocks или mingw? Здравствуйте! Столкнулся с такой проблемой - при компиляции программ в Code Blocks с помощью mingw стиль получается как у классического Windows (к примеру, некрасивые кнопки и меню) в любом случае.... https://www.cyberforum.ru/ cpp/ thread225103.html
C++ Таинственный макрос https://www.cyberforum.ru/ cpp/ thread224518.html Здравствуйте, в исходники nginx (веб-сервер) есть такой макрос: int ngx_cdecl main(int argc, char const argv) { //...некий код... } Он встречается еще и в других функциях. Само его...	C++ Люди, кто может помочь в написании проги Составить прогу на С++, которая кодирует текст, алгоритмом Лемпела-Зива (Не LZW). Выводится в текствой файл двоичный код каждого символа. Выводится CRC-код текстового файла.... https://www.cyberforum.ru/ cpp/ thread223728.html

@Molotoff 1 / 1 / 0 Регистрация: 21.07.2009 Сообщений: 50
		0
	Сокращение расстояния Хэмминга 14.01.2011, 10:47. Просмотров 3210. Ответов 14 Метки (Все метки) Добрый день, уважаемые форумчане. Есть у меня следующая ситуация: имеем два массива одинаковой длины типа unsigned int, например arr1[2] и arr2[2] (на самом деле размерность может быть любой). Необходимо сократить расстояние Хэмминга между этими двумя наборами чисел, т.е., имеем, например, следующие числа arr1 656546345 15632489 arr2 606214697 78559272 которые в двоичном коде выглядят как arr1 0010 0111 0010 0010 0001 1010 0010 1001 0000 0000 1110 1110 1000 1000 0110 1001 arr2 0010 0100 0010 0010 0001 1010 0010 1001 0000 0100 1010 1110 1011 1000 0010 1000 Расстояние Хэмминга в данном случае - число отличающихся бит массива arr1 от arr2 (здесь оно равно 8-ми). Причем, это должен быть один или n бит, выбранные случайным образом, т.е. не обязательно менять первый отличающийся бит, это может быть и 5-й и 10-й и т.д. На ум приходит только не очень эффективный способ: взять единицу и случайным образом ее двигать влево-вправо, пока не будет найден отличающийся бит и не будет заменен на противоположный. Вопрос: можно ли как-то более эффективнее с точки зрения скорости выполнения сделать или тут без вариантов? P.S. Почему нужно оптимизировать по скорости выполнения - эта операция будет повторяться много раз, что скажется на общем времени выполнения программы. Вернуться к обсуждению: Сокращение расстояния Хэмминга Следующий ответ 0