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

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

Новые блоги и статьи Все статьи Все блоги /
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .

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

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