Результаты битовых операций
УТВЕРЖДАЮ
Ректор университета
____________ А.В. Лагерев
«___» ____________ 2009 г.
ПРОГРАММИРОВАНИЕ НА ЯЗЫКАХ ВЫСОКОГО УРОВНЯ
РАБОТА С БИТОВЫМИ ОПЕРАЦИЯМИ
Методические указания к выполнению лабораторной работы №8
для студентов 1 курса очной формы обучения
специальностям 230105 «Программное обеспечение
вычислительной техники и автоматизированных систем» и 010503 «Математическое обеспечение и администрирование информационных систем».
Брянск 2009
УДК 539.3
Программирование на языках высокого уровня. Работа с битовыми операциями: методические указания к выполнению лабораторной работы №8 для студентов 1 курса дневной формы обучения специальностям 230105 «Программное обеспечение вычислительной техники и автоматизированных систем» и 010503 «Математическое обеспечение и администрирование информационных систем». Брянск: БГТУ, 2008. – 12 с.
Разработал А.П. Бабин,
канд. техн. наук
Рекомендовано кафедрой «Информатика и программное обеспечение» БГТУ (протокол № 6 от 13.02.09)
ЦЕЛИ И ЗАДАЧА РАБОТЫ
Цели работы:
1. Изучить принципы работы с битовыми операциями
2. Дальнейшее совершенствование в вопросах проектирования, разработки, тестирования и документирования программ
Задача работы: составить программу на алгоритмическом языке Си по заданию преподавателя.
Продолжительность работы – 4 часа.
2. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ*
Любые данные, записанные в память ЭВМ, как известно, представляют собой последовательность бит, т.е. последовательность нулей и единиц. Например, любое число типа int будет занимать 2 байта в памяти, т.е 16 бит (про программировании под Windows – 4 байта). Его можно рассматривать двояко: либо как целое число ( так и делается при выполнении операций *,/, +, -, % ), либо как последовательность бит, что возможно при использовании битовых операций.
Битовые операции выполняются независимо над каждым битом данных. Если операция двуместная, то она выполняется над соответствующими битами операндов.
В Си имеются следующие битовые операции:
~ битовое отрицание (одноместная),
& побитовое "и" (двуместная),
^ побитовое "исключающие или" (двуместная),
| побитовое "или" (двуместная).
Результат этих операций определяет таблица значений для всевозможных комбинаций бит двух операндов.
Результаты битовых операций
| op1 | op2 | ~op1 | op1 & op2 | op1 ^ op2 | op1 | op2 |
Рассмотрим несколько примеров.
Первый пример показывает, как с помощью операции | можно установить в единицу выбранные биты операнда:
/* a = 00001001 = 9 */
char a, b; /* 00011010 = 26 */
a = 9; /* -------- */
b = a | 26 /* b = 31 */ /* b = 00011011 = 31 */
Следующий пример показывает, как с помощью операции & можно обнулить старшую часть байта:
char a, b; /* a = 00101101 = 45 */
a = 45; /* 00001111 */
b = a & 0x0F; /* -------- */
/* b = 00001101 = 13 */
Очередной пример показывает, как с помощью операции ^ можно инвертировать часть байта:
char a, b; /* a = 00101001 = 41 */
a = 41; /* 00001111 */
b = a ^ 0x0F; /* -------- */
/* b = 00100110 = 38 */
К битовым операциям относятся операции сдвига << и >> :
a << b сдвиг битов переменной a влево на b позиций,
a >> b сдвиг битов переменной a вправо на b позиций.
Например:
char a, b;
a = 26; /* a = 00011010 = 26 */
b = a << 2; /* b = 01101000 = 104 */
Сдвиг влево равносилен умножению на 2 в соответствующей степени. Сдвиг вправо - делению на 2 в соответствующей степени.
Все битовые операции выполняются слева направо. В следующей строке приведены битовые операции в порядке уменьшения их приоритета: ~, << >>, &, ^, |
ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
1. Изучить методические указания по выполнению лабораторной работы
2. Составить программу на алгоритмическом языке Си
3. Составить контрольный пример, отладить программу
4. Ответить на вопросы преподавателя
ВАРИАНТЫ ЗАДАНИЙ
1. Реализовать функции чтения и записи даты (день, месяц, год в столетии) из типа int (16 бит) по формату: 5 бит – день, 4 бита – месяц, 7 бит – год в столетии.
Пример: 15 марта 2008 -> 0001000 0011 01111
2. Реализовать функции чтения и записи времени (часы, минуты, секунды) из типа int (16 бит) по формату: 6 бит – секунды, 6 бит – минуты, 4 бита – часы от 0 до 12.
3. Реализовать функции чтения и записи из типа int (16 бит) следующих данных: возраст (от 0 до 127) – 7 бит, пол – 1 бит, семейное положение – 1 бит, количество детей - 4 бита.
4. Реализовать функции чтения и записи из типа int (16 бит) следующих данных: масть карты – 2 бита, значение карты – 4 бита, номер колоды – 1 бит.
5. Реализовать функции чтения и записи из типа int (16 бит) числа с плавающей точкой по формату: 1 бит - знак мантиссы, 10 бит – мантисса, 1 бит – знак степени, 4 бита – степень.
Пример: 7.87 (тоже самое 787*10-2) -> 0 1100010011 1 0010
Пример: -5676500.45 (можем записать только -567*104) -> 1 1000110111 0 0100.
Примечание.
Значение степени можно получить следующим образом:
pw=floor(log10(fabs(val)))-2;
Значение мантиссы можно получить следующим образом:
fpp = floor(val/pow10(pw));
6. Реализовать функции чтения и записи из типа int (16 бит) следующих данных: цвет обуви – 4 бита, размер (от 33 до 48) – 4 бита, женская/мужская – 1 бит, сезон - 2 бита.
7. Реализовать функции чтения и записи из типа int (16 бит) следующих данных: внутренний диаметр колеса (R12 - R19) – 3 бита, ширина (значение ширины минус 100мм) – 7 бит, профиль (значение минус 40) 6 бит.
Пример: 175/70 R13 – 001110 1001011 001 (здесь 175 – ширина, 70 профиль).
8. Реализовать функции чтения и записи из типа int (16 бит) следующих данных: номер лабораторной работы – 4 бита, оценка – 3 бита, количество бонусов – 4 бита.
9. Реализовать функции чтения и записи из типа int (16 бит) следующих данных: цвет – 4 бита, номер модели – 4 бита, количество – 7 бит.
10. Реализовать функции чтения и записи из типа char (8 бит) следующих данных: цвет окна – 4 бита, наличие кнопок свернуть и минимизировать – 2 бита, модальное/немодальное окно – 1 бит, разрешено изменять размеры – 1 бит.
11. Реализовать функции шифрования и дешифрования строк. Принцип шифрования: два младших бита каждого символа перенести в начало, после чего три младших бита инвертировать. После шифрования напечатать коды символов зашифрованной строки и полученную строку. Дешифровать результат и убедиться, что строка стала равна исходной.
12. Реализовать функции шифрования и дешифрования строк. Принцип шифрования: для каждого символа сначала расположить все четные биты, затем нечетные. После шифрования напечатать коды символов зашифрованной строки и полученную строку. Дешифровать результат и убедиться, что строка стала равна исходной.
13. Реализовать функции шифрования и дешифрования строк. Принцип шифрования: на четыре бита слева каждого символа наложить 4-ёх битную маску (операция XOR), затем пять бит справа каждого символа расположить в обратном порядке. После шифрования напечатать коды символов зашифрованной строки и полученную строку. Дешифровать и убедиться, что строка стала равна исходной.
14. Реализовать функции шифрования и дешифрования строк. Принцип шифрования: на четыре бита слева каждого символа наложить 4-ёх битную маску (операция XOR), затем первый и третий биты слева поменять местами. После шифрования напечатать коды символов зашифрованной строки и полученную строку. Дешифровать результат и убедиться, что строка стала равна исходной.
15. Реализовать функции шифрования и дешифрования строк. Принцип шифрования: четыре бита слева каждого символа инвертировать, на пять бит справа наложить побитовую маску (операция XOR). После шифрования напечатать коды символов зашифрованной строки и полученную строку. Дешифровать и убедиться, что строка стала равна исходной.
16. Реализовать функции шифрования и дешифрования строк. Принцип шифрования: поменять местами первые четыре бита каждого символа с четырьмя последними битами каждого следующего символа; тоже самое сделать с последним и первым символом строки. После шифрования напечатать коды символов зашифрованной строки и полученную строку. Дешифровать результат и убедиться, что строка стала равна исходной.
17. Реализовать функции шифрования и дешифрования строк. Принцип шифрования: на средние четыре бита каждого символа наложить 4-ёх битную маску (операция XOR), затем поменять местами старшие 3 бита с младшими. После шифрования напечатать коды символов зашифрованной строки и полученную строку. Дешифровать результат и убедиться, что строка стала равна исходной.
18. Реализовать функции шифрования и дешифрования строк. Принцип шифрования: на два старших и два младших бита каждого символа наложить 4-ёх битную маску (операция XOR), средние шесть бит инвертировать. После шифрования напечатать коды символов зашифрованной строки и полученную строку. Дешифровать результат и убедиться, что строка стала равна исходной.
19. Реализовать функции шифрования и дешифрования строк. Принцип шифрования: на все биты каждого символа наложить восьми битную маску (операция XOR), затем поменять местами четные и нечетные биты. После шифрования напечатать коды символов зашифрованной строки и полученную строку. Дешифровать результат и убедиться, что строка стала равна исходной.
20. Реализовать функции шифрования и дешифрования строк. Принцип шифрования: два младших бита каждого символа поместить в середину оставшихся шести бит, на результат наложить восьми битную маску (операция XOR). После шифрования напечатать коды символов зашифрованной строки и полученную строку. Дешифровать результат и убедиться, что строка стала равна исходной.
СОДЕРЖАНИЕ ОТЧЕТА
Отчет должен содержать:
- программу
- для вариантов 1-10:
× входные параметры (день, месяц, год; цвет, модель, количество и т.п.)
× значение числа типа int, которое было сформировано по этим данным
× бинарное представление сформированного числа типа int
× какое-либо число типа int в качестве входного параметра
× прочитанные данные их этого числа (день, месяц, год; цвет, модель, количество и т.п.)
× продемонстрировать корректность работы программы на примере записи данных в число int и обратного чтения;
- для вариантов 11-20:
× исходную строку символов
× зашифрованную строку
× последовательность кодов символов зашифрованной строки
× продемонстрировать корректность работы программы на примере шифрования и дешифрования строки символов
Текст программы должен включать подробные комментарии, поясняющие назначения процедур, их параметры, использование переменных, смысл и особенности реализации отдельных программных блоков.
ПРИМЕР РЕШЕНИЯ ЗАДАЧИ
Преобразовать число int по следующему принципу: два младших бита перенести в начало, после чего младшие 8 бит инвертировать.
#include<conio.h>
#include<stdio.h>
int incode( unsigned int data )
{
unsigned int rez;
char tmp;
// Получаем два младших бита
tmp = data&3;
// Переносим два младших бита в начало
rez = (data>>2)|(tmp<<14);
// Инвертируем 8 младших бит
rez = rez^(0xFF);
return rez;
}
int decode( unsigned int data )
{
unsigned int rez;
char tmp;
// Инвертируем 8 младших бит
rez = data^(0xFF);
// Получаем два старших бита
tmp = (rez>>14)&3;
// Переносим два старших бита в конец
rez = (rez<<2)|tmp;
return rez;
}
void printBinary(unsigned int v)
{
int i;
for( i=sizeof(int)*8-1; i>=0; i-- )
printf("%d", (v>>i)&1 );
printf("\n" );
}
void main(void)
{
unsigned int v_in, v_out;
clrscr();
printf("Введите число ");
scanf( "%u", &v_in );
v_out = incode(v_in);
printf("Исходное число %u\n", v_in);
printf("Его бинарное представление: ");
printBinary(v_in);
printf("После кодирования %u\n", v_out);
printf("Бинарное представление: ");
printBinary(v_out);
printf("После декодирования %u\n", decode(v_out));
getch();
}
Введите число 101
Исходное число 101
Его бинарное представление: 0000000001100101
После кодирования 16614
Бинарное представление: 0100000011100110
После декодирования 101
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Какой битовой операцией можно установить значение бита в 0?
2. Какой битовой операцией можно установить значение бита в 1?
3. Каким образом можно установить 0 в третий справа бит, не изменив значения других битов?
4. Что означает следующее выражение: (v>>5)&1? Чем результат этого выражения отличается от v&(1<<5)?
5. Как изменится число, если к нему два раза применить операцию исключающего «или» с одним и тем же значением (например, (45^82)^82)?
6. Чем битовое отрицание (~) отличается от обычного отрицания (!)?
7. Как проверить четность целого числа с помощью битовых операций?
8. Как с помощью битовых операций получить остаток от деления целого числа на четыре?
9. Значения каких битов могут измениться, если к некоторому числу применить операцию «или» с числом 18 ( x|18 )? Как изменится результат этого выражения, если операцию «или» с числом 18 применить еще раз ( (x|18)|18 )?
10. Где и как применяются битовые операции?
СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ
1. Березин Б.И., Березин С.Б. Начальный курс С и С++. – М.: Диалог-МИФИ, 2007. – 288с.
2. Дейтел, Х. Как программировать на С: [пер. с англ.]/ Х. Дейтел, П. Дейтел. – М.: БИНОМ-ПРЕСС, 2002. – 1168с.
3. Керниган Б., Ритчи Д.. Язык программирования Си. – СПб.: Невский Диалект, 2000. - 350 с.
4. Керниган Б., Пайк Р.. Практика программирования. - СПб.: Невский Диалект, 2001. - 380 с.
5. Павловская Т. А., Щупак Ю. А.. С/С++. Структурное программирование: Практикум. – СПб.: Питер, 2007. – 238 с.
6. Павловская Т.А.. С/С++. Программирование на языке высокого уровня. СПб.: Питер, 2006. – 464 с.
Программирование на языках высокого уровня. Работа с битовыми операциями: методические указания к выполнению лабораторной работы №8 для студентов 1 курса очной формы обучения специальностям 230105 «Программное обеспечение вычислительной техники и автоматизированных систем» и 010503 «Математическое обеспечение и администрирование информационных систем».
АЛЕКСАНДР ПАВЛОВИЧ БАБИН
Научный редактор В.И. Израилев
Редактор издательства Л.И. Афонина
Компьютерный набор А.П. Бабин
Темплан 2009г., п.295
Подписано в печать . Формат 60x84 1/16. Бумага офсетная. Офсетная печать
| Усл. печ. л. 0,7 | Уч.-изд. л. 0.7 | Тираж 30 экз. Заказ Бесплатно |
Брянский государственный технический университет
241035, г. Брянск, бульвар им. 50-летия Октября, 7, БГТУ. 58-82-49
Лаборатория оперативной типографии БГТУ, ул. Харьковская, 9.