С.Б. Липпман, Ж. Лажойе - Язык программирования С++ Вводный курс (1114944), страница 29
Текст из файла (страница 29)
При работе с битовыми векторами такжеС++ для начинающихможно применять подход, заимствованный из С, – использовать для представлениятакого вектора объект встроенного целого типа, обычно unsigned int, или класс bitsetстандартной библиотеки С++. Этот класс инкапсулирует семантику вектора,предоставляя операции для манипулирования отдельными битами.
Кроме того, онпозволяет ответить на вопросы типа: есть ли “взведенные” биты (со значением 1) ввекторе? Сколько битов “взведено”?В общем случае предпочтительнее пользоваться классом bitset, однако, пониманиеработы с битовыми векторами на уровне встроенных типов данных очень полезно. В этомразделе мы рассмотрим применение встроенных типов для представления битовыхвекторов, а в следующем – класс bitset.При использовании встроенных типов для представления битовых векторов можнопользоваться как знаковыми, так и беззнаковыми целыми типами, но мы настоятельносоветуем пользоваться беззнаковыми: поведение побитовых операторов со знаковымитипами может различаться в разных реализациях компиляторов.Побитовое НЕ (~) меняет значение каждого бита операнда.
Бит, установленный в 1,меняет значение на 0 и наоборот.Операторы сдвига (<<, >>) сдвигают биты в левом операнде на указанное правымоперандом количество позиций. “Выталкиваемые наружу” биты пропадают,освобождающиеся биты (справа для сдвига влево, слева для сдвига вправо) заполняютсянулями. Однако нужно иметь в виду, что для сдвига вправо заполнение левых битовнулями гарантируется только для беззнакового операнда, для знакового в некоторыхреализациях возможно заполнение значением знакового (самого левого) бита.Побитовое И (&) применяет операцию И ко всем битам своих операндов. Каждый битлевого операнда сравнивается с битом правого, находящимся в той же позиции.
Если обабита равны 1, то бит в данной позиции получает значение 1, в любом другом случае – 0.(Побитовое И (&) не надо путать с логическим И (&&),но, к сожалению, каждыйпрограммист хоть раз в жизни совершал подобную ошибку.)Побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ (^) сравнивает биты операндов. Соответствующийбит результата равен 1, если операнды различны (один равен 0, а другой 1).
Если же обаоперанда равны, результата равен 0.Побитовое ИЛИ (|) применяет операцию логического сложения к каждому битуоперандов. Бит в позиции результата получает значение 1, если хотя бы один изсоответствующих битов операндов равен 1, и 0, если биты обоих операндов равны 0.(Побитовое ИЛИ не нужно смешивать с логическим ИЛИ.)Рассмотрим простой пример. Пусть у нас есть класс из 30 студентов. Каждую неделюпреподаватель проводит зачет, результат которого – сдал/не сдал. Итоги можнопредставить в виде битового вектора.
(Заметим, что нумерация битов начинается с нуля,первый бит на самом деле является вторым по счету. Однако для удобства мы не будемиспользовать нулевой бит; таким образом, студенту номер 1 соответствует бит номер 1. Вконце концов, наш преподаватель – не специалист в области программирования.)unsigned int quiz1 = 0;Нам нужно иметь возможность менять значение каждого бита и проверять это значение.Предположим, студент 27 сдал зачет. Бит 27 необходимо выставить в 1, не меняязначения других битов.
Это можно сделать за два шага. Сначала нужно начать с числа,содержащего 1 в 27-м бите и 0 в остальных. Для этого используем операцию сдвига:161С++ для начинающих1621 << 27;Применив побитовую операцию ИЛИ к переменной quiz1 и нашей константе, получимнужный результат: значение 27-й бита станет равным значение 1, а другие битыостанутся неизменными.quiz1 |= 1<<27;Теперь представим себе, что преподаватель перепроверил результаты теста и выяснил,что студент 27 зачет не сдал.
Теперь нужно присвоить нуль 27-му биту, не трогаяостальных. Сначала применим побитовое НЕ к предыдущей константе и получим число,в котором все биты, кроме 27-го, равны 1:~(1<<27 );Теперь побитово умножим (И) эту константу на quiz1 и получим нужный результат: 0 в27-м бите и неизменные значения остальных.quiz1 &= ~(1<<27);Как проверить значение того же 27-го бита? Побитовое И дает true, если 27-й бит равен1, и false, если 0:bool hasPassed = quiz1 & (1<<27);При использовании побитовых операций подобным образом очень легко допуститьошибку. Поэтому чаще всего такие операции инкапсулируются в макросы препроцессораinline boo1 bit_on (unsigned int ui, int{return u1 & ( 1 << pos );pos)или встроенные функции:}enum students { Danny = 1, Jeffrey, Ethan, Zev, Ebie, // ...AnnaP = 26, AnnaL = 27 };const int student_size = 27;// наш битовый вектор начинается с 1boo1 has_passed_quiz[ student_size+l ];for ( int index = 1; index <= student_size; ++-index )Вот пример использования:has_passed_quiz[ index ] = bit_on( quiz1, index );Раз уж мы начали инкапсулировать действия с битовым вектором в функции, следующимшагом нужно создать класс.
Стандартная библиотека С++ включает такой класс bitset,его использование описано ниже.С++ для начинающих163Упражнение 4.12Даны два целых числа:unsigned int ui1 = 3, ui2 = 7;Каков результат следующих выражений?(a) ui1 & ui2 (c) uil | ui2(b) ui1 && ui2 (d) uil || ui2Упражнение 4.13Используя пример функции bit_on(), создайте функции bit_turn_on() (выставляетбит в 1), bit_turn_off() (сбрасывает бит в 0), flip_bit() (меняет значение напротивоположное) и bit_off() (возвращает true, если бит равен 0). Напишитепрограмму, использующую ваши функции.Упражнение 4.14В чем недостаток функций из предыдущего упражнения, использующих тип unsignedint? Их реализацию можно улучшить, используя определение типа с помощью typedefили механизм функций-шаблонов.
Перепишите функцию bit_on(),применив сначалаtypedef, а затем механизм шаблонов.4.12. Класс bitsetТаблица 4.4. Операции с классом bitsetОперацияЗначениеИспользованиеtest(pos)Бит pos равен 1?a.test(4)any()Хотя бы один бит равен 1?a.any()none()Ни один бит не равен 1?a.none()count()Количество битов, равных 1a.count()size()Общее количество битовa.size()[pos]Доступ к биту posa[4]flip()Изменить значения всехa.flip()flip(pos)Изменить значение бита posa.flip(4)set()Выставить все биты в 1a.set()set(pos)Выставить бит pos в 1a.set(4)reset()Выставить все биты в 0a.reset()reset(pos)Выставить бит pos в 0a.reset(4)Как мы уже говорили, необходимость создавать сложные выражения для манипуляциибитовыми векторами затрудняет использование встроенных типов данных.
Класс bitsetупрощает работу с битовым вектором. Вот какое выражение нам приходилось писать впредыдущем разделе для того, чтобы “взвести” 27-й бит:С++ для начинающихquiz1 |= 1<<27;При использовании bitset то же самое мы можем сделать двумя способами:quiz1[27] = 1;илиquiz1.set(27);(В нашем примере мы не используем нулевой бит, чтобы сохранить “естественную”нумерацию.
На самом деле, нумерация битов начинается с 0.)Для использования класса bitset необходимо включить заголовочный файл:#include <bitset>Объект типа bitset может быть объявлен тремя способами. В определении поумолчанию мы просто указываем размер битового вектора:bitset<32> bitvec;Это определение задает объект bitset, содержащий 32 бита с номерами от 0 до 31. Всебиты инициализируются нулем. С помощью функции any() можно проверить, есть ли ввекторе единичные биты. Эта функция возвращает true, если хотя бы один бит отличенот нуля. Например:bool is_set = bitvec.any();Переменная is_set получит значение false, так как объект bitset по умолчаниюинициализируется нулями.
Парная функция none() возвращает true, если все битыравны нулю:bool is_not_set = bitvec.none();Изменить значение отдельного бита можно двумя способами: воспользовавшисьфункциями set() и reset() или индексом. Так, следующий цикл выставляет в 1for ( int index=0; index<32; ++index )if ( index % 2 == 0 )каждый четный бит:bitvec[ index ] = 1;Аналогично существует два способа проверки значений каждого бита – с помощьюфункции test() и с помощью индекса.
Функция () возвращает true, еслиif ( bitvec.test( 0 ))соответствующий бит равен 1, и false в противном случае. Например:// присваивание bitvec[0]=1 сработало!;164С++ для начинающих165cout << "bitvec: включенные биты:\n\t";for ( int index = 0; index < 32; ++-index )if ( bitvec[ index ] )cout << index << " ";Значения битов с помощью индекса проверяются таким образом:cout << endl;bitvec.reset(0);Следующая пара операторов демонстрирует сброс первого бита двумя способами:bitvec[0] = 0;Функции set() и reset() могут применяться ко всему битовому вектору в целом. В// сброс всех битовbitvec.reset();if (bitvec.none() != true)// что-то не сработало// установить в 1 все биты вектора bitvecif ( bitvec.any() != true )этом случае они должны быть вызваны без параметра.
Например:// что-то опять не сработалоbitvec.f1ip( 0 );bitvec[0].flip();// меняет значение первого бита// тоже меняет значение первого битаФункция flip() меняет значение отдельного бита или всего битового вектора:bitvec.flip();// меняет значения всех битовСуществуют еще два способа определить объект типа bitset. Оба они дают возможностьпроинициализировать объект определенным набором нулей и единиц.
Первый способ –явно задать целое беззнаковое число как аргумент конструктору. Начальные N позицийбитового вектора получат значения соответствующих двоичных разрядов аргумента.Например:bitset< 32 > bitvec2( Oxffff );инициализирует bitvec2 следующим набором значений:00000000000000001111111111111111В результате определенияС++ для начинающихbitset< 32 > bitvec3( 012 );у bitvec3 окажутся ненулевыми биты на местах 1 и 3:00000000000000000000000000001010В качестве аргумента конструктору может быть передано и строковое значение,состоящее из нулей и единиц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
