Formule, conversii și tabele — foaia de cheat¶

Ce este acest fișier: tot ce trebuie calculat la examen, într-un singur loc. Cum îl folosești: printează-l sau ține-l deschis alături. Este pagina de recitit în ultimele 30 de minute înainte de examen.

Cuprins¶

Puterile lui 2
Sisteme de numerație: binar ↔ hexa ↔ zecimal
Complementul față de 2
Operatori pe biți
Subnetare IPv4
Memorie virtuală și paginare
Indexarea tablourilor
Sume utile și formule matematice
Recursivitate — șabloane rezolvate
Procese: fork și exec
Tabele de referință rapidă

1. Puterile lui 2¶

Cea mai rentabilă listă de memorat din tot examenul. Apare la subnetare, paginare, logaritmi, conversii.

n	2ⁿ	n	2ⁿ	n	2ⁿ
0	1	8	256	16	65 536
1	2	9	512	17	131 072
2	4	10	1 024 (1 K)	18	262 144
3	8	11	2 048	19	524 288
4	16	12	4 096 (4 K)	20	1 048 576 (1 M)
5	32	13	8 192	24	16 777 216
6	64	14	16 384	30	1 073 741 824 (1 G)
7	128	15	32 768	32	4 294 967 296

Prefixe binare: 2¹⁰ = 1 Ki · 2²⁰ = 1 Mi · 2³⁰ = 1 Gi · 2⁴⁰ = 1 Ti

Logaritm în bază 2 (rapid): ⌊log₂ x⌋ = exponentul celei mai mari puteri a lui 2 care este ≤ x.

Exemplu: 2¹⁰ = 1024 ≤ 2020 < 2048 = 2¹¹ ⇒ ⌊log₂ 2020⌋ = 10. ➜ Folosit direct la C6.

2. Sisteme de numerație: binar ↔ hexa ↔ zecimal¶

Tabelul fundamental — 1 cifră hexa = 4 biți¶

Hexa	Binar	Zecimal	Hexa	Binar	Zecimal
0	0000	0	8	1000	8
1	0001	1	9	1001	9
2	0010	2	A	1010	10
3	0011	3	B	1011	11
4	0100	4	C	1100	12
5	0101	5	D	1101	13
6	0110	6	E	1110	14
7	0111	7	F	1111	15

Binar → zecimal (metoda rapidă)¶

Nu aduna 16 puteri ale lui 2. Grupează în nibble-uri de câte 4 biți, de la dreapta, convertește în hexa, apoi hexa → zecimal.

1100 0110 1010 1110
 C    6    A    E     →  0xC6AE

0xC6AE = 12·4096 + 6·256 + 10·16 + 14
       = 49152 + 1536 + 160 + 14 = 50862

Puterile lui 16 (pentru hexa → zecimal)¶

16⁰	16¹	16²	16³	16⁴
1	16	256	4 096	65 536

Zecimal → binar¶

Împărțiri succesive la 2, resturile citite de jos în sus. Sau: scade cea mai mare putere a lui 2 care încape, repetat.

Verificări de plauzibilitate (economisesc timp)¶

Ce observi	Ce deduci
ultimul bit = 0	numărul este par
numărul are 16 biți și începe cu `11`	este între `0xC000 = 49152` și `0xFFFF = 65535`
ultimul nibble = `1110`	`numărul mod 16 = 14`
n biți, primul = 1	valoarea este în `[2ⁿ⁻¹, 2ⁿ − 1]`

3. Complementul față de 2¶

Modul în care se reprezintă numerele negative pe n biți.

Identitățile care contează¶

~x  =  −x − 1        ⟺        ~x  =  −(x + 1)
−x  =  ~x + 1

~x = −(x+1) este cea mai utilă formulă din tot capitolul C. ~87 = −88 · ~103 = −104 · ~0 = −1 · ~(−1) = 0

Conversia unui negativ în octet¶

Pe 8 biți, valoarea −N are reprezentarea binară a lui 256 − N:

−N	256 − N	Hexa	Binar
−1	255	0xFF	1111 1111
−76	180	0xB4	1011 0100
−88	168	0xA8	1010 1000
−90	166	0xA6	1010 0110
−104	152	0x98	1001 1000
−128	128	0x80	1000 0000

Generalizat: pe n biți, −N ⟶ 2ⁿ − N.

Promovarea întreagă¶

Orice char sau short devine int (32 de biți) înainte de o operație aritmetică sau pe biți.

unsigned char k = 0x57;   // 87
~k                        // → int: 0xFFFFFFA8 = -88, NU 0xA8

Dacă rezultatul se atribuie înapoi într-un unsigned char, contează doar ultimul octet.

Rețeta completă pentru `m &= ~k + c`¶

1.  ~k + c  =  -(k+1) + c            ← calculează ca întreg cu semn
2.  dacă rezultatul e negativ: octet = 256 - |rezultat|
3.  m AND octet                       ← bit cu bit, pe 8 biţi

Exemplu rezolvat (k = 87, m = 31, m &= ~k + 12):

~87 + 12 = -88 + 12 = -76
256 - 76 = 180 = 1011 0100
m = 31   =       0001 1111
             AND ─────────
                 0001 0100 = 20

➜ Folosit direct la C1.

4. Operatori pe biți¶

Operator	Nume	Regulă	Truc
`&`	AND	1 doar dacă ambii sunt 1	maschează (stinge biți)
`\\|`	OR	1 dacă cel puțin unul e 1	aprinde biți
`^`	XOR	1 dacă biții diferă	comută biți; `x^x = 0`
`~`	NOT	inversează toți biții	`~x = −(x+1)`
`<<`	shift stânga	`x << n` = `x · 2ⁿ`	înmulțire rapidă
`>>`	shift dreapta	`x >> n` = `x / 2ⁿ` (întreg)	împărțire rapidă

Idiomuri de recunoscut¶

Expresie	Ce face
`x & 1`	testează dacă `x` este impar
`x & (1 << k)`	testează bitul k
`x \\| (1 << k)`	setează bitul k
`x & ~(1 << k)`	șterge bitul k
`x ^ (1 << k)`	comută bitul k
`~(~0 << n)`	mască cu exact `n` biți de 1 la dreapta (= `(1 << n) − 1`)
`(x >> k) & mască`	extrage un câmp de biți
`(x >> (p+1-n)) & ~(~0 << n)`	`getbits` — extrage `n` biți din `x`, terminând la poziția `p`

➜ Folosit direct la C9.

5. Subnetare IPv4¶

Formulele¶

Mărime	Formulă
Total adrese în `/n`	`2^(32 − n)`
Adrese utilizabile	`2^(32 − n) − 2`
Adresa de rețea	prima din bloc (biți de host = 0)
Adresa de broadcast	ultima din bloc (biți de host = 1)
Interval utilizabil	`rețea + 1` … `broadcast − 1`
Pas (block size) pe octetul relevant	`256 − valoarea_octetului_din_mască`

Tabelul complet /8 → /30¶

CIDR	Mască	Total	Utilizabile	Pas
/8	255.0.0.0	16 777 216	16 777 214	–
/16	255.255.0.0	65 536	65 534	–
/21	255.255.248.0	2 048	2 046	8 (oct. 3)
/22	255.255.252.0	1 024	1 022	4 (oct. 3)
/23	255.255.254.0	512	510	2 (oct. 3)
/24	255.255.255.0	256	254	256
/25	255.255.255.128	128	126	128
/26	255.255.255.192	64	62	64
/27	255.255.255.224	32	30	32
/28	255.255.255.240	16	14	16
/29	255.255.255.248	8	6	8
/30	255.255.255.252	4	2	4

Algoritmul în 4 pași¶

1.  Pasul = 2^(32-n) (dacă n ≥ 24, este pasul pe ultimul octet)
2.  Blocurile încep la multipli ai pasului: 0, pas, 2·pas, …
3.  Găseşte blocul care conţine adresa dată
4.  reţea = începutul blocului
    broadcast = începutul + pas − 1
    utilizabile = reţea+1 … broadcast−1

Exemplu — 172.16.1.32/28:

pas = 2^(32-28) = 16
blocuri: .0  .16  .32  .48  .64 …
.32 este chiar începutul unui bloc
reţea      = 172.16.1.32
broadcast  = 172.16.1.32 + 16 − 1 = 172.16.1.47
utilizabile= 172.16.1.33 … 172.16.1.46   (14 adrese)

Sunt două adrese în aceeași subrețea?¶

Aplică AND între fiecare adresă și mască. Dacă rezultatele sunt identice → aceeași subrețea (ajunge un switch L2). Dacă nu → subrețele diferite (e nevoie de router L3).

Exemplu — 10.1.0.36 și 10.1.1.70:

Mască	AND octet 3	Rezultat	Concluzie
/24 (255)	`0 & 255 = 0` vs `1 & 255 = 1`	10.1.0.0 vs 10.1.1.0	diferite → L3
/25 (255 pe oct.3)	idem	10.1.0.0/25 vs 10.1.1.0/25	diferite → L3
/21 (248 pe oct.3)	`0 & 248 = 0` vs `1 & 248 = 0`	10.1.0.0/21 ambele	aceeași → L2

➜ Folosit direct la N3 și N21.

Lungimi de adrese¶

Adresă	Biți
IPv4	32
MAC	48
IPv6	128

6. Memorie virtuală și paginare¶

Formulele¶

Mărime	Formulă
Biți de offset	`log₂(dimensiune_pagină)`
Biți pentru numărul de pagină	`total_biți_adresă − biți_offset`
Nr. de intrări în tabela de pagini	`2^(biți_număr_pagină)`
Traducerea	`adr_fizică = frame · dim_pagină + offset`
Echivalent pe biți	`adr_fizică = (frame << biți_offset) \\| offset`

Biți de offset per dimensiune de pagină¶

Pagină	Biți offset	Cifre hexa de offset
256 B = 2⁸	8	2
512 B = 2⁹	9	–
1 KB = 2¹⁰	10	–
2 KB = 2¹¹	11	–
4 KB = 2¹²	12	3
8 KB = 2¹³	13	–
64 KB = 2¹⁶	16	4
4 MB = 2²²	22	–

Scurtătura hexazecimală¶

1 cifră hexa = 4 biți. Dacă offset-ul are 4k biți, ocupă exact ultimele k cifre hexa ale adresei.

Pagini de 4 KB (12 biţi offset)  →  ultimele 3 cifre hexa

adresă virtuală  0x305B
                   ▲ ▲▲▲
                   │ └┴┴── offset = 0x05B   (rămâne NESCHIMBAT)
                   └────── pagina = 0x3     (se caută în tabelă)

tabela: pagina 0x3 → frame 0x9

adresă fizică = 0x9 05B = 0x905B

Rețeta în 10 secunde: taie ultimele 3 cifre hexa → caută restul în tabelă → lipește cadrul la loc.

➜ Folosit direct la S6.

7. Indexarea tablourilor¶

Formula generală (row-major)¶

Pentru T a[D1][D2][D3]:

index_liniar( a[i][j][k] )  =  i·(D2·D3)  +  j·D3  +  k

Regula: fiecare indice se înmulțește cu produsul dimensiunilor care îl urmează.

Pentru 2D, T a[D1][D2]: index = i·D2 + j Pentru 4D: index = i·(D2·D3·D4) + j·(D3·D4) + k·D4 + l

Aritmetica pe pointeri¶

a[i]  ≡  *(a + i)
dacă p = &a[k]   atunci   p[j] == a[k + j]

p + 1 avansează cu un element (sizeof(tip) octeți), nu cu un octet.

Combinația de examen¶

1.  index = i·D2·D3 + j·D3 + k          ← poziţia lui &a[i][j][k]
2.  index_total = index + offset         ← din aptr[offset]
3.  valoare = contor_iniţial − index_total   ← dacă bucla face contor--

Exemplu — int a[24][45][17], umplut cu contor-- de la 20019, aptr = &a[19][17][11], se cere aptr[31]:

index = 19·(45·17) + 17·17 + 11 = 19·765 + 289 + 11 = 14835
index_total = 14835 + 31 = 14866
valoare = 20019 − 14866 = 5153

➜ Folosit direct la C3.

8. Sume utile și formule matematice¶

Formulă	Rezultat
`1 + 2 + … + k`	`k(k+1) / 2`
`1² + 2² + … + k²`	`k(k+1)(2k+1) / 6`
`1³ + 2³ + … + k³`	`[k(k+1)/2]²`
`2² + 4² + … + (2k)²`	`4 · k(k+1)(2k+1)/6`
`1 + 3 + 5 + … + (2k−1)`	`k²`
`1 + 2 + 4 + … + 2ⁿ`	`2ⁿ⁺¹ − 1`
Nr. de termeni în `a, a+p, …, b`	`(b − a)/p + 1`

Valori pre-calculate utile:

k	`k(k+1)(2k+1)/6`
10	385
25	5 525
50	42 925
100	338 350

Exemplu rezolvat — suma pătratelor pare până la 100:

2² + 4² + … + 100² = 4 · (1² + … + 50²) = 4 · 42925 = 171700
2 · 171700 = 343400

➜ Folosit direct la C21.

9. Recursivitate — șabloane rezolvate¶

Șablon	Ce calculează	Formula
`f(x) = (x==1) ? 0 : 1 + f(x/2)`	de câte ori împart la 2 până la 1	`⌊log₂ x⌋`
`f(x) = (x==0) ? 0 : c + f(x/10)`	numără cifrele, adunând `c`	`c × nr_cifre`
`f(x)` cu `c₁` la cifră pară / `c₂` la impară	numără paritatea cifrelor	`c₁·nr_pare + c₂·nr_impare`
`f(a,b) = (a==b) ? V : c + f(a+p, b−p)`	pași până la întâlnire	`nr_pași = (b−a)/(2p)`; rezultat = `V + c·nr_pași`
`f(n) = 0 dacă n==0, altfel g(n) + f(n−1)`	sumă de la 1 la n	`Σ g(i)`

Metoda în 3 pași¶

1.  CAZ DE BAZĂ:  când se opreşte?
2.  PAS:          cum se apropie argumentul de caz de bază?
3.  NUMĂRĂ:       câţi paşi × cât se adaugă la fiecare

Nu desfășura lanțul de apeluri

Dacă are mai mult de ~10 pași. Caută tiparul. Verifică divizibilitatea la șablonul cu doi parametri: dacă (b−a) nu e divizibil cu 2p, condiția a == b nu se atinge niciodată. x % 2 depinde doar de ultima cifră zecimală — util când recursia face x / 10.

10. Procese: `fork` și `exec`¶

Situație	Rezultat
`n` apeluri `fork()` necondiționate, în serie	`2ⁿ` procese (inclusiv cel inițial)
`fork()` într-o buclă de `n` iterații	`2ⁿ` procese
`execve()` reușit	nu se mai întoarce — codul de după nu se execută
`execve()` eșuat	returnează `−1`, execuția continuă
`for` fără acolade	cuprinde o singură instrucțiune

n	`2ⁿ`
1	2
2	4
3	8
4	16
5	32

➜ Folosit direct la S4.

11. Tabele de referință rapidă¶

Porturi¶

Port	Serviciu	Port	Serviciu
20/21	FTP	67/68	DHCP srv/client
22	SSH	69	TFTP
23	Telnet	80	HTTP
25	SMTP	110/143	POP3/IMAP
53	DNS	161/162	SNMP
		443	HTTPS

Câmpul Protocol din IPv4¶

1	6	17	50	51
ICMP	TCP	UDP	ESP	AH

Nivelurile OSI¶

7	6	5	4	3	2	1
Aplicație	Prezentare	Sesiune	Transport	Rețea	Legătură	Fizic
HTTP, DNS	TLS	–	TCP/UDP · port	IP · adresă IP · router	Ethernet · MAC · switch	biți

Specificatori `printf`¶

`%d`	`%c`	`%s`	`%f`	`%lf`	`%u`	`%x`	`%p`
int	char	șir	float	double	unsigned	hexa	pointer

Permisiuni Linux (octal)¶

7	6	5	4	3	2	1	0
`rwx`	`rw-`	`r-x`	`r--`	`-wx`	`-w-`	`--x`	`---`

r = 4 · w = 2 · x = 1 · ordinea cifrelor: proprietar · grup · alții

Dimensiuni de tipuri în C¶

`char`	`short`	`int`	`long long`	`float`	`double`	pointer (64-bit)
1 B	2 B	4 B	8 B	4 B	8 B	8 B

Ultimele 5 minute — ce recitești¶

2^10 = 1024        2^12 = 4096         ~x = -(x+1)
/28 → 16 adrese, 14 utilizabile        -N pe 8 biţi = 256-N
443 = HTTPS        53 = DNS            67/68 = DHCP
Protocol 50 = ESP  1 = ICMP  6 = TCP  17 = UDP
DORA: Discover-Offer-Request-Ack       OFFER = primul PRIMIT
MAC se schimbă la fiecare hop, IP rămâne
n × fork() = 2^n   execve reuşit nu se întoarce
9/4 = 2 (împărţire întreagă)
strlen = până la \0   |   sizeof = tot tabloul
chmod 700 = doar proprietarul, drepturi depline
/etc = configurări   /var/log = jurnale   ss -uln = UDP listening numeric
Tip 1 = bare metal   Tip 2 = hosted

Limbajul C · Index · ➡ Simulare examene

Formule, conversii și tabele — foaia de cheat¶

Cuprins¶

1. Puterile lui 2¶

2. Sisteme de numerație: binar ↔ hexa ↔ zecimal¶

Tabelul fundamental — 1 cifră hexa = 4 biți¶

Binar → zecimal (metoda rapidă)¶

Puterile lui 16 (pentru hexa → zecimal)¶

Zecimal → binar¶

Verificări de plauzibilitate (economisesc timp)¶

3. Complementul față de 2¶

Identitățile care contează¶

Conversia unui negativ în octet¶

Promovarea întreagă¶

Rețeta completă pentru m &= ~k + c¶

4. Operatori pe biți¶

Idiomuri de recunoscut¶

5. Subnetare IPv4¶

Formulele¶

Tabelul complet /8 → /30¶

Algoritmul în 4 pași¶

Sunt două adrese în aceeași subrețea?¶

Lungimi de adrese¶

6. Memorie virtuală și paginare¶

Formulele¶

Biți de offset per dimensiune de pagină¶

Scurtătura hexazecimală¶

7. Indexarea tablourilor¶

Formula generală (row-major)¶

Aritmetica pe pointeri¶

Combinația de examen¶

8. Sume utile și formule matematice¶

9. Recursivitate — șabloane rezolvate¶

Metoda în 3 pași¶

10. Procese: fork și exec¶

11. Tabele de referință rapidă¶

Porturi¶

Câmpul Protocol din IPv4¶

Nivelurile OSI¶

Specificatori printf¶

Permisiuni Linux (octal)¶

Dimensiuni de tipuri în C¶

Ultimele 5 minute — ce recitești¶

Rețeta completă pentru `m &= ~k + c`¶

10. Procese: `fork` și `exec`¶

Specificatori `printf`¶