Задача о цепочке побитовых операций
Исходная величина 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 [1238 просмотров]