Rgfl, gh=Q). В этом случае, также не нужны никакие разделители в силу однозначности декодирования."

При использовании этой схемы полуход может выглядеть следующим образом:

gh=Q

д) 12 битов на полуход

Еще более компактную запись можио получить, применив иной подход. Полуход однозначно определяется исходной клеткой и клеткой назначения. Поскольку всего клеток 64, для представления одной клетки достаточно 6 битов, так что всего для записи полухода требуется 12 битов. Этого достаточно для обычных ходов; однако для записи рокировки потребуется большее количество памяти.

Этот способ оказывается существенно лучше всех описанных ранее. Давайте теперь ненадолго отложим вопрос упаковки информации в сторону и приступим к следующей задаче, в которой рассмотрим, как можно создать вспомогательные структуры данных для хранения таких объектов нестандартного размера", с которыми не так-то легко работать и которые ухитряются пересекать границы байтов.

Кстати, основное достоинство такого представления вне компьютерного мира в том, что такая запись может быть легко выполнена на бумаге человеком, даже в условиях цейтнота. Оказывается, уменьшение длины записи от максимум 8 символов до максимум 4 вместе с определенной концептуальной простотой Ифает большую роль для пользователей (которых в шахматном мире называют игроками :)).

Задача 27. Форматы данных

и эффективность. Часть 2: игры с битами Сложность: 8

Пришло время рассмотреть более компактные и эффективно использующие память структуры данных, и поработать с кодом, оперирующим на битовом уровне.

Вопрос для профессионала

1. Для реализации решения д) второго вопроса задачи 26 вы решили создать класс, управляющий буфером битов. Реализуйте его максимально переносимо, с тем чтобы он корректно работал на любом ко.мпиляторе, соответствующем стандарту С+ + , независимо от платформы.

class BitBuffer { public:

... добавьте при необходимости другие функции... добавляет num битов, начиная с первого бита р. void Append С unsigned char* р, size t num ); Запрос количества используемых битов (изначально 0). si2e t SizeO const;

получает num битов, начиная с start-oro бита, и сохраняет результат, начиная с первого бита dst.

void Get(size t start, size t num, unsigned char* dst)

const;

private:

...дополнительные детали...

2. Нельзя ли хранить партию в шахматы с использованием менее чем 12 битов на полуход? Если можно - покажите, как. Если нет - поясните, почему.

Решение

BitBuffer, убийца битов

1. Для реализации решения д) второго вопроса задачи 26 вы решили создать класс, управляющий буфером битов. Реализуйте его максимально переносимо, с тем чтобы он корректно работал на любом компиляторе, соответствующем стандарту С++, независимо от платформы.

Для начала обратите внимание, что здесь нет упоминания о том, что байт состоит из 8 битов, которое было в предыдущей задаче - здесь это условие попросту неприменимо. Нам нужно решение, компилирующееся и корректно работающее в любой реализации С++, соответствующей стандарту, независимо от того, на какой платформе она работает.

Требуемый условием задачи интерфейс выглядит следующим образом.

class BitBuffer {

public:

void Append( unsigned char* p, size t num ); size t Size() const;

void Get(size t start, size t num, unsigned char* dst)

const;

...

Вы можете удивиться, почему интерфейс BitBuffer определен с использованием указателей на unsigned char. Во-первых, в стандарте С++ нет такой веши, как указатель на бит. Во-вторых, стандарт С++ гарантирует, что операции над беззнаковыми типами (включая unsigned char, unsigned short, unsigned int и unsigned long) не будут вызывать сообщения ко.мпилятора типа "Вы не инициализировали этот байт!" или "Эго некорректное значение!". Бьярн Страуструп пишет в [StroustrupOO]:

Беззнаковые целые типы идеально подходят для использования в качестве хранилища

для битового массива.

От компиляторов требуется предоставить юзможность рассматривать unsigned char (как и другие беззнаковые типы) как просто хранилище набора битов -- именно то, что нам и требуется. Имеются и другие подходы, но данный подход позволит нам получить навыки программирования работы с отдельными битами, что и является основной целью данной задачи.

Главный вопрос при реализации BitBuffer - какое внутреннее представление следует использовать? Я рассмотрю две основные альтернативы.

Попытка №1: использование unsigned char

Первая мысль - реализовать BitBuffer с использованием большого внутреннего блока unsigned char, и самостоятельно работать с отдельными битами при их размещении и выборке. Мы можем позволить классу BitBuffer иметь член типа unsigned char*, который указывал бы на буфер, но, тем не менее, давайте воспользуемся вектором vector<unsigned char>, чтобы не заботиться о вопросах распределения памяти.

Вам кажется, что все это звучит очень просто? Если да - значит, вы не пытались реализовать (и протестировать!) сказанное. Потратьте на это два-три часа, и вновь вернитесь к данной задаче? Я готов держать пари, что больше вы так не скажете.

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

И вот результат. Я не говорю, что он идеален, но он прошел все мои тесты, включая добавление одного и нескольких битов и некоторые граничные случаи. Обратите внимание, что эта версия исходного текста работает одновременно с блоками байтов - например, если мы используем 8-биговые байты и имеем смещение, равное 3 битам, то мы копируем первые три бита как отдельную единицу, и так же поступаем с последними 5 битами, получая 2 операции на байт. Для простоты я также требую, чтобы пользователь предоставлял буферы на байт большие, чем необходимо. Таким образом, я могу упростить свой код, позволив ему работать за концом буфера.

пример 27-1: реализация BitBuffer с использованием vector<unsigned char>. трудная,

скрупулезная работа. Брр...

class BitBuffer { public:

BitBufferC) : buf (0), size (0) { }

Добавление num битов, начиная с первого бита р.

void Append( unsigned char* p, size t num ) {

int bits = numeric limits<unsigned char>::digits;

первый байт назначения и смещение бита 180 Оптимизация и эффективность