Начин за представяне на числата посредством дадена азбука.
| Двоична (binary) | Десетична (decimal) | Шестнайсетична (hexadecimal) | |
|---|---|---|---|
| Aзбука | 0-1 | 0-9 | 0-F (0-9 & A-F) |
| Основа | 2 | 10 | 16 |
| Десетична (decimal) | Двоична (binary) | осмична (octal) | Шестнайсетична (hexadecimal) |
|---|---|---|---|
| 00 | 00000 | 00 | 00 |
| 01 | 00001 | 01 | 01 |
| 02 | 00010 | 02 | 02 |
| 03 | 00011 | 03 | 03 |
| 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 |
- Алгоритъм за преобразуване от произволна бройна система в дестична бройна система.
- Алгоритъм за преобразуване от десетична бройна система в произволна бройна система.
Прилагат върху един бит или набор от повече отделни битове на двоични числа.
| Operator | Description |
|---|---|
| << | Bitwise left shift | Побитово отместване наляво |
| >> | Bitwise right shift | Побитово отместване надясно |
| & | Bitwise AND | Побитово И |
| | | Bitwise OR | Побитово ИЛИ |
| ~ | Bitwise NOT | Побитово НЕ |
| ^ | Bitwise XOR | Побитово ИЗКЛЮЧВАЩО ИЛИ |
| a | b | a & b | a | b | a ^ b | a << 2 | a >> 2 | ~a | ~b |
|---|---|---|---|---|---|---|---|---|
| 101010100 | 100101110 | 100000100 | 101111110 | 001111010 | 101010000 | 001010101 | 010101011 | 011010001 |
Примери:
-
Функция, която с побитови операции проверява дали число е четно
-
Функция, която с побитови операции повдига 2 на степен k.
-
Проверка на бит
-
Изчистване на бит (да стане 0)
-
Вдигане на бит (да стане 1)
-
Слагане на подадена стойност на бит.
-
Toggle (обръщане) на бит
- Най-левият бит (MSB - Most significant bit) е резервиран за знака на числото: 1, ако числото е отрицателно, и 0 - иначе. За да се опростят и оптимизират аритметичните операции и тези са сравнение, се използва една от следните системи:
-
- One's complement (5) [101] -(flip)-> [010] (-5)
-
- Two's complement (5) [101] -(flip)-> [010] + [001] = [011] (-5)
- Статия
Повечето модерни компилатори използват 2's compliment, защото 1's compliment има проблем - поддържа положителна и отрицателна нула. Аритметичните операции също са по-лесни, използвайки
Задача 1: Да се напише функция, която приема масив, в който всяко число се среща 2 пъти с изключение на едно число, което се среща веднъж. Напишете функция, която приема такъв масив и връща кое е това число. (Подсказка: използвайте побитови операции, за да постигнете линейно решение)
Вход: [9 18 9 12 18 15 12], Изход: 15
Задача 2: Напишете функция, която приема масив(разглеждаме го като множество) и отпечатва всички негови подмножества.
Вход: [1, 2, 3], Изход: [], [1], [2], [3], [1,2], [2,3], [1,3], [1,2,3]
Вход: [5, 3] Изход: [], [5], [3], [5, 3]
От интервю: Да се напише функция, която проверява дали число е степен на двойката. Да работи да константно време.