Сокращение расстояния Хэмминга - C++ - Ответ 1289299

@lemegeton · 15.01.2011, 13:28

Ну тогда так.

C++

#include <cstdio>
#include <cstddef>
#include <cstdlib>
#include <ctime>
#include <cmath>
 
// подсчет количества бит, установленных в 1
size_t CountBits(const size_t a_number) {
  size_t temporary_number = a_number;
  size_t bits_counter = 0;
  while (temporary_number != 0) {
    if (temporary_number & 1) ++bits_counter;
    temporary_number >>= 1;
  }
  return bits_counter;
}
 
// подсчет количества разных бит
// нужно только для того, чтобы показать, что алгоритм работает
size_t CountDefferentBits(const size_t a, const size_t b) {
  return CountBits(a ^ b);
}
 
// подсчет расстояния Хэмминга для двух массивов
size_t HammingDistance(size_t *first_array, size_t *second_array,
                       size_t array_size) {
  size_t result = 0;
  for (int i = 0; i < array_size; ++i)
    result += CountDefferentBits(first_array[i], second_array[i]);
  return result;
}
 
size_t DecreaseHammingDistance(size_t *first_array, size_t *second_array,
                                size_t array_size, size_t bits_to_change) {
  size_t changed_bits = 0;
  size_t bits_in_element = sizeof(*first_array) * 8;
  size_t total_bits = array_size * bits_in_element;
  size_t current_bit = 0;
  while ((changed_bits < bits_to_change) && (current_bit < total_bits)) {
    size_t current_element = current_bit / bits_in_element;
    size_t bit_in_element  = current_bit % bits_in_element;
    if ((first_array[current_element]  & (1 << bit_in_element)) !=
        (second_array[current_element] & (1 << bit_in_element))) {
      first_array[current_element]  |= (1 << bit_in_element);
      second_array[current_element] |= (1 << bit_in_element);
      ++changed_bits;
    }
    ++current_bit;
  }
  return changed_bits;
}
 
int main(int argc, char *argv[]) {
  srand(time(NULL));
 
  // инициализация двух массивов
  size_t array_size = 20 + rand() % 10;
  size_t *first_array = new size_t[array_size];
  size_t *second_array = new size_t[array_size];
 
  // заполнение двух массивов случайными числами
  for (int i = 0; i < array_size; ++i) {
    first_array[i]  = rand() % 65535;
    second_array[i] = rand() % 65535;
  }
 
  printf("%d\n", HammingDistance(first_array, second_array, array_size));
  printf("%d\n", DecreaseHammingDistance(first_array, second_array, array_size, array_size));
  printf("%d\n", HammingDistance(first_array, second_array, array_size));
  // удаление массивов
  delete [] first_array;
  delete [] second_array;
  return 0;
}

Добавлено через 30 минут
Если нужно менять только один массив.

C++

#include <cstdio>
#include <cstddef>
#include <cstdlib>
#include <ctime>
#include <cmath>
 
// подсчет количества бит, установленных в 1
size_t CountBits(const size_t a_number) {
  size_t temporary_number = a_number;
  size_t bits_counter = 0;
  while (temporary_number != 0) {
    if (temporary_number & 1) ++bits_counter;
    temporary_number >>= 1;
  }
  return bits_counter;
}
 
// подсчет количества разных бит
// нужно только для того, чтобы показать, что алгоритм работает
size_t CountDefferentBits(const size_t a, const size_t b) {
  return CountBits(a ^ b);
}
 
// подсчет расстояния Хэмминга для двух массивов
size_t HammingDistance(size_t *first_array, size_t *second_array,
                       size_t array_size) {
  size_t result = 0;
  for (int i = 0; i < array_size; ++i)
    result += CountDefferentBits(first_array[i], second_array[i]);
  return result;
}
 
size_t DecreaseHammingDistance(size_t *first_array, size_t *second_array,
                                size_t array_size, size_t bits_to_change) {
  size_t changed_bits = 0;
  size_t bits_in_element = sizeof(*first_array) * 8;
  size_t total_bits = array_size * bits_in_element;
  size_t current_bit = 0;
  while ((changed_bits < bits_to_change) && (current_bit < total_bits)) {
    size_t current_element = current_bit / bits_in_element;
    size_t bit_in_element  = current_bit % bits_in_element;
    if ((first_array[current_element]  & (1 << bit_in_element)) !=
        (second_array[current_element] & (1 << bit_in_element))) {
      //second_array[current_element] |= (1 << bit_in_element);
      //first_array[current_element]  |= (1 << bit_in_element);
      second_array[current_element] ^= (1 << bit_in_element);
      ++changed_bits;
    }
    ++current_bit;
  }
  return changed_bits;
}
 
int main(int argc, char *argv[]) {
  srand(time(NULL));
 
  // инициализация двух массивов
  size_t array_size = 20 + rand() % 10;
  size_t *first_array = new size_t[array_size];
  size_t *second_array = new size_t[array_size];
 
  // заполнение двух массивов случайными числами
  for (int i = 0; i < array_size; ++i) {
    first_array[i]  = rand() % 65535;
    second_array[i] = rand() % 65535;
  }
 
  printf("%d\n", HammingDistance(first_array, second_array, array_size));
  printf("%d\n", DecreaseHammingDistance(first_array, second_array, array_size, array_size * sizeof(size_t) * 8));
  printf("%d\n", HammingDistance(first_array, second_array, array_size));
  // удаление массивов
  delete [] first_array;
  delete [] second_array;
  return 0;
}

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

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

Другие темы раздела
C++ Нажно написать программу на языке програм С "моделирование движения" https://www.cyberforum.ru/ cpp/ thread228251.html Нужно написать программу моделирующую движение спутника вокруг планеты. Грубо говоря написать программу в которой будет один объект вращаться вокруг второго. Писать можно любыми способами но: программа должно быть написана на языке С а не С++ спутник не вращается вокруг своей оси,планета не вращается вокруг своей оси, спутник вращается только вокруг планеты, вращение происходит в 1 плоскости...	C++ Про CRC32 Народ, кто шарит в CRC, помогите. Прогу надо доделать или переделать, может у кого-нибудь рабочий вариант есть? Тестировалось в MV C++ 6. Bulder C++ 6. Borland 3.1. везде одни и теже ошибки #include <stdio.h> #include <string.h> #include <conio.h> void Update_CRC(char in, char crc) { #define POLYNOMIAL 0xEDB88320//Полином crc = *crc^in;
C++ Работа с изображениями Добрый день! Есть тут знающие как работать с изображениями (Масштабировать, скопировать/вставить, обрезать). А то что-то не могу ни как разобраться. Может книги какие кто знает :) https://www.cyberforum.ru/ cpp/ thread227442.html	C++ Программа завершения процесса Возможно ли написать программу, чтобы завершить процесс mail.ru agenta? Да, и если возможно, из другого пк. (через сетку). Если есть такая, выложите пожалуйста, очень надо. https://www.cyberforum.ru/ cpp/ thread227392.html
C++ Не получается разрешить доступ к интернету Не получается разрешить доступ к интернету через LAN другому компьютеру	C++ Irrlicht https://www.cyberforum.ru/ cpp/ thread226685.html Доброго времени суток. Проблема состоит в том, что при загрузке движка Irrlicht все в порядке, а при прописывании программе через какой путь ей надо пройти, чтобы обратиться к классу, показывает, что что-то не так. Не смотря на это, программа какое-то время правильно функционирует, но не создает экзешник, спустя еще несколько дней она просто отказывается работать и предлагает попробовать...
C++ Получить индекс типа в mpl::map`е всем привет. есть mpl карта типов(key -> value). нужно получить индекс типа имея только ключ. где-то накосячил. но непойму где. #include <iostream> #include <boost/mpl/distance.hpp> #include <boost/mpl/find.hpp> #include <boost/mpl/find_if.hpp> https://www.cyberforum.ru/ cpp/ thread226098.html	Отвечает за стиль программы - Code Blocks или mingw? C++ Здравствуйте! Столкнулся с такой проблемой - при компиляции программ в Code Blocks с помощью mingw стиль получается как у классического Windows (к примеру, некрасивые кнопки и меню) в любом случае. Где только не искал - не могу найти как изменить на обычные. <==Классичный стиль <==обычный. Кто сталкивался прошу ответить. Спасибо! Прикрепляйте картинки к сообщениям.
C++ Таинственный макрос Здравствуйте, в исходники nginx (веб-сервер) есть такой макрос: int ngx_cdecl main(int argc, char const argv) { //...некий код... } Он встречается еще и в других функциях. Само его объявление пустое (он в конце): #if !(NGX_WIN32) https://www.cyberforum.ru/ cpp/ thread224518.html	C++ Люди, кто может помочь в написании проги Составить прогу на С++, которая кодирует текст, алгоритмом Лемпела-Зива (Не LZW). Выводится в текствой файл двоичный код каждого символа. Выводится CRC-код текстового файла. ******************************************************************** Перерыл весь инет, но подобного не смог найти, одни архиваторы, а мне надо закодировать текст введённый пользователем. Очень буду благодарен всем, кто... https://www.cyberforum.ru/ cpp/ thread223728.html
C++ Прямое обращение к памяти Доброго всем времени суток. Товарищи, помогите пожалуйста найти литературу для компилятора DJGPP. Точнее для особенностей данного компилятора. В частности интересует прямое обращение к ОЗУ. Насколько я понял данный компилятор использует 32-битный режим, т.е. может позволить обращение ко всему пространству ОЗУ. Задача заключается в том, чтобы по заданному адресу записать в оперативную память...	C++ Проверка ввода https://www.cyberforum.ru/ cpp/ thread223435.html Помогите пожалуйста с проверкой. Нужно, чтобы при вводе массива x, если предыдущее значение больше вводимого, пользователю выдало сообщение об ошибке и он ввел правильное значение (которое больше предыдущего) void interpol::input() { int i; cout<<"Kolichestvo yzlov: "; do { cin>>n; if(n<=0) cout<<"Nepravilnyj vvod. Vvedite koli4estvo yzlov: "; } while(n<=0);

	15.01.2011, 13:28