Лекция 8
Наименьшая адресуемая ячейка памяти — байт (адреса 0, 1, 2, …)
Байт — обычно 8 битов
Зачем нужен доступ к битам?
1. Компактное хранение информации (вместо 1 байта — 1 бит, размер расходуемой памяти уменьшается в 8 раз)
2. Операции с числами — удобно выполнять при помощи битовых операций.Добавить
Пример 1. Деление на 2:
char x; unsigned char y; /* x – в [-126, 127], y – в [0, 255] */
x /= 2;
x >>= 1; /* x = x >> 1; */
x:
|
Номер бита |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
Значение бита |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
Отрицательные числа (в прямом представлении):
-1 = 10000001 (знак 1, в младших 7 битах - абсолютное значение: 1)
Отрицательные числа (в дополнительном представлении):
-1 = 11111111 (знак 1, абсолютное значение — в дополнительном коде)
-2 = 11111110
-3 = 11111101
…
-128 = 10000000
1
|
Номер бита |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
Значение бита |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1
|
Номер бита |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
Значение бита |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 + (-1):
|
Номер бита |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
Значение бита |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Битовые операции:
1.
Логические
а) И (&)
б) ИЛИ (|)
в) Исключающее ИЛИ (^)
г) НЕ (~)
2. Сдвига
а) Влево (<<) - в сторону старших битов
б) Вправо (>>) - в сторону меньших битов
|
И |
0 |
1 |
|
0 |
0 |
0 |
|
1 |
0 |
1 |
|
ИЛИ |
0 |
1 |
|
0 |
0 |
1 |
|
1 |
1 |
1 |
|
Исключющее ИЛИ |
0 |
1 |
|
0 |
0 |
1 |
|
1 |
1 |
0 |
|
НЕ |
|
|
0 |
1 |
|
1 |
0 |
Задача 1. Найти количество битов со значением 1 в целом числе.
N
|
Значение бита |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1) mask
|
Значение бита |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
N&mask:
|
Значение бита |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2) mask
|
Значение бита |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
N&mask:
|
Значение бита |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3) mask
|
Значение бита |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
N&mask:
|
Значение бита |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4) mask
|
Значение бита |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
N&mask != 0
|
Значение бита |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
...
8) mask
|
Значение бита |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
N&mask != 0
|
Значение бита |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
9) mask
|
Значение бита |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
#include <stdio.h>
int main(void) {
int N, res = 0, mask = 1;
printf("Input number\n");
scanf("%d", &N);
while(mask) { /* != 0 */
if (N & mask) { /* !=0 */
++res; /* Non-zero bit found */
}
mask <<= 1;
}
printf("%d bits\n", res);
return 0;
}
Задача 2. Найти количество битов в целом числе
#include <stdio.h>
int main(void) {
int res = 0, mask = 1;
printf("Input number\n");
while(mask) { /* != 0 */
++res;
mask <<= 1;
}
printf("%d bits in integer\n", res);
return 0;
}
Сдвиг — эффективнее, чем умножение (и тем более деление) на два, так как это одна ассемблерная инструкция (ассемблер — язык машинных кодов в записи, понятной человеку)
ARM (RISC – Restricted Instruction Set):
ASL – сдвиг влево на 1 бит
ASR – сдвиг вправо
ROL – циклический сдвиг
ROR – циклический сдвиг
Задача 3. Быстрое возведение в степень — используя O(log2(N)) умножений
Справа налево (от младших степеней)
Слева направо (от старших степеней) — схема Горнера
K**N = A*A*A*...*A – N-1 умножение
K**(2**l) = (A*
K**32 = ((A**2)**2)**2)**2)**2) – 5 умножений = log2(32)
O(N**2) – при увеличении N в 2 раза — количество операций вырастет в 4 раза
N = an-1 * 2**(n-1) + an-2 * 2**(n-2) + … + a2 * 2**2 + a1 * 2**1 + a0 * 2**0
A**N = A ** (an-1 * 2**(n-1) + an-2 * 2**(n-2) + … + a2 * 2**2 + a1 * 2**1 + a0 * 2**0) =
= ((...((A**an-1)**2*(A** an-2)**2)…)*(A** a1)**2)*(A** a0 )
Задача 4. Найти беззнаковое целое число, у которого самый старший бит — 1, остальные все биты 0
M:
|
Номер бита |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
Значение бита |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
M>>1:
|
Номер бита |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
Значение бита |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
M-(M>>1):
|
Номер бита |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
Значение бита |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
#include <stdio.h>
int main(void) {
unsigned int M = -1;
M -= (M>>1);
printf("res: %x\n", M);
return 0;
}
Решение задачи 3:
#include <stdio.h>
int main(void) {
int A, N, res = 1;
unsigned int M = -1;
M -= (M>>1);
/* printf("res: %x\n", M); */
printf("Input number and degree:\n");
scanf("%d%d", &A, &N);
while (M) {
if (res > 1) { /* log2(N) multiplications */
res *= res;
}
if (N & M) { /* <= log2(N) multiplications */
res *= A;
}
M >>= 1;
}
printf("Res: %d\n", res);
return
0;
}