Логические операции над многоразрядными числами

Алгоритмизация / Логические операции над многоразрядными числами

 

Рассмотрим выполнение логических операций И, ИЛИ, Исключающее ИЛИ и НЕ над многоразрядными числами.

Основная особенность выполнения побитовых логических операций над такими числами состоит в том, что каждое из них предварительно необходимо перевести в систему счисления с основанием, кратным 2, и только после этого выполнять логические операции. При необходимости результат можно снова перевести в десятичную систему счисления.

О переводе многоразрядных чисел в различные системы счисления подробно описано в этой статье.

Выполнение бинарной логической операции (то есть операции над двумя числами) осуществляется в следующем порядке:

  • Представить каждое число в 16-ричной системе счисления
  • Выровнять два числа по правому краю, поскольку побитовая операция будет осуществляться начиная с младшей 16-ричной цифры
  • Выполнить поразрядную логическую операцию над цифрами двух чисел
  • Сохранить цифру результата
  • Перейти к следующей цифре, двигаясь к началу пока не будут обработаны все цифры наиболее длинного числа
  • При необходимости перевести результат в десятичную систему счисления

Для выполнения унарной логической операции (в частности, логическое отрицание - НЕ) мы представляем обрабатываемое число в 16-ричной системе счисления и инвертируем каждую цифру числа. При необходимости переводим результат в десятичную систему счисления.

Реализация на 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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <iostream>
using namespace std;// Перевод цифры в символ
// Перевод цифры от 0 до F в символьное представление
char digittochar(int num)
{
  switch (num)
  {
  case 0: return '0';
  case 1: return '1';
  case 2: return '2';
  case 3: return '3';
  case 4: return '4';
  case 5: return '5';
  case 6: return '6';
  case 7: return '7';
  case 8: return '8';
  case 9: return '9';
  case 10: return 'A';
  case 11: return 'B';
  case 12: return 'C';
  case 13: return 'D';
  case 14: return 'E';
  case 15: return 'F';
  }
}
// Перевод символа от '0' до 'F' в цифру
int digittoint(char num)
{
  switch (num)
  {
  case '0'return 0;
  case '1'return 1;
  case '2'return 2;
  case '3'return 3;
  case '4'return 4;
  case '5'return 5;
  case '6'return 6;
  case '7'return 7;
  case '8'return 8;
  case '9'return 9;
  case 'A'return 10;
  case 'B'return 11;
  case 'C'return 12;
  case 'D'return 13;
  case 'E'return 14;
  case 'F'return 15;
  }
}
int dectox(char *a, int q, int p, char *c)
{
  int rest = 0; // остаток от деления
  char *s; // символьное десятичное представление частного a/p
  int lena = strlen(a);
  s = new char[lena];
  int flag = 0; // проверка на нулевой результат в частном
  for (int i = 0; i < lena; i++)
  {
    int dig = a[i] > 0 ? digittoint(a[i]) : 0;
    int num = rest*q + dig; // делимое на текущем шаге
    s[i] = digittochar(num / p); // следующий разряд частного
    rest = num % p; // остаток от деления
    if (s[i] != '0') flag = 1; // в случае ненулевого результата установить флаг
  }
  if (flag == 0) // частное равно 0, базовый случай рекурсии
  {
    c[0] = digittochar(rest); return 1; // запись старшего разряда результата
  }
  s[lena] = '\0'// заканчиваем полученную строку результата
  int k = dectox(s, q, p, c); // рекурсивный вызов для следующего разряда
  c[k++] = digittochar(rest); // заполнение текущего разряда результата
  return k;
}
// Функция ИЛИ
char * or (char *a, char *b) {
  int lena = strlen(a); // количество разрядов первого числа
  int lenb = strlen(b); // количество разрядов второго числа
  char *c;
  int k = lena > lenb ? lena : lenb; // количество разрядов результата
  c = new char[k + 1];
  c[k] = '\0'// завершающий нуль-символ результата
  k--;
  for (int i = lena - 1, j = lenb - 1; i >= 0 || j >= 0; i--, j--) {
    char dig1 = i < 0 ? 0 : digittoint(a[i]); // если разряд отсутствует, взять 0
    char dig2 = j < 0 ? 0 : digittoint(b[j]); // иначе преобразовать символ в цифру
    char dig = dig1 | dig2; // операция побитового ИЛИ над цифрами разрядов
    c[k] = digittochar(dig);
    k--; // перейти к следующему разряду
  }
  return c;
}

// Функция И
char * and(char *a, char *b) 
{
  int lena = strlen(a); // количество разрядов первого числа
  int lenb = strlen(b); // количество разрядов второго числа
  char *c;
  int k = lena > lenb ? lena : lenb; // количество разрядов результата
  c = new char[k + 1];
  c[k] = '\0'// завершающий нуль-символ результата
  k--;
  for (int i = lena - 1, j = lenb - 1; i >= 0 || j >= 0; i--, j--)
  {
    char dig1 = i < 0 ? 0 : digittoint(a[i]); // если разряд отсутствует, взять 0
    char dig2 = j < 0 ? 0 : digittoint(b[j]); // иначе преобразовать символ в цифру
    char dig = dig1 & dig2; // операция побитового И над цифрами разрядов
    c[k] = digittochar(dig);
    k--; // перейти к следующему разряду
  }
  return c;
}
// Функция Исключающее ИЛИ
char * xor(char *a, char *b) 
{
  int lena = strlen(a); // количество разрядов первого числа
  int lenb = strlen(b); // количество разрядов второго числа
  char *c;
  int k = lena > lenb ? lena : lenb; // количество разрядов результата
  c = new char[k + 1];
  c[k] = '\0'// завершающий нуль-символ результата
  k--;
  for (int i = lena - 1, j = lenb - 1; i >= 0 || j >= 0; i--, j--)
  {
    char dig1 = i < 0 ? 0 : digittoint(a[i]); // если разряд отсутствует, взять 0
    char dig2 = j < 0 ? 0 : digittoint(b[j]); // иначе преобразовать символ в цифру
    char dig = dig1 ^ dig2; // операция побитового исключающего ИЛИ над цифрами разрядов
    c[k] = digittochar(dig);
    k--; // перейти к следующему разряду
  }
  return c;
}
// Функция НЕ
char * not(char *a) 
{
  int lena = strlen(a); // количество разрядов первого числа
  char *c;
  int k = lena; // количество разрядов результата
  c = new char[k + 1];
  c[k] = '\0'// завершающий нуль-символ результата
  k--;
  for (int i = lena - 1; i >= 0; i--)
  {
    char dig1 = i < 0 ? 0 : digittoint(a[i]); // если разряд отсутствует, взять 0
    char dig = (~dig1) & 0x0F; // операция побитового НЕ над цифрами разрядов
    c[k] = digittochar(dig);
    k--; // перейти к следующему разряду
  }
  return c;
}
int main() 
{
  char a[1000] = { 0 };
  char b[1000] = { 0 };
  char ahex[1000] = { 0 };
  char bhex[1000] = { 0 };
  char *rhex;
  char r[1000] = { 0 };
  cout << "a = ";
  cin.getline(a, 1000);
  cout << "b = ";
  cin.getline(b, 1000);
  dectox(a, 10, 16, ahex);
  dectox(b, 10, 16, bhex);
  cout << "ahex = " << ahex << "h" << endl;
  cout << "bhex = " << bhex << "h" << endl;
  rhex = and (ahex, bhex);
  dectox(rhex, 16, 10, r);
  cout << a << " & " << b << " = " << rhex << "h = " << r << endl;
  rhex = or (ahex, bhex);
  dectox(rhex, 16, 10, r);
  cout << a << " | " << b << " = " << rhex << "h = " << r << endl;
  rhex = xor (ahex, bhex);
  dectox(rhex, 16, 10, r);
  cout << a << " ^ " << b << " = " << rhex << "h = " << r << endl;
  rhex = not (ahex);
  dectox(rhex, 16, 10, r);
  cout << "~" << a << " = ~" << ahex << "h = " << rhex << "h = " << r << endl;
  cin.get();
  return 0;
}


Результат выполнения
Результат логических операций над многоразрядными числами


Назад: Алгоритмизация

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *