# Бройни системи и побитови операции

| Десетична (decimal) | Двоична (binary) | осмична (octal) | Шестнайсетична (hexadecimal) | Унарна (unary) |
|---------------------|------------------|-----------------|------------------------------|-------|
| 00                  | 00000            | 00              | 00                           | 00001 |
| 01                  | 00001            | 01              | 01                           | 00011 |
| 02                  | 00010            | 02              | 02                           | 00111 |
| 03                  | 00011            | 03              | 03                           | 01111 |
| 04                  | 00100            | 04              | 04                           | ...   |
| 05                  | 00101            | 05              | 05                           |       |
| 06                  | 00110            | 06              | 06                           |       |
| 07                  | 00111            | 07              | 07                           |       |
| 08                  | 01000            | 10              | 08                           |       |
| 09                  | 01001            | 11              | 09                           |       |
| 10                  | 01010            | 12              | 0A                           |       |
| 11                  | 01011            | 13              | 0B                           |       |
| 12                  | 01100            | 14              | 0C                           |       |
| 13                  | 01101            | 15              | 0D                           |       |

#### Преобразуване между бройни системи

Примери:

 - Алгоритъм за преобразуване от произволна бройна система в дестична бройна система
 - Алгоритъм за преобразуване от десетчина бройна система в произволна бройна система

#### Представяния на отрицателни числа

 - One's complement  (5)  [101] -(flip)->   [010] (-5)
 - Two's complement   (5)  [101] -(flip)->  [010] + [001] = [011] (-5)

#### Побитови операции
прилагат върху един бит или набор от повече отделни битове на двоични числа

 - Побитово И (**&**)
 - Побитово ИЛИ  (**|**)
 - Побитово ИЗКЛЮЧВАЩО ИЛИ  (**^**)
 - Побитово отместване  (**<<** )     ( **>>**)

|        |           |
|--------|-----------|
| a      | 101010100 |
| b      | 100101110 |
| a&b    | 100000100 |
| a \| b | 101111110 |
| a^b    | 001111010 |
| a << 2 | 101010000 |
| a >> 2 | 001010101 |

Примери:

 - Функция, която с побитови операции проверява дали число е четно
 - Функция, която с побитови операции повдига 2 на степен k.

<h3>Задачи</h3>

**Задача 1:** Напишете функция, която приема число от в произволна бройна система и преобразува **директно** (без да минава през десетична) числото в друга произволна бройна система.

**Задача 2** Да се напише функция, която приема масив, в който всяко число се среща 2 пъти с изключение на едно число, което се среща веднъж.
Напишете функция, която приема такъв масив и връща кое е това число.
(Подсказка: използвайте побитови операции, за да постигнете линейно решение)

*Вход: [9 18 9 12 18 15 12], Изход: 15*


**Задача 3** Напишете функция, която приема цяло число и връща броя на 1-ците в двоичния му запис.

*Вход: 189,  Изход: 6*

**Задача 4 :** Напишете функция, която приема цяло число и обръща най-десният бит в него, който е единица.

*Вход: 12, Изход: 8*

*Вход: 15, Изход: 14*

**Задача 5:** Напишете функция, която по подадено цяло число n и цяло число k и връща числото, което е "закодирано" в последните k бита на n.

*Вход: 15 2, Изход: 3*

*Вход: 189 3, Изход: 5*

*Вход: 189 4, Изход: 13*

**Задача 6:** Напишете функция, която приема цяло число n и цяло число k и връща дали k в двоичен запис (разглеждайки го без водещите 0-ли) е част от двоичния запис на n.

*Вход: 15 3, Изход: true*

*Вход: 13 5 Изход: true*

*Вход: 13 7, Изход: false*

**Задача 7:** Напишете функция, която приема масив(разглеждаме го като множество) и отпечатва всички негови подмножества.

*Вход: [1, 2, 3], Изход: [], [1], [2], [3], [1,2], [2,3], [1,3], [1,2,3]*

*Вход: 13 5 Изход: true*

*Вход: 13 7, Изход: false*