Создание битовых множеств

При создании битового множества указывается его размер (как аргумент шаблона). Можно инициализировать bitset строкой, состоящей из нулей и единиц:

bitset<32> bset1;

bitset<8> bset2(string ( "01011011"));

Вторая форма конструктора объявлена как explicit, с аргументом типа string, поэтому приходится делать явное преобразование литеральной строки в стандартную.

Действия над bitset

Порядок следования элементов в bitset с точки зрения индексации является обратным расположению нулей и единиц в инициализирующей строке. (Это соответствует семантике двоичных чисел — слева стоит самый старший бит, которому обычно приписывают наибольший номер.)

Функция-элемент test() позволяет проверить состояние бита с указанным индексом. Функция апу() возвращает true, если хотя бы один из битов множества установлен.

Функции set () и reset () служат соответственно для установки и сброса битов множества. При указании индекса в качестве аргумента функция устанавливает/сбрасывает соответствующий бит; при вызове функции без аргумента устанавливаются/сбрасываются все биты множества.

Функция flip () инвертирует состояние указанного бита или всех битов множества.

К битовым множествам можно применять обычные логические поразрядные операции и сдвиги (~, &, |, ^, <<, >>).

Для битовых множеств определена операция передачи в поток (<<).

Структуры и объединения

Структуры

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

Структуры и объединения – это один из примеров составных типов данных, называемых агрегатными типами, или просто агрегатами. Структурные переменные, или просто структуры, – это объединение одной или более переменных, возможно, разных типов, в одну область памяти, имеющую одно имя. Отдельные составные части структурной переменной называются полями.

Как и любая переменная, структурная переменная должна описываться. Это описание состоит из двух шагов:

1) задание шаблона структуры;

2) собственно описание структурной переменной.

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

 

struct имя_шаблона {тип_1 имя_поля_1;

 

                тип_2 имя_поля_2;

 

                •••

 

                тип_N имя_поля_N;};

 

где имя_шаблона – имя шаблона, удовлетворяющее правилам задания идентификаторов языка C/C++.

Рассмотрим структуру «аэропорт», включающую сведения об аэропортах, таких как код ИАТА[35] и длина взлетно-посадочной полосы:

struct airport {

char code[3];

intlen;

};

Далее можно объявить несколько переменных структурного типа:

airport Simferopol = {"SIP", 3701};

airport Kursk = {"URS", 2500};

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

Simferopol Kursk                 SIP 3701 URS 2500         … байты…                             … байты…

Доступ к элементам структуры осуществляется при помощи операции доступа (операции точки). Например, для вывода длины взлетно-посадочной полосы симферопольского аэропорта можно воспользоваться:

cout << Simferopol.len;

ВАЖНО: Для доступа к полям, являющимися указателями, применяется ->вместо операции точки.

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

struct myStr {

     int a:1;

     int b:2;

};

Поле a занимает один бит, поле b – два.

Объединения

Объединения (union) подобны структурам в том, что содержат поля различных типов, но помещаемые в одно и то же место памяти. Фактически объединения – это доступ к одному и тому же месту памяти, но по-разному.

ВАЖНО: Размер unionравен размеру самого большого из его полей. Фактически, unionесть смысл применять лишь в том случае, когда из нескольких описанных объектов будет использоваться лишь один, либо если необходимо получать доступ к отдельным байтам, словам и т.д. переменной.

Например, если требуется определить, какая применяется модель хранения числовых данных big endianили little endian–т.е. начинается со старших байт или младших, то это можно сделать с помощью следующей программы.

Задача №182.  Порядок байтов

Определите, какой порядок байт – big endian или little endian применяется на устройстве.

Решение

#include <iostream>

using namespace std;

 

union {

unsigned short sh;

unsigned char bt[sizeof(short)];

} u;

 

int main(){

if ( sizeof(short) != 2 ){

   cout<< "Тип short занимает более 2 байт памяти.";

   return 1;

}

u.sh = 0x0105;

cout <<( u.bt[0] == 1 ? "Big" : "Little") << " endian";

 

return 0;

}

Число sh типа short и массив однобайтных беззнаковых целых bt размещаются по одному и тому же адресу. Для big endian байты будут расположены в порядке 0x01, 0x05, а для littleendian–наоборот.

Задача №183.  Расчет маски сети

Василий Васильевич Пупкин отныне работает в школе системным администратором. Но поскольку он ничем кроме олимпиадного программирования никогда не занимался, то понятия не имеет об администрировании сетей. Бывшему однокласснику Васи – Диме Дудкину часто приходится выручать товарища. Помогите Диме написать программу, которая сможет считать сетевые маски для Васи.

Объяснение формул расчета сетей

IP адрес состоит из 32 битов, которые поделены на 4 части по 8 бит соответственно (эти части называются октетами).

Примеры IP адресов:

178.68.128.168 = 10110010.01000100.10000000.10101000

217.20.147.94 = 11011001.00010100.10010011.01011110

Часть этих 32 битов часть относится к адресу сети, в которой находится этот компьютер (хост), а вторая часть – к адресу компьютера в сети. Чтобы узнать, сколько битов относится к адресу сети, а сколько – к адресу хоста, надо воспользоваться маской сети.

Маска сети тоже состоит из 32 битов, но в отличие от IP адреса, в маске единицы и нули не могут перемешиваться.

Примеры масок сети:

255.255.255.0 = 11111111.11111111.11111111.00000000

255.255.240.0 = 11111111.11111111.11110000.00000000

255.255.255.128 = 11111111.11111111.11111111.10000000

Префикс маски

Часто маска сети записывается в виде короткого префикса. Число в префиксе обозначает количество бит относящихся к адресу сети.

/16 = 11111111.11111111.00000000.00000000 = 255.255.0.0

/26 = 11111111.11111111.11111111.11000000 = 255.255.255.192

Та часть маски, где биты нулевые, в IP-адресе соответствует адресу хоста, а где единичные – адресу сети. Например, для IP-адреса

192.168.100.12= 11000000. 10101000.01100100.00001100 и маски подсети

255.255.255.0 = 11111111.11111111.11111111.00000000

Первые 3 байта в примере являются адресом сети, а последний – адресом хоста. В сокращенной форме с сетевым префиксом это записывается так: 192.168.100.12/24

Таким образом, в этой сети будут доступны адреса от 192.168.100.0 до 192.168.100.255. Будем считать, что эти два адреса для хостов использовать нельзя[36].

Входные данные

IP-адрес Васиного компьютера с сетевым префиксом.

Выходные данные

В трёх строках последовательно маска подсети, минимальный адрес хоста, максимальный адрес хоста (всё в десятичной форме).

Пример

Ввод	Вывод
188.191.23.200/28	255.255.255.240 188.191.23.193 188.191.23.207
188.191.24.3/32	255.255.255.255 188.191.24.3 188.191.24.3

Пояснение к примеру №2: Если префикс маски равен 32, то в сети кроме Васиного компьютера других хостов быть не может.

Решение

Используем union для удобства работы с отдельными байтами IP-адреса и сетевой маски.

#include <iostream>

using namespace std;

union Address{

   unsigned long number;

   unsigned char octet[4];     

} ip, mask, first, last;

 

void showAddress(Address& t){ // выводим адрес с разделителями

for(int i = 3; i >= 0; i--)

   cout << (unsigned int)t.octet[i] << (i > 0 ? "." : "\n");

}

 

int main() {

unsigned int s,prefix;

char ch;

for(int i = 3; i >= 0; i--){

   cin >> s >> ch;   // читаем адрес с разделителями

   ip.octet[i] = s;

}

cin >> prefix;

s = 0xFFFFFFFF << (32 - prefix);

mask.number = s;

showAddress(mask);

first.number = (ip.number & mask.number) | 1;

last.number = ip.number | (~mask.number);

if(prefix == 32) first = last;

showAddress(first);

showAddress(last);

return 0;

}

Классы

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

В.В.Бианки.