ПОБИТОВИ ОПЕРАЦИИ
1. Побитови операции
знак
|
име
|
пример
|
операция
|
резултат
|
~
|
Отрицание
|
~ 01010010
|
10101101
|
&
|
Логическо „и”
|
01010010 &11001001
|
01000000
|
|
|
Логическо „или”
|
01010010 | 11001001
|
11011011
|
^
|
Изключващо „или”
|
01010010 ^ 11001001
|
10011011
|
>>
|
Отместване надясно
битове >> цяло >0 число
|
01010010 >> 3
01010010 >> -3
|
00001010
10010000
|
<<
|
Отместване наляво битове << цяло >0 число
|
01010010 << 3
01010010 << -3
|
10010000
00001010
|
2. Пояснителни фрагменти
фрагмент
|
b
|
Op b
|
резултат
|
обяснение
|
int b = 107;
printf(%d”, ~b);
|
01101011
|
10010100
|
-108
|
Отрицателните числа се съхраняват в допълнителен код
int се съхраняват в 2 B
|
unsigned int b = 107;
printf(%u”, ~b);
|
01101011
|
10010100
|
65428
|
1111111110010100 (2) = 65428 (10)
unsigned int се съхраняват в 2 B
|
unsigned int b = 2;
printf(%u”, 1^b);
|
10
|
11
|
3
|
Ако битовете са различни, резултатът е едно
|
unsigned int b = 2;
printf(%u”, b<<3);
|
10
|
10000
|
16
|
b<<1 е еквивалентно на умножаване на b с 2
2.2.2.2=16
|
unsigned int b = 17;
printf(%u”, b>>1);
|
10001
|
01000
|
8
|
b>>2 е еквивалентно на целочислено деление на 2
|
3. Задачи
зад. *
Да се преброят единиците в битовете на цяло число x
int bitcount (unsigned x)
{
int b;
for (b = 0; x != 0; x >>= 1)
if (x & 01) b++;
return b;
}
|
Зад. **
отпечатване на двоичното представяне на цяло число
#include
int main () {
int N, i; unsigned mask = 1;
scanf(“%d”, &N);
i = 8*sizeof(unsigned);
mask <<= i -1;
printf(“The binary represetation of %d is “, N);
while (mask)
{
printf(“%d”, N&mask?1:0);
mask>>=1;
}
printf(“\n”);
return 0;
}
|
Зад. *
Дадена е огромна редица от цели числа, с неизвестен брой елементи. Всяко число в редицата се среща точно по два пъти, с изключение на едно. Намерете го.
#include
int main() {
int y, z;
scanf("%d", &z);
while (!feof(stdin))
{
scanf("%d", &y);
z ^= y;
}
printf("%d", z);
return 0;
}
|
Зад. ************
Да се опише функция, която взема n бита на цяло положително число без знак, започващи от позиция p.
#include
unsigned getbits (unsigned x, int p, int n) {
return (x>>(p+1-n))&~(~0<
}
int main() {
unsigned x;
scanf("%u", &x);
printf("%d", getbits(x, 4, 3));
return 0;
}
|
Пример
Вход
16
|
10000
от 4тия бит се вземат 3
|
Изход
4
|
100
|
Зад. *
Напишете програма, по описания псевдокод за умножаване на две произволни цели числа чрез използване на отместване на битове и събиране.
c := 0
while b ≠ 0
if b and 1 ≠ 0
c := c + a
shift a left by one
shift b right by one
return c
Зад. *
XOR кодирането е трудно разбиваемо с метода на грубата сила. Необходимо е да са известни и кодиращия, и декодиращия ключ.
Реализирайте XOR кодиране с метода на Vernam
Текста, който трябва да кодирате е съобщението Text. За ключ създайте произволен стринг Key. Необходимо е дължините им да са равни LENGTH(Text)=LENGTH(Key)
Кодирането на текста става чрез прилагането на „изключващо побитово или” на първоначалния текст и ключа.
Ciphertex t = BITXOR(Text, Key)
Разшифрирането на кодирания текст става чрез прилагането на „изключващо побитово или” на кодирания текст и ключа (ако го знаете)
Plaintext = BITXOR(Ciphertext, Key)
Получения текст трябва да съвпада с началното съобщение.
Зад. **+
От предния алгоритъм съставете две програми, едната за кодиране, а другата за декодиране. Нека ключа да бъде известен само на програмиста, т.е. програмите ще се изпълняват от exe файловете си. Съобщението, което ще се кодира се въвежда, като параметър на програмата. Втората програма използва кодирания текст, получен от първата, като чете кодирания текст от текстов файл и извежда резултата на екрана.
Побитови операции – ЕСП – Информатика – II курс – 2005 - ВСУ
1>
Сподели с приятели: |