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

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

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

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