int dst = size / bits; int off = size % bits;

whileC buf .size() < (size +num) / bits + 1 )

buf .push back( 0 ); for( int i = 0; i < (num+bits-l)/bits; ++i ) {

unsigned char mask = FirstBits(num - bits*i);

buf [dst+i] 1= (*(p+i) & mask) » off;

if( off > 0 )

buf [dst+i+l] = (*(p+i) & mask)«(bits-off);

size += num;

Запрос количества используемых битов (изначально ноль).

size t SizeC) const { return size ;

получение num битов, начиная с start-го бита

(нумерация начинается с 0), и сохранение результата

начиная с первого бита dst. Буфер, на который

указывает dst, должен быть по крайней мере на один

байт больше, чем минимально необходимый для хранения

num битов.

void GetCsize t start, si2e t num, unsigned char* dst) const {

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

первый исходный байт и смещение бита int src = start / bits; int off = start % bits;

for( int i = 0; i < (num+bits~l)/bits; ++i ) {

*(dst+i) = buf.....[src+i] « off;

if( off > 0 )

*(dst+i) 1= buf [src+i+l] » (bits - off);

private:

vector<unsigned char> buf ; size t size ; in bi ts

Создание маски, в которой первые п битов равны 1, а остальные - 0.

unsigned char FirstBits( size t n ) {

int num=min(n,numeric limits<unsigned char>::digits); unsigned char b = 0; while( num-- > 0 ) b = (b » 1) I

(l«(numeric limits<unsigned char>: :digits-l)) ; return b;

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

" Вероятно, разобраться в приведенном исходном тексте (а кое-где даже улучшить его) вам поможет знакомство с книгой [Warren03]. - Прим. ред.

ее наличие. Если наличие ошибки подтвердится - прошу вас, отправьте мне сообщение об ошибке вместе с вашей тестовой профаммой, демонстрирующей наличие ошибки.)

Попытка №2: использование стандартного контейнера упакованных битов

Вторая идея заключается в том, чтобы обратить внимание на то, что стандартная библиотека уже содержит два контейнера для хранения битов: bitset и vector<bool>. Для наших целей bitset - плохой вариант, поскольку bitset<N> имеет фиксированную длину N, а мы должны работать с потоками битов переменной длины. Не получается... Зато vector<bool>, несмотря на все его недостатки в данном случае оказывается тем, "что доктор прописал". (Конечно, стандарт не требует, ттобы реализация vector<bool> использовала упакованные биты, а только поощряет это. Тем не менее, большинство реализаций именно так и поступают.)

Самое главное, что я могу сказать о приведенном далее исходном тексте, - это то, что исходный текст примера 27-2 был совершенно корректен при первом его написании.

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

Пример 27-2: Реализация BitBuffer с использованием

vector<bool>.

class BitBuffer { public:

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

void AppendC unsigned char* p, size t num ) {

int bits = numeric„lim1ts<unsigned char>::digits; for( int i =0; i < num; ++i ) {

buf„.push back( p & (1 « (bits-1 - i%bits)) ); if( (i+1) % bits == 0 ) ++p;

Запрос количества используемых битов (изначально ноль). size t SizeO const { return buf .sizeO;

получение num битов, начиная с start-го бита

(нумерация начинается с 0), и сохранение результата

начиная с первого бита dst.

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

int bits = numeric limits<unsigned char>::digits; ••*dst = 0;

for( int i = 0; i < num; ++i ) {

*dst i= unsigned char(buf [start+i])

« (bits-1 - i%bits); if( (i+1) % bits == 0 ) *++dst = 0;

private:

Более подробно вопрос о vector<bOOl> рассмотрен в [Sutter021 (задача 1.13 в русском издании). - Прим. ред.

vector<bool> buf ;

Вас не должно удивлять, что написать эту версию было существенно проще, чем пример 27-1. Здесь вместо разработки собственного кода для работы с битами используется уже готовый, размер текста оказывается примерно в два раза меньше, чем в предыдущей версии, и как результат - непропорционально малое количество ошибок. Такой код, кроме того, яснее и понятнее; в частности, теперь мне не требуется, чтобы вызывающая программа выделяла дополнительную память только для того, чтобы мой код был проще, как это было в первой версии исходного текста.

Я подозреваю, что оба решения (в особенности первое) можно было бы улучшить - в частности, в исходном тексте могут быть не замеченные мною ошибки, текст может быть упрошен способом, о котором я не подумал, - но я думаю, что оба решения близки к идеалу как в плане корректности, так и в плане стиля.

Плотная упаковка

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

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

Да. но если вы захотите использовать это представление в коде, вам потребуется специальный битовый контейнер вроде BitBuffer. Например, имеется три способа.

Достичь упаковки полухода в 10 битов достаточно просто. Нам достаточно указать, какая именно фигура (а для каждого полухода их не более 16) и в какую клетку (которых на доске 64) ходит. Цвет фигуры определяется номером полухода. Перенумеровав фигуры (например, в порядке их размещения по горизонталям, а в пределах горизонтали - по вертикалям) и клетки доски, мы получаем, что для указания фигуры нам надо 4 бита, а для указания клетки, в которую она ходит, - 6 битов; итого достаточно 10 битов, чтобы однозначно определить полуход.

Можно ли улучшить этот результат? Судите сами: мы можем закодировать все клетки доски в качестве целевых клеток полухода, в то время как правила игры позволяют быть таковыми только малому количеству клеток. Таким образом, в нашем представлении явно имеется избыгочность. Аналогично, наше представление позволяет записать ход любой фигуры в заданную клетку, в то время как такой ход могут сделать далеко не все фигуры, причем некоторые фигуры в принципе не могут попасть в некоторые клетки. Так что, например, можно использовать для кодирования клетки 6 битов, а затем выяснить, какие фигуры могут пойти в данную клетку, и использовать от О до 4 битов для указания одной из них. Если таких фигур мало, нам не потребуются все 4 бита. При декодировании из анализа текущей позиции мы знаем, какое количество фигур может попасть в целевую клетку, а значит, нам известно, сколько именно битов из входного потока требуется запросить, чтобы декодировать полуход.

Мы можем закодировать полуход с использованием не менее О и не более 8 битов следующим образом: сначала надо разработать способ упорядочения разрешенных шагов; например, мы можем упорядочить фигуры описанным выше способом, в соответствии с занимаемыми ими позициями, а для каждой фигуры - упорядочить возможные ходы с использованием того же принципа, что и для фигур. Затем номер фактического хода записывается с использованием минимально необходимого количества битов. Например, начальная позиция имеет 20 возможных ходов; для представления их в бинарном виде требуется ceil(log2(20)) = 5 битов.

В результате минимальное количество битов, необходимое для записи полухода, равно О - если имеется только один возможный, вынужденный ход. Но сколько би-