Поразрядная операция & называется также конъюнкцией, или логическим умножением, часто обозначается словом AND.
Поразрядная операция ИЛИ обозначается символом |. Когда над двумя значениями производится эта операция, то последовательно сравниваются значения всех битов при их двоичном представлении. Если соответствующий бит имеет значение 1 в первом или втором операнде, то результирующее значение будет равно 1. Рассмотрим предыдущий пример с поразрядной операцией ИЛИ:
Поразрядная операция ИЛИ (|) |
w1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 (25) |
w2 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 (77) |
w3 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 (93) |
Данную операцию обычно используют для установки заданных битов слова в 1. Ее называют также включающей дизъюнкцией, или логическим сложением. Часто применяется обозначение OR.
Поразрядная операция исключающего ИЛИ (^) работает следующим образом. Сравниваются соответствующие биты двух операндов, и если только один из битов равен 1, будет получен результат 1, а при равенстве обоих соответствующих битов или 0, или 1 результат будет равен 0. Для двух операндов b1, b2 при использовании исключающего ИЛИ справедлива таблица истинности (табл. 13.3).
Таблица 13.3 | ||
Таблица истинности операции исключающего ИЛИ | ||
b1 | b2 | b1 ^ b2 |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Если операцию исключающего ИЛИ использовать для одного и того же значения, то в результате получится нуль. Этот прием часто использовался программистами в языке ассемблера как наиболее быстрый путь установить значение в нуль или сравнить два значения на их равенство. Данный способ не рекомендуется использовать в языке программирования С, так как скорость работы не повышается, а программа становится менее понятной. Операция исключающего ИЛИ может применяться для перестановки значений двух переменных без выделения дополнительной памяти (и соответственно без использования дополнительной переменной).
Поразрядная операция исключающего ИЛИ называется также исключающей дизъюнкцией, применяется обозначение XOR.
13.3. Поразрядные операции сдвига
Оператор сдвига влево <<
Когда оператор сдвига влево << выполняется над некоторым значением, все биты, составляющие это значение, сдвигаются влево. Связанное с данным оператором число показывает количество бит, на которое значение должно переместиться. Биты, сдвигающие со старшего разряда, считаются потерянными, а на место младших битов всегда помещаются нули.
Оператор сдвига вправо >>
Операция сдвига вправо >> сдвигает разряды левого операнда вправо на количество позиций, указываемое правым операндом. Выходящие за правую границу разряды теряются. Для типов данных без знака (unsigned) освобождаемые слева позиции заполняются нулями. Для знаковых типов результат зависит от используемой системы. Освобождаемые позиции могут заполняться нулями либо копиями знакового (первого слева) разряда.
Поразрядные операции сдвига могут служить удобным и эффективным средством выполнения операций умножения и деления на числа, представляющие собой степени двойки. Они аналогичны смещению десятичной точки при умножении или делении на 10.
13.4. Битовые поля
Второй метод управления разрядами состоит в использовании битового (разрядного) поля, которое представляет собой последовательную цепочку разрядов в рамках значения типа signed int или unsigned int. Оно может быть только элементом структуры или объединения [3]. Создается путем объявления структуры (объединения), которая помечает каждое поле и определяет его разряд.
Приведем пример с использованием битовых полей в структуре [2]:
struct packed_struct {
unsigned int : 3;
unsigned int f1 : 1;
unsigned int f2 : 1;
unsigned int f3 : 1;
unsigned int type : 8;
unsigned int index : 18; };
В созданном шаблоне-структуре с дескриптором packed_struct первый член не имеет имени. Символ :3 задает три безымянных бита. Второй, третий и четвертый члены структуры – f1, f2, f3 также имеют тип unsigned int. Символ :1 говорит о том, что в данном члене структуры будет храниться 1 бит. Член структуры с именем type в памяти занимает 8 бит, член структуры index рассчитан на хранение 18 бит.
Для заданного шаблона структуры можно определить структурную переменную, например
struct packed_struct packed_data;
После этого можно присваивать значения полям структуры:
packed_data.type = 7;
Если ранее была объявлена какая-то переменная, например n, то присвоение может быть таким:
packed_data.type = n;
При этом нет необходимости беспокоиться о том, что значение переменной n будет слишком большим. Только младшие 8 бит будут учитываться при присваивании значения для поля packed_data.type. Для извлечения битовых полей структуры можно использовать обычное утверждение:
n = packed_data.type;
После извлечения значения поля type будет произведен сдвиг в сторону младших бит.
Битовые поля могут быть объявлены только как тип int (в стандарте С99 также _Bool), от реализации которого зависит, будет он знаковым (signed) или беззнаковым (unsigned). Для исключения неоднозначности следует использовать явные объявления: signed int или unsigned int. Битовые поля нельзя объединять в массивы, нельзя использовать адрес битового поля, поэтому не может быть такого типа, как указатель на битовое поле. Компилятор языка программирования С не переупорядочивает битовые поля для получения оптимального распределения памяти. Но в некоторых случаях может производиться выравнивание за счет безымянного поля. Это может использоваться для выравнивания следующего поля структуры по границе блока.
С помощью битовых полей можно формировать объекты с длиной внутреннего представления, не кратной байту.
Пример 13. Написать программу по демонстрации операции поразрядного отрицания (поразрядного дополнения) числа без знака, вводимого с клавиатуры, с использованием операций побитового сдвига.
Для решения примера зададим число, которое представим в виде нескольких разрядов, после чего через операции побитового сдвига изменим его и выведем на консоль.
Программный код решения примера:
#include <stdio. h> #include <conio. h> // Прототип функции void printBits(unsigned int var); // Главная функция int main (void) { unsigned int number; printf("\n The program on demonstration digit-by-digit operation of denying ( ~ )\n"); printf("\n\t Enter a whole number of unsigned: "); scanf_s("%u", &number); printf("\n\t Binary representation of the starting number and\n"); printf("\t Binary representation of bitwise negation of the initial number:\n"); printBits(number); //Исходное число printBits(~number); // Число после поразрядного дополнения printf("\n\n Press any key: "); _getch(); return 0; } // Функция побитового представления целого числа без знака void printBits(unsigned int var) { unsigned int b; unsigned int mask = 1 << 31; // shift to 31 bit printf("\n\t %10u = ", var); for (b = 1; b <= 32; ++b) { printf("%c", var & mask? '1' : '0'); var <<= 1; // or: var = var << 1; if (b % 8 == 0) putchar(' '); } } |
В программе применен форматный ввод числа в виде %u и вывод числа в виде %10u, где u используется для беззнакового типа числа, 10 – количество позиций, отводимое для десятичного числа. Предполагается, что заданное число может быть представлено 32 разрядами: по 4 группы с 8 разрядами (4 байта по 8 бит в каждом). Применение оператора сдвига (<<) позволяет все биты числа сдвигать на единицу (действие в цикле for) влево. При этом используется операция поразрядного И. С помощью оператора условия (?) осуществляется замена 1 на 0 и наоборот.
Возможный результат выполнения программы показан на рис. 13.1. Видно, что все нули или единицы исходного числа (в двоичном представлении) были инвертированы.
Рис. 13.1. Поразрядное инвертирование целого числа
14. Рекурсивные алгоритмы и функции
Рекурсивные функции (лат. recursio – возвращение) – в вычислительной математике функции, определенные на множестве натуральных чисел и принимающие значения того же множества.
Рекурсивный алгоритм – это алгоритм, решающий задачу путем решения одного или нескольких более простых вариантов той же задачи. Функция называется рекурсивной, если в ее определении содержится вызов этой же функции. Рекурсивная функция может вызывать саму се6я или непосредственно, или косвенно через другую функцию. Рекурсии целесообразно применять в задачах, которые можно разбить на множество меньших подобных задач. Рекурсия в программировании может быть определена как сведение задачи к такой же задаче, но манипулирующей более простыми данными.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
Основные порталы (построено редакторами)