Задача о цепочке побитовых операций

Исходная величина A представляет собой натуральное число. Разрешены следующие операции над двоичным представлением числа A:

• shl(a, n) - сдвиг числа на n бит влево, справа дописывается нулевой бит;
• shr(a, n) - сдвиг числа на n бит вправо, слева дописывается нулевой бит;
• set0(a, n) - установка бита номер n в ноль, нумерация битов выполняется справа налево начиная с нуля;
• set1(a, n) - установка бита номер n в единицу, нумерация битов выполняется справа налево начиная с нуля.

Сформировать наиболее короткую цепочку операций (не более пяти), переводящую десятичное число A в число B.

На несложной олимпиаде по информатике / программированию за такое можно назначить, например, 5 баллов при условии, что задача решена не более, чем за 3 операции, 4 балла за 4 операции, 3 балла за 5 операций, иначе 2 балла за любое решение. Задачу можно решить только через операции set1 и set0, но нужно контролировать, чтобы исходное число отличалось от целевого не менее, чем на 6 бит.

Так как решение не обязано быть единственным, цепочки операций надо проверять тестовой программой, вот она для консоли Visual C++, запускалась в Studio 2019 и 2015.

#include <cstdio>
#include <windows.h>
using namespace std;

void printBits (size_t const size, void const* const ptr) {
 //assumes little endian
 unsigned char* b = (unsigned char*)ptr;
 unsigned char byte;
 int i, j;
 for (i = size - 1; i >= 0; i--) {
  for (j = 7; j >= 0; j--) {
   byte = (b[i] >> j) & 1;
   printf("%u", byte);
  }
 }
 printf("\n");
}

int shl(int a, int n) { return a << n; }
int shr(int a, int n) { return a >> n; }
int set0(int a, int n) { return (a &= ~(1 << n)); }
int set1(int a, int n) { return (a |= 1 << n); }

int main() {
 int a = 74; //введи исходное число
 printBits(sizeof(a), &a);

 //действия по одному и печать очередного результата по битам
 a = shr(a, 1);
 printBits(sizeof(a), &a);

 a = set1(a, 7);
 printBits(sizeof(a), &a);

 a = set0(a, 0);
 printBits(sizeof(a), &a);

 //окончательный итог
 printf("\n%d (%02X)", a, a);

 system("pause");
 return 0;
}

Метод printBits печатает число по битам (для little endian представления), не пользуясь bitset. Побитовые действия на C++ есть также в этой заметке.

Любопытно было бы также написать "решалку" таких преобразований методами динамического программирования.

14.12.2019, 11:15 [1237 просмотров]