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

@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. Почему нужно оптимизировать по скорости выполнения - эта операция будет повторяться много раз, что скажется на общем времени выполнения программы.

@taras atavin · 14.01.2011, 10:52

Это: метрика Хэминга в википедии?

@Molotoff · 14.01.2011, 10:56 **[ТС]**

да, да, именно о нем и идет речь, покороче пример приведу
x1 11010001
x2 10100101
здесь расстояние Хэмминга равно 4-м, алгоритм должен менять x2, например, так
x2 10000101
или так
x2 10010101

@taras atavin · 14.01.2011, 12:29

Ксоркой их, единицы в результате отметят позиции..

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 · 14.01.2011, 19:36

Уменьшить метрику между числами можно с помощью простейших логических операций.

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 · 15.01.2011, 08:13 **[ТС]**

Сообщение от 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 · 15.01.2011, 08:38

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 · 15.01.2011, 11:07 **[ТС]**

Ругается компилятор:
Error 54 error C2297: '^' : illegal, right operand has type 'char *'

на строку: buffer=*p1^p2;

@lemegeton · 15.01.2011, 11:53

А не, был устатый. Мой пример подходит под описание задачи. Вот улучшенная версия алгоритма с добавлением вычисляемых бит. Собственно, тот же ксор, что говорил Тарас.

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 · 15.01.2011, 12:04 **[ТС]**

Сообщение от 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 · 15.01.2011, 13:28

Ну тогда так.

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 · 16.01.2011, 13:14 **[ТС]**

Сообщение от 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 · 16.01.2011, 13:21

C++
1
2
3
unsigned int bit_in_element = rand() % 0xFFFFFFFF;
...
... (1 << bit_in_element);

Представляю сдвиг на 60 000 бит влево... Наверно, имелось в виду rand() % (sizeof(*arr1) * 8).

@Molotoff · 16.01.2011, 13:25 **[ТС]**

конечно же, сдвиг тут максимально может быть на 32 осуществлен, ошибочка вышла

@lemegeton · 16.01.2011, 21:38

Хм. Так рандома можно и не дождаться. А что, если расстояния уже нулевые?

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;
}

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

@Molotoff 1 / 1 / 0 Регистрация: 21.07.2009 Сообщений: 50

	Сокращение расстояния Хэмминга 14.01.2011, 10:47. Показов 4596. Ответов 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

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	14.01.2011, 10:52
	Это: метрика Хэминга в википедии? 0

@Molotoff 1 / 1 / 0 Регистрация: 21.07.2009 Сообщений: 50
	14.01.2011, 10:56 [ТС]
	да, да, именно о нем и идет речь, покороче пример приведу x1 11010001 x2 10100101 здесь расстояние Хэмминга равно 4-м, алгоритм должен менять x2, например, так x2 10000101 или так x2 10010101 0

@Molotoff 1 / 1 / 0 Регистрация: 21.07.2009 Сообщений: 50
	15.01.2011, 11:07 [ТС]
	Ругается компилятор: Error 54 error C2297: '^' : illegal, right operand has type 'char ' на строку: buffer=p1^p2; 0

@Molotoff 1 / 1 / 0 Регистрация: 21.07.2009 Сообщений: 50
	16.01.2011, 13:25 [ТС]
	конечно же, сдвиг тут максимально может быть на 32 осуществлен, ошибочка вышла 0