Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.83
Molotoff
1 / 1 / 0
Регистрация: 21.07.2009
Сообщений: 50
#1

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

14.01.2011, 10:47. Просмотров 2224. Ответов 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. Почему нужно оптимизировать по скорости выполнения - эта операция будет повторяться много раз, что скажется на общем времени выполнения программы.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.01.2011, 10:47     Сокращение расстояния Хэмминга
Посмотрите здесь:

Генерация чисел Хэмминга C++
Код Хэмминга C++
C++ Код Хэмминга кодер-декодер
C++ Последовательность Хэмминга
C++ Builder Код Хэмминга
C++ Код Хэмминга
Сокращение в Memo C++ Builder
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
14.01.2011, 10:52     Сокращение расстояния Хэмминга #2
Это: метрика Хэминга в википедии?
Molotoff
1 / 1 / 0
Регистрация: 21.07.2009
Сообщений: 50
14.01.2011, 10:56  [ТС]     Сокращение расстояния Хэмминга #3
да, да, именно о нем и идет речь, покороче пример приведу
x1 11010001
x2 10100101
здесь расстояние Хэмминга равно 4-м, алгоритм должен менять x2, например, так
x2 10000101
или так
x2 10010101
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
14.01.2011, 12:29     Сокращение расстояния Хэмминга #4
Ксоркой их, единицы в результате отметят позиции..
C++
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
bool f(unsigned int *arr1, ansigned int *arr2, unsigned int l, unsigned int n)
{
 unsigned int size;
 unsigned int i, j;
 unsigned int metric;
 char *p1,*p2, buffer;
 unsigned int changed;
 ststic char masks[8]={0x01, 0x02, 0x04,0x08,0x10,0x20,0x40,0x80};
 size=l*sizeof(unsigned int);
 if (size/sizeof(unsigned int)==l)
 {
  for (metric=0, p1=(char *)arr1+size-1, p2=(char *)arr2+size-1; p1>=(vhar *)arr1; --p1, --p2)
  {
   buffer=*p1^p2;
   for (j=7; j>=0; --j)
   {
    if (buffer&masks[j])
    {
     ++metric;
     if (metric==0)
     {
      return false;
     }
    }
   }
  }
  while (n!=0)
  {
   for (p1=(char *)arr1+size-1, p2=(char *)arr2+size-1; p1>=(vhar *)arr1; --p1, --p2)
   {
    buffer=*p1^p2;
    for (j=7; j>=0; --j)
    {
     if (buffer&masks[j])
     {
      if ((rnd%metric)<n)
      {     
       *p2=(*p2&(!masks[j]))&(*p1&masks[j]);
       --metric;
       --n;
      }
     }
    }
   }
  }
  retrun true;
 }
 retrun false;
}
. Именно этот вариант может с небольшой вероятностью виснуть, попробуй придумать гарантированный вариант выбора n бит.

Добавлено через 1 минуту
Уменьшить метрику до нуля можно простым копирожанием.
lemegeton
 Аватар для lemegeton
2915 / 1344 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
14.01.2011, 19:36     Сокращение расстояния Хэмминга #5
Уменьшить метрику между числами можно с помощью простейших логических операций.

C++
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
#include <cstdio>
#include <cstddef>
#include <cstdlib>
#include <ctime>
 
size_t CountDefferentBits(const size_t a, const size_t b) {
  size_t different_bits = a ^ b;
  size_t result = 0;
  while (different_bits > 0) {
    result += (different_bits & 1);
    different_bits >>= 1;
  }
  return result;
}
 
int main(int argc, char *argv[]) {
  srand(time(NULL));
  size_t a = rand()%65535;
  size_t b = rand()%65535;
 
  // уменьшение расстояния Хэмминга
  size_t c = a | (a ^ b);
 
  printf("Metrix(%d, %d) = %d\n", a, b, CountDefferentBits(a, b));
  printf("Metrix(%d, %d) = %d\n", c, b, CountDefferentBits(c, b));
  return 0;
}
Добавлено через 23 минуты
Цитата Сообщение от Molotoff Посмотреть сообщение
Причем, это должен быть один или n бит, выбранные случайным образом
Пардон, не заметил.
Molotoff
1 / 1 / 0
Регистрация: 21.07.2009
Сообщений: 50
15.01.2011, 08:13  [ТС]     Сокращение расстояния Хэмминга #6
Цитата Сообщение от taras atavin Посмотреть сообщение
Ксоркой их, единицы в результате отметят позиции..
C++
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
bool f(unsigned int *arr1, ansigned int *arr2, unsigned int l, unsigned int n)
{
 unsigned int size;
 unsigned int i, j;
 unsigned int metric;
 char *p1,*p2, buffer;
 unsigned int changed;
 ststic char masks[8]={0x01, 0x02, 0x04,0x08,0x10,0x20,0x40,0x80};
 size=l*sizeof(unsigned int);
 if (size/sizeof(unsigned int)==l)
 {
  for (metric=0, p1=(char *)arr1+size-1, p2=(char *)arr2+size-1; p1>=(vhar *)arr1; --p1, --p2)
  {
   buffer=*p1^p2;
   for (j=7; j>=0; --j)
   {
    if (buffer&masks[j])
    {
     ++metric;
     if (metric==0)
     {
      return false;
     }
    }
   }
  }
  while (n!=0)
  {
   for (p1=(char *)arr1+size-1, p2=(char *)arr2+size-1; p1>=(vhar *)arr1; --p1, --p2)
   {
    buffer=*p1^p2;
    for (j=7; j>=0; --j)
    {
     if (buffer&masks[j])
     {
      if ((rnd%metric)<n)
      {     
       *p2=(*p2&(!masks[j]))&(*p1&masks[j]);
       --metric;
       --n;
      }
     }
    }
   }
  }
  retrun true;
 }
 retrun false;
}
. Именно этот вариант может с небольшой вероятностью виснуть, попробуй придумать гарантированный вариант выбора n бит.

Добавлено через 1 минуту
Уменьшить метрику до нуля можно простым копирожанием.
Тарас, можете в двух словах описать алгоритм? В чем его суть?
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
15.01.2011, 08:38     Сокращение расстояния Хэмминга #7
C++
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
bool f(unsigned int *arr1, ansigned int *arr2, unsigned int l, unsigned int n)
{
 unsigned int size;
 unsigned int i, j;
 unsigned int metric;
 char *p1,*p2, buffer;
 unsigned int changed;
 ststic char masks[8]={0x01, 0x02, 0x04,0x08,0x10,0x20,0x40,0x80};
 size=l*sizeof(unsigned int); // Длина в байтах
 if (size/sizeof(unsigned int)==l) // Защита от переполнения
 {
  for (metric=0, p1=(char *)arr1+size-1, p2=(char *)arr2+size-1; p1>=(vhar *)arr1; --p1, --p2) // Перебиараем байты
  {
   buffer=*p1^p2; // Ксорим байты из обоих массивов. Операция побитовая в каждой позиции даёт 1, если биты операндов различаются и 0, если совпадают
   for (j=7; j>=0; --j)
   {
    if (buffer&masks[j]) // Операция И тоже побитовая, в результат попадают биты buffer, позиции которых совпадают с позициями единичных бит masks[j], но в masks[j] только один такой бит.
    {
     ++metric; // Нашли отличающиеся биты, учитываем это в значении метрики.
     if (metric==0) // Защита от переполнения.
     {
      return false;
     }
    }
   }
  }
  while (n!=0) // Для гарантии отбора именно n бит. Именно здесь возможно, но маловероятно повисание. Если убрать, то возможен отбор меньшего количества бит.
  {
   for (p1=(char *)arr1+size-1, p2=(char *)arr2+size-1; p1>=(vhar *)arr1; --p1, --p2) // Перебираем байты
   {
    buffer=*p1^p2; // Ксорим байты из обоих массивов. Операция побитовая в каждой позиции даёт 1, если биты операндов различаются и 0, если совпадают
    for (j=7; j>=0; --j)
    {
     if (buffer&masks[j]) // Операция И тоже побитовая, в результат попадают биты buffer, позиции которых совпадают с позициями единичных бит masks[j], но в masks[j] только один такой бит.
     {
      if ((rnd%metric)<n) // С заданной вероятностью отбираем для изменения найденные отличающиеся биты
      {     
       *p2=(p2&(!masks[j]))|(*p1&masks[j]);// Копирожаем бит. *p2&(!masks[j]) обнуляет бит в байте из второго массива в позиции, отмеченной единичным битом masks[j]. *p1&masks[j]) выделяет в байте из первого операнда бит, отмеченный единичным битом masks[j]. Операция | копирует в байт второго операнда единичный бит из байта первого операнда, отмеченный единичным битом masks[j]. Здесь как раз и была ошибка: & вместо | не сработает, то есть бит останется равен нулю. Если же в байте первого операнда в этой позиции ноль, то после p2&(!masks[j]) в этой позиции и так уже будет копия этого ноля, | не изменит результата.
       --metric; // Один бит мы скопирожали, метрика уменьшилась на единицу, учитываем этот факт.
       --n; // Один бит мы скопирожали, осталось скопирожать на 1 меньше, учитываем этот факт
      }
     }
    }
   }
  }
  retrun true;
 }
 retrun false;
}
Molotoff
1 / 1 / 0
Регистрация: 21.07.2009
Сообщений: 50
15.01.2011, 11:07  [ТС]     Сокращение расстояния Хэмминга #8
Ругается компилятор:
Error 54 error C2297: '^' : illegal, right operand has type 'char *'

на строку: buffer=*p1^p2;
lemegeton
 Аватар для lemegeton
2915 / 1344 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
15.01.2011, 11:53     Сокращение расстояния Хэмминга #9
А не, был устатый. Мой пример подходит под описание задачи. Вот улучшенная версия алгоритма с добавлением вычисляемых бит. Собственно, тот же ксор, что говорил Тарас.

C++
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
#include <cstdio>
#include <cstddef>
#include <cstdlib>
#include <ctime>
 
// подсчет расстояния Хемминга (количество разных бит)
// нужно только для того, чтобы показать, что алгоритм работает
size_t CountDefferentBits(const size_t a, const size_t b) {
  size_t different_bits = a ^ b;
  size_t result = 0;
  while (different_bits > 0) {
    result += (different_bits & 1);
    different_bits >>= 1;
  }
  return result;
}
 
// подсчет количества бит, установленных в 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;
}
 
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;
  }
 
  for (int i = 0; i < array_size; ++i) {
    // количество разных бит до уменьшения расстояния
    size_t  distance_before = CountDefferentBits(first_array[i], second_array[i]);
    printf("Before: DifferentBits(%d, %d) = %d; ",
            first_array[i], second_array[i], distance_before);
 
    // вся работа заключается в двух строках:
    // берем число с меньшим количеством установленных бит
    size_t &number_to_change = (CountBits(first_array[i]) <
                                CountBits(second_array[i])) ?
                                first_array[i] : second_array[i];
    // и добавляем к нему отсутствующие по сравнению со вторым числом биты
    number_to_change |= first_array[i] ^ second_array[i];
 
 
    // количество разных бит после уменьшения расстояния
    size_t  distance_after = CountDefferentBits(first_array[i], second_array[i]);
    printf("After: DifferentBits(%d, %d) = %d; ",
            first_array[i], second_array[i], distance_after);
    printf("Less by %d.\n", abs(distance_before-distance_after));
  }
 
  // удаление массивов
  delete [] first_array;
  delete [] second_array;
  return 0;
}
Molotoff
1 / 1 / 0
Регистрация: 21.07.2009
Сообщений: 50
15.01.2011, 12:04  [ТС]     Сокращение расстояния Хэмминга #10
Цитата Сообщение от lemegeton Посмотреть сообщение
А не, был устатый. Мой пример подходит под описание задачи. Вот улучшенная версия алгоритма с добавлением вычисляемых бит. Собственно, тот же ксор, что говорил Тарас.
По сути, то что делает ваш алгоритм можно реализовать простым присваиванием, если я не ошибаюсь
Тут задача несколько другая - должна получится функция, которая получает на входе два массива одинаковой длины и число бит, на которое один массив (некоторая двоичная последовательность, представленная массивом чисел) будет "приближен" к другому. А на выходе второй массив, число бит которого отличается уже меньше как раз на этот самый параметр.

Кстати для подсчета количества бит я нашел достаточно интересное решение в плане быстродействия:
C++
1
2
3
4
5
6
7
8
9
10
11
inline unsigned int Hamming_distance(unsigned int *arr, unsigned int arr_var)
{unsigned int v, res = 0;
        for (int i=0;i<arr_var;i++)
        {v = arr[i];
        v = (v & g21) + ((v >> 1) & g21);
        v = (v & g22) + ((v >> 2) & g22);
        v = (v + (v >> 4)) & g23;
        res += (v + (v >> 8) + (v >> 16) + (v >> 24)) & 0x3f;
        }
        return res;
}
lemegeton
 Аватар для lemegeton
2915 / 1344 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
15.01.2011, 13:28     Сокращение расстояния Хэмминга #11
Ну тогда так.
C++
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
70
71
72
73
74
#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++
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
70
71
72
73
74
75
#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;
}
Molotoff
1 / 1 / 0
Регистрация: 21.07.2009
Сообщений: 50
16.01.2011, 13:14  [ТС]     Сокращение расстояния Хэмминга #12
Цитата Сообщение от lemegeton Посмотреть сообщение
Ну тогда так.
В данном случае меняются одни и те же биты. А задача стоит, чтобы при вызове функции с одними и теми же параметрами результат был разный, т.е. менялись разные биты из отличающихся.

Добавлено через 15 часов 22 минуты
вообщем, в итоге вернулись к моей изначальной идее, видимо, более быстрый путь найти сложно
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline unsigned int DecreaseHammingDistance(unsigned int *arr1, unsigned int *arr2, unsigned int arr_var, unsigned int n)
{
    unsigned int changed_bits = 0;
    unsigned int element = rand() % arr_var;
    unsigned int bit_in_element = rand() % 0xFFFFFFFF;
    while (changed_bits < n)
    {
        if ((arr1[element] & (1 << bit_in_element)) !=
            (arr2[element] & (1 << bit_in_element))) 
        {
            arr2[element] ^= (1 << bit_in_element);
            changed_bits++;
        }
        element = rand() % arr_var;
        bit_in_element = rand() % 0xFFFFFFFF;
    }
return changed_bits;
}
Добавлено через 6 часов 27 минут
В любом случае спасибо за проявленное внимание и потраченное время
lemegeton
 Аватар для lemegeton
2915 / 1344 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
16.01.2011, 13:21     Сокращение расстояния Хэмминга #13
C++
1
2
3
unsigned int bit_in_element = rand() % 0xFFFFFFFF;
...
... (1 << bit_in_element);
Представляю сдвиг на 60 000 бит влево... Наверно, имелось в виду rand() % (sizeof(*arr1) * 8).
Molotoff
1 / 1 / 0
Регистрация: 21.07.2009
Сообщений: 50
16.01.2011, 13:25  [ТС]     Сокращение расстояния Хэмминга #14
конечно же, сдвиг тут максимально может быть на 32 осуществлен, ошибочка вышла
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.01.2011, 21:38     Сокращение расстояния Хэмминга
Еще ссылки по теме:

C++ код Хэмминга
C++ Коды Хэмминга С++
Последовательность Хэмминга C++
Как реализовать кодирование кода Хэмминга? C++
Код Хэмминга (Dev C++) C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
lemegeton
 Аватар для lemegeton
2915 / 1344 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
16.01.2011, 21:38     Сокращение расстояния Хэмминга #15
Хм. Так рандома можно и не дождаться. А что, если расстояния уже нулевые?
C++
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
70
71
72
73
74
75
76
#include <cstdio>
#include <cstddef>
#include <cstdlib>
#include <ctime>
 
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 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 += CountBits(first_array[i] ^ second_array[i]);
  return result;
}
 
inline size_t GetBit(size_t *array, size_t bit_number) {
  size_t this_bit = bit_number % (sizeof(*array) * 8);
  size_t this_element = bit_number / (sizeof(*array) * 8);
  return ((array[this_element] & (1 << this_bit)) == 0) ? 0 : 1;
}
 
inline void ChangeBit(size_t *array, size_t bit_number) {
  size_t this_bit = bit_number % (sizeof(*array) * 8);
  size_t this_element = bit_number / (sizeof(*array) * 8);
  array[this_element] ^= 1 << this_bit;
}
 
size_t DecreaseDistance(size_t *first_array, size_t *second_array,
                        size_t array_size, size_t decrease_by) {
  size_t current_distance = HammingDistance(first_array, second_array,
                                            array_size);
  if (decrease_by > current_distance)
    decrease_by = current_distance;
 
  for (int j = 0; j < decrease_by; ++j) {
    size_t different_bit_to_change = rand() % current_distance + 1;
    size_t bit_to_change = 0;
    for (int i = 0; i < different_bit_to_change; ++i)
      while (GetBit(first_array, bit_to_change) == GetBit(second_array, bit_to_change))
        ++bit_to_change;
    ChangeBit(second_array, bit_to_change);
    --current_distance;
  }
  return decrease_by;
}
 
int main(int argc, char *argv[]) {
  srand(time(NULL));
 
  size_t array_size = 10 + 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));
  DecreaseDistance(first_array, second_array, array_size, 100);
  printf("%d\n", HammingDistance(first_array, second_array, array_size));
 
  delete [] first_array;
  delete [] second_array;
  return 0;
}
Yandex
Объявления
16.01.2011, 21:38     Сокращение расстояния Хэмминга
Ответ Создать тему
Опции темы

Текущее время: 00:49. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru