Лекция 7. Битовые поля и побитовые операции ####################################################################################### Системы счисления =========================================================== Теория ----------------------------------------------------------- Системы счисления `````````````````````````````````````````````````````````` В настоящее время применяются **позиционные** системы счисления, изобретённые в Древней Индии. Основные используемые системы счисления: #. Двоичная (алфавит :math:`A_2={0,1}` ). #. Десятичная (алфавит :math:`A_{10}={0,1,2,3,4,5,6,7,8,9}` ). #. Шестнадцатеричная (алфавит :math:`A_{16}={0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f}` ). Принцип формирования числа: :math:`n = a_{m-1}(o)^{m-1}+...+a_1(o)+a_0` :math:`o` - основание системы счисления (2,10,16). :math:`a` - значение разряда. :math:`m` - номер разряда. *Пример:* :math:`234 = 2*10^2+3*10^1+4*10^0` Перевод из двоичной в десятичную `````````````````````````````````````````````````````````` *Пример* Имеем двоичное число :math:`n_{2}=00101001` . :math:`o=2, m=8` Ему соответствует десятичное :math:`n_{10}=0*(2)^7+0*(2)^6+1*(2)^5+0*(2)^4+1*(2)^3+0*(2)^2+0*(2)^1+1*(2)^0=32+8+1=41` Числа, содержащие по одной единице легко запоминаются: .. list-table:: * - :math:`00000001` - :math:`1` * - :math:`00000010` - :math:`2` * - :math:`00000100` - :math:`4` * - :math:`00001000` - :math:`8` * - :math:`00010000` - :math:`16` * - :math:`00100000` - :math:`32` * - :math:`01000000` - :math:`64` * - :math:`10000000` - :math:`128` Несложно выполнить перевод, если числа содержат несколько идущих подряд единиц: .. list-table:: * - :math:`00000011` - :math:`4-1=3` * - :math:`00000111` - :math:`8-1=7` * - :math:`00001111` - :math:`16-1=15` * - :math:`00011111` - :math:`32-1=31` * - :math:`00111111` - :math:`64-1=63` * - :math:`01111111` - :math:`128-1=127` * - :math:`11111111` - :math:`256-1=255` Перевод из десятичной в двоичную `````````````````````````````````````````````````````````` Пусть дано :math:`n_{10}=57` #. Разделить 57 на 2: 28 - 1 (с остатком) #. Разделить 28 на 2: 14 - 0 (без остатка) #. Разделить 14 на 2: 7 - 0 (без остатка) #. Разделить 7 на 2: 3 - 1 (с остатком) #. Разделить 3 на 2: 1 - 1 (с остатком) #. Разделить 1 на 2: 0 - 1 (с остатком) Пишем значения разрядов в обратном порядке. В результате получаем :math:`n_2=111001` . Перевод из шестнадцатиричной в десятичную `````````````````````````````````````````````````````````` *Пример* :math:`2a = 2*16^1+a = 32+10 = 42` *Пример* :math:`ff = f*16^1 +f = 15*16+15 = 255` Перевод из шестнадцатиричной в двоичную `````````````````````````````````````````````````````````` Удобно переводить шестнадцатиричное число в двоичное по **тетрадам**: *Пример* Рассмотрим число :math:`8a` .. list-table:: * - :math:`8` - :math:`a` * - :math:`1000` - :math:`1010` Ответ: :math:`10001010` Арифметика ----------------------------------------------------------- Сложение `````````````````````````````````````````````````````````` .. image:: _static/07/add.png Вычитание `````````````````````````````````````````````````````````` .. image:: _static/07/sub.png Знак числа `````````````````````````````````````````````````````````` .. image:: _static/07/nums.png Порядок байтов ----------------------------------------------------------- Little Endian vs. Big Endian `````````````````````````````````````````````````````````` .. image:: _static/07/endian.png Используется два порядка расположения байтов в многобайтной величине: от старшего к младшему **big endian** и от младшего к старшему **little endian**. .. image:: _static/07/5.png **BE** используют: IBM 360/370/390, Motorola 68000, SPARC **LE** используют: Intel x86 Достоинства LE `````````````````````````````````````````````````````````` Существенным достоинством **little-endian** по сравнению с **big-endian** порядком записи считается возможность ''неявной типизации'' целых чисел при чтении меньшего объёма байт. Так, если в ячейке памяти содержится число 0x00000022, то прочитав его как int16 (два байта) мы получим число 0x0022, прочитав один байт — число 0x22. Однако, это же может считаться и недостатком, потому что провоцирует ошибки потери данных. Проверка `````````````````````````````````````````````````````````` Следующие функции позволяют проверить, какой порядок байт принят в вашей системе: .. code-block:: c int endian1() { int one = 1; char *ptr; ptr = (char *)&one; return (*ptr); } int endian2() { union { int one; char ch; } endn; endn.one = 1; return endn.ch; } Использование полей битов =========================================================== Представление байта `````````````````````````````````````````````````````````` Очень полезное с практической точки зрения представление памяти в 1 байт, которое можно использовать как *unsigned char* или как набор значений отдельных битов. .. code-block:: c union CODE { unsigned char ch; struct BYTE { unsigned b1:1; unsigned b2:1; unsigned b3:1; unsigned b4:1; unsigned b5:1; unsigned b6:1; unsigned b7:1; unsigned b8:1; } byte; }; Преобразование в двоичную систему `````````````````````````````````````````````````````````` Функция, переводящая байт из 10-тичной системы в 2-ичную с использованием поля битов: .. code-block:: c void bin(unsigned char c) { union CODE code; code.ch=c; printf("Bit numbers: 8 7 6 5 4 3 2 1 \n"); printf("Bit values: %d %d %d %d %d %d %d %d ", code.byte.b8, code.byte.b7, code.byte.b6, code.byte.b5, code.byte.b4, code.byte.b3, code.byte.b2, code.byte.b1); printf("Number: %d Symbol: %c\n",c,c); } Побитовые операции =========================================================== Обзор ----------------------------------------------------------- Побитовые операции `````````````````````````````````````````````````````````` Побитовые операции применяются к значениям отдельных разрядов числа и их не следует путать с обычными логическими операциями (&&, ||,!), которые действуют на значение в целом. * **&** - умножение (конъюнкция) * ** :math:`|` ** - сложение (дизъюнкция) * \alert{\~{ - отрицание * ** :math:`>>` ** - побитовый сдвиг вправо * ** :math:`<<` ** - побитовый сдвиг влево * ** :math:`\widehat{**` } - исключающее "или" (xor) Вместе с этими операциями может использоваться присваивание, например **a>>=2** Отрицание `````````````````````````````````````````````````````````` Поразрядное отрицание \alert{\~{ меняет значение битов на противоположное .. code-block:: c unsigned char a=4; (00000100) unsigned char b=~a; (11111011) Следующая функция возвращает максимальное значение **unsigned int** в вашей системе: .. code-block:: c typedef unsigned int ui; ui getMaxUIValue() { return ~(ui)0; } Поразрядное ''И'' `````````````````````````````````````````````````````````` Операция **&** ''И'' является бинарной и выставляет результирующий бит в 1, если оба бита операндов равны 1. .. image:: _static/07/lcd1.png Поразрядное И `````````````````````````````````````````````````````````` Преобразование числа в бинарную форму: .. code-block:: c void binary(ui n) { for(int i = 256; i > 0; i /=2) { if(n & i) putchar('1'); else putchar('0'); } putchar('\n'); } Поразрядное ''ИЛИ'' `````````````````````````````````````````````````````````` Операция **|** ''ИЛИ'' является бинарной и выставляет результирующий бит в 1, если хотя бы один бит у операндов равен 1. .. image:: _static/07/lcd2.png Поразрядное ИСКЛЮЧАЮЩЕЕ ИЛИ `````````````````````````````````````````````````````````` Операция ** :math:`\widehat{**` } ''ИСКЛЮЧАЮЩЕЕ ИЛИ'' является бинарной и выставляет результирующий бит в 1, если первый (или второй) бит операнда равен 1, но не оба одновременно. .. image:: _static/07/lcd3.png XOR `````````````````````````````````````````````````````````` В следующем примере **XOR** используется для обмена значений двух целочисленных переменных: .. code-block:: c void swap(int *a,int *b) { *a=*a^*b; *b=*a^*b; *a=*a^*b; } Полезные мелочи ----------------------------------------------------------- Проверка, выставлен ли данный бит: .. code-block:: c int getBit(int n, int index) { return ( (n & (1 << index) ) > 0); } Подсчёт количества выставленных битов: .. code-block:: c int bitCountA(int n) { int count = 0; while(n) { if(n & 1) count++; n = n >> 1; } return count; } Очистка заданного бита: .. code-block:: c unsigned char b &= ~(1 << n); Переключение бита: .. code-block:: c unsigned char c ^= (1 << n); Выделение первого и второго байтов: .. code-block:: c unsigned char right = val & 0xff; unsigned char left = (val>>8) & 0xff; Выделение знакового разряда: .. code-block:: c char sign = val & 0x8000; Маски `````````````````````````````````````````````````````````` **Маска** - это битовый шаблон с установленными значениями разрядов. Если найти результат операции ''И'' между величиной и маской, то в результате получим только те значения разрядов, у которых маска содержала единицы: .. image:: _static/07/lcd4.png В данном примере из 24-битной величины выделяется первый байт. При необходимости можно включить специфические биты, не изменяя оставшиеся. Это произойдет, если наложить маску с помощью операции **|**. .. code-block:: c flags |= MASK; Аналогично можно отключить избранные разряды: .. code-block:: c flags &= ~MASK; Приведем пример с переключением значения битов (установкой в ноль единиц): .. code-block:: c flags ^= MASK; Для сравнения значения разряда необходимо сначала маскировать другие биты .. code-block:: c if((flags & MASK)==MASK) { ... } Вопросы для самоконтроля ============================================= * Опишите принцип формирования числа в позиционной системе счисления. * Перечислите наиболее распространенные системы счисления. * Как перевести число из двоичной системы в десятичную? * Как перевести число из десятичной системы в двоичную? * Как перевести шестнадцатиричное число в десятичное? * Как перевести шестнадцатиричное число в двоичное? * Как узнать, какой порядок байт в вашей системе? * Как можно перевести число в двоичную систему без деления? * Перечислите побитовые операции. * Чему равен результат поразрядного отрицания? * Как узнать максимальное значение целого беззнакового типа в системе? * Чему равен результат поразрядного И? * Чему равен результат поразрядного ИЛИ? * Чему равен результат поразрядного исключающего ИЛИ? * Как реализовать обмен двух целых без вспомогательной ячейки? * Что такое маска? Для чего могут использоваться маски? * Как включить и выключить специфические разряды? * Как можно переключить значение бита? Сравнить значение бита?