🔢 Бройни Системи (Numeral Systems)
Бройните системи са начин за представяне на числа чрез символи. Компютрите работят в двоична система, но програмистите често използват шестнайсетична. Разбирането на бройните системи е ключово за работа с битови операции, оптимизация на паметта и решаване на различни олимпиадни задачи.
1. Основни Системи
1.1. Десетична Система (Decimal, Base 10)
Това е системата, която използваме в ежедневието. Използва 10 цифри: 0-9. * Пример: \(123 = 1 · 10^2 + 2 · 10^1 + 3 · 10^0 = 100 + 20 + 3\) * Всяка позиция представлява степен на 10 (единици, десетици, стотици и т.н.)
1.2. Двоична Система (Binary, Base 2)
Основната система за компютрите. Използва само 2 цифри: 0 и 1 (битове). * Пример: \(1011_2 = 1 · 2^3 + 0 · 2^2 + 1 · 2^1 + 1 · 2^0 = 8 + 0 + 2 + 1 = 11_{10}\) * Всеки бит представлява степен на 2 * Широко използвана за битови маски и флагове
1.3. Осмична Система (Octal, Base 8)
Използва 8 цифри: 0-7. Често се среща в Unix файлови права (permissions).
* Пример: \(752_8 = 7 · 8^2 + 5 · 8^1 + 2 · 8^0 = 448 + 40 + 2 = 490_{10}\)
* В C++ осмичните числа се пишат с префикс 0: 0752
1.4. Шестнайсетична Система (Hexadecimal, Base 16)
Използва 16 символа: 0-9 и A-F (където A=10, B=11, C=12, D=13, E=14, F=15).
* Пример: \(1A3_{16} = 1 · 16^2 + 10 · 16^1 + 3 · 16^0 = 256 + 160 + 3 = 419_{10}\)
* Компактно представяне на двоични данни (1 hex цифра = 4 бита)
* В C++ hex числата се пишат с префикс 0x: 0x1A3
* Широко използвана за цветове в web (напр. #FF5733), адреси в паметта
2. Преобразуване Между Бройни Системи
2.1. От Десетична към База \(K\)
Използваме деление с остатък - класическият алгоритъм.
Алгоритъм: 1. Делим числото на \(K\). 2. Записваме остатъка (това е последната цифра в новата база). 3. Повтаряме с частното, докато стане 0. 4. Резултатът е записаните остатъци в обратен ред.
Пример: 156₁₀ → база 16
Имплементация с поддръжка на отрицателни числа:
string toBase(long long n, int base) {
if (n == 0) return "0";
string chars = "0123456789ABCDEF";
string res = "";
bool negative = n < 0;
n = abs(n);
while (n > 0) {
res += chars[n % base];
n /= base;
}
if (negative) res += '-';
reverse(res.begin(), res.end());
return res;
}
// Примери на използване:
// toBase(255, 2) -> "11111111"
// toBase(255, 16) -> "FF"
// toBase(64, 8) -> "100"
// toBase(-42, 2) -> "-101010"
2.2. От База \(K\) към Десетична
Използваме схема на Хорнер или просто сумиране на степените.
Пример: 1A₁₆ → десетична
Метод 1: Сумиране на степените (отдясно наляво)
long long toDec(string s, int base) {
long long res = 0;
long long power = 1;
for (int i = s.length() - 1; i >= 0; i--) {
int digit;
if (isdigit(s[i]))
digit = s[i] - '0';
else
digit = toupper(s[i]) - 'A' + 10;
res += digit * power;
power *= base;
}
return res;
}
Метод 2: Схема на Хорнер (отляво надясно) - по-ефективна
long long toDecHorner(string s, int base) {
long long res = 0;
for (char c : s) {
int digit;
if (isdigit(c))
digit = c - '0';
else
digit = toupper(c) - 'A' + 10;
res = res * base + digit; // Схема на Хорнер
}
return res;
}
// Вградена функция в C++:
long long val = stoll(s, nullptr, base); // base от 2 до 36
Примери:
2.3. Директно Преобразуване Между Произволни Бази
// Преобразуване от база A към база B чрез десетична
string convertBase(string num, int fromBase, int toBase) {
// Стъпка 1: От fromBase към десетична
long long decimal = toDecHorner(num, fromBase);
// Стъпка 2: От десетична към toBase
return toBase(decimal, toBase);
}
// Пример: convertBase("FF", 16, 2) -> "11111111"
3. Бързи Преобразувания Между Степени на 2
Между бази, които са степени на 2 (\(2^1=2, 2^3=8, 2^4=16\)), може да се преобразува директно чрез групиране на битове, без да минаваме през десетична система.
3.1. Двоична → Шестнайсетична (2 → 16)
Групираме по 4 бита отдясно наляво (защото \(2^4 = 16\)).
Пример:
Таблица за преобразуване:
0000₂ = 0₁₆ 0100₂ = 4₁₆ 1000₂ = 8₁₆ 1100₂ = C₁₆
0001₂ = 1₁₆ 0101₂ = 5₁₆ 1001₂ = 9₁₆ 1101₂ = D₁₆
0010₂ = 2₁₆ 0110₂ = 6₁₆ 1010₂ = A₁₆ 1110₂ = E₁₆
0011₂ = 3₁₆ 0111₂ = 7₁₆ 1011₂ = B₁₆ 1111₂ = F₁₆
3.2. Шестнайсетична → Двоична (16 → 2)
Всяка hex цифра става точно 4 бита.
Пример:
3.3. Двоична → Осмична (2 → 8)
Групираме по 3 бита отдясно наляво (защото \(2^3 = 8\)).
Пример:
3.4. Осмична → Двоична (8 → 2)
Всяка осмична цифра става точно 3 бита.
Пример:
4. Работа с Бройни Системи в C++
4.1. Манипулатори за Вход/Изход
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
int x = 255;
// Изход в различни бази
cout << dec << x << endl; // 255 (десетична)
cout << hex << x << endl; // ff (шестнайсетична, малки букви)
cout << uppercase << hex << x << endl; // FF (големи букви)
cout << oct << x << endl; // 377 (осмична)
// Показване на префикса (0x за hex, 0 за oct)
cout << showbase << hex << x << endl; // 0xff
cout << oct << x << endl; // 0377
// Връщане към десетична система (важно!)
cout << dec << x << endl; // 255
// Четене в различни бази
int a, b, c;
cin >> hex >> a; // Очаква hex вход (напр. FF)
cin >> oct >> b; // Очаква oct вход (напр. 377)
cin >> dec >> c; // Връща към десетична (напр. 255)
return 0;
}
4.2. Префикси за Литерали
int decimal = 42; // Десетична
int binary = 0b101010; // Двоична (C++14 и по-нови)
int octal = 052; // Осмична (префикс 0)
int hex = 0x2A; // Шестнайсетична (префикс 0x)
// Всички са равни на 42₁₀
4.3. Функции за Преобразуване
#include <string>
#include <bitset>
// String към число в различни бази
int num1 = stoi("101010", nullptr, 2); // от двоична
int num2 = stoi("52", nullptr, 8); // от осмична
int num3 = stoi("2A", nullptr, 16); // от hex
long long num4 = stoll("FFFF", nullptr, 16); // за по-големи числа
// Число към string
string bin = bitset<8>(42).to_string(); // "00101010"
// Използване на stringstream
#include <sstream>
stringstream ss;
ss << hex << 255;
string hexStr = ss.str(); // "ff"
5. Практически Приложения и Типични Задачи
5.1. Проверка Дали Число е Валидно в База K
bool isValidInBase(string num, int base) {
for (char c : num) {
int digit;
if (isdigit(c))
digit = c - '0';
else
digit = toupper(c) - 'A' + 10;
// Цифрата трябва да е по-малка от базата
if (digit >= base) return false;
}
return true;
}
// isValidInBase("189", 8) -> false (9 >= 8)
// isValidInBase("177", 8) -> true
5.2. Намиране на Сумата на Цифрите в База K
int digitSum(long long n, int base) {
int sum = 0;
while (n > 0) {
sum += n % base;
n /= base;
}
return sum;
}
// digitSum(255, 10) -> 2+5+5 = 12
// digitSum(255, 16) -> F+F = 15+15 = 30
5.3. Палиндром в Различни Бази
bool isPalindromeInBase(long long n, int base) {
string repr = toBase(n, base);
string rev = repr;
reverse(rev.begin(), rev.end());
return repr == rev;
}
// 585₁₀ = 1001001001₂ (палиндром в двоична)
// 45₁₀ = 2D₁₆ (не е палиндром в hex)
5.4. Броене на Единици в Двоично Представяне
// Метод 1: Чрез конвертиране към string
int countOnes_v1(long long n) {
return __builtin_popcountll(n); // Вградена функция
}
// Метод 2: Ръчно броене
int countOnes_v2(long long n) {
int count = 0;
while (n > 0) {
count += n % 2;
n /= 2;
}
return count;
}
// Метод 3: Brian Kernighan's Algorithm (най-бърз)
int countOnes_v3(long long n) {
int count = 0;
while (n) {
n &= (n - 1); // Премахва най-десния 1 бит
count++;
}
return count;
}
6. Важни Граници и Edge Cases
6.1. Препълване (Overflow)
// ВНИМАНИЕ: Препълване при големи числа!
string binary = "1111111111111111111111111111111111111111111111111111111111111111"; // 64 единици
// Това не може да се побере в long long (64 бита)!
// Решение 1: Използване на unsigned long long
unsigned long long maxULL = ULLONG_MAX; // 2^64 - 1
// Решение 2: BigInteger библиотека или string операции
// Решение 3: Работа само със string представяне без конвертиране към число
6.2. Специални Случаи
// Нула в различни бази
toBase(0, 2) -> "0"
toBase(0, 16) -> "0"
// Отрицателни числа (трябва специална обработка)
toBase(-15, 2) -> "-1111"
// Водещи нули се игнорират
toDec("007", 8) == toDec("7", 8) // true
// Проверка за валидност
isValidInBase("1G9", 16) -> false (G е валидно, но след него не може 9... всъщност може!)
isValidInBase("1Z9", 16) -> false (Z > F, невалидно)
6.3. Бази Извън Стандартните
// База 36 - използва 0-9 и A-Z
string base36 = toBase(1000000, 36); // "LFLS"
// База 62 - използва 0-9, A-Z, a-z (често за URL shortening)
// Изисква разширена chars таблица: "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
7. Оптимизационни Трикове
7.1. Бързо Удвояване и Деление на 2 в Двоична
// Вместо n * 2 използвайте битов shift
int doubled = n << 1; // Умножение по 2
// Вместо n / 2
int halved = n >> 1; // Деление на 2
// Проверка дали числото е четно
bool isEven = (n & 1) == 0; // По-бързо от n % 2 == 0
7.2. Бързо Повдигане на Степен на 2
// Проверка дали n е степен на 2
bool isPowerOf2 = (n > 0) && ((n & (n - 1)) == 0);
// Намиране на следващата степен на 2
int nextPowerOf2(int n) {
n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return n + 1;
}
8. Задачи за Практика
8.1. Олимпиадни Задачи
- Codeforces 492C: Vanya and Exams (изисква long long).
- UVa 10018: Reverse and Add (палиндроми в различни бази).
- SPOJ ADDREV: Adding Reversed Numbers.
- Codeforces 1017C: The Phone Number (работа с цифри).
- AtCoder ABC192 - C: All 4-digit Numbers (генериране в бази).
8.2. Класически Проблеми
- Преобразуване на IP адрес (4 байта ↔ 32-битово число)
- RGB към hex и обратно (#FF5733 ↔ rgb(255, 87, 51))
- Base64 encoding/decoding (база 64 с специална таблица)
- Проверка на ISBN/Barcode (специфични алгоритми с модулни операции)
🏁 Заключение
Ключови точки за запомняне:
* Винаги проверявайте за препълване при работа с големи числа
* За числа над 64 бита използвайте BigInteger библиотека или работете със string
* Бази степени на 2 (2, 4, 8, 16) позволяват директни преобразувания без десетична система
* Битовите операции са много по-бързи от аритметичните за степени на 2
* Внимавайте с водещи нули в осмична система (0777 != 777)
* При конкурси използвайте вградените функции (stoll, bitset, манипулатори) за по-малко грешки
Съвети за олимпиади:
* Четете внимателно условието - коя база се използва по подразбиране
* Винаги тествайте с граничните случаи: 0, 1, максимално число
* При съмнение използвайте long long вместо int
* Помнете че unsigned типовете могат да съхраняват 2× по-големи положителни числа