Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

Verifică dacă un număr dat este o putere de 2 în C++

Dându-se un număr natural n, să se verifice dacă este sau nu o putere de a lui 2.

Exemplu. Pentru n = 16, răspunsul este DA. În schimb, pentru n = 3, răsunsul este NU.

Explicarea algoritmului

Pentru a verifica dacă un număr este sau nu o putere de 2, ne vom folosi de proprietățile biților. Mai precis, un număr putere de 2 are un singur bit de 1 în reprezentarea sa binară, restul cifrelor fiind de 0 (similar cum o putere de a lui 10 în baza 10 are o singură cifră de 1, restul de 0: 1, 10, 100, 1000, …). Așadar, vom căuta un bit de 1 din numărul n, și vom verifica dacă acel bit este egal sau nu cu n. Dacă acel bit este egal cu n, atunci n nu mai are alți biți de 1, așadar n este putere de 2. În caz contrar, n nu va fi putere de 2.

Poți citi acest articol pentru mai multe detalii despre parcurgerea biților.

Implementare în C++

Metoda 1 (parcurgerea biților pe rând)

Parcurgem cu o structură repetitivă de tip for biții lui n, de la ultimul bit către primul, iar primul bit de 1 întâlnit îl vom verifica dacă este egal cu n (după cum am menționat mai sus).

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim numărul nostru, n
    int n;
    cin >> n;

    //Căutăm primul bit de 1 din n
    int amGasit = 0;
    for(int i = 1; i <= n; i *= 2) {
        if(i & n) { //Am găsit un bit de 1
            if(i == n) { //Numărul n nu mai are alți biți de 1
                amGasit = 1;
                cout << "DA";
            }
            break; //Ne oprim după primul bit de 1 întâlnit
        }
    }
    if(amGasit == 0) { //Dacă nu am găsit o soluție (ori n = 0, ori n are mai mulți biți de 1)
        cout << "NU";
    }
    return 0;
}

Metoda 2 (instant)

Vom folosi o proprietate interesantă: dacă n este puterea 2^k, atunci n - 1 va avea ultimii k biți egali cu 1, restul egali cu 0. Astfel, aplicând AND între n și n - 1, vom obține 0, dacă și numai dacă n este o putere de a lui 2.

Există un caz particular, când n = 0. Îl vom trata separat.

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim numărul nostru, n
    int n;
    cin >> n;

    //Determinăm dacă n este o putere de a lui 2
    if(n == 0) { //Caz particular, când nu putem calcula n - 1
        cout << "NU"; 
    } else if(n & (n - 1)) { 
        cout << "NU";
    } else {
        cout << "DA";
    }
    return 0;
}

Alte resurse și bibliografie

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Interclasarea a doi vectori în C++Cea mai lungă secvență de elemente crescătoare în C++Cifra maximă a unui număr recursiv în C++Generarea șirului Fibonacci generalizat în C++Șirul lui Fibonacci în C++Verifică dacă un caracter este literă în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Ce este o variabilă unsigned în C++?Materia pentru olimpiada de informatică - tot ce trebuie să știiComplexitatea unui algoritm (timp și spațiu) în C++Algoritm recursiv pentru căutare binară (clasa a X-a)Matrice pătratice în C++. Diagonala principală și secundarăCitește un șir de caractere cu spații în C++Operații cu numere mari în C++ - Toate funcțiile explicateCe înseamnă variabilă globală și locală în C++?Ce înseamnă endl în C++?Căutare binară în C++Verificare dacă un număr este palindrom în C++Radicalul unui număr în C++ (rădăcina pătrată)Suma numerelor naturale dintr-un interval dat în C++Numărul combinărilor în C++ (formula combinărilor)Inversarea unui vector în C++Verifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Verifică dacă trei puncte sunt coliniare C++Combinatorică în C++: permutări, aranjamente, combinări și alteleRădăcina cubică a unui număr în C++ (cube root)Copiuțe: Cifrele unui numărAl N-lea termen dintr-o progresie geometricăRecursivitate în C++Vectorii în C++: declarare și parcurgereNumărul de divizori al unui număr în C++Suma elementelor unui vector recursiv în C++Verificarea unui an bisect în C++Verifică dacă un număr dat este o putere de 2 în C++Distanța dintre două puncte în C++Verifică dacă un număr aparține șirului Fibonacci în C++Pointer în C++. Variabile de tipul char * (char steluță)Verifică dacă un caracter este cifră în C++Valoarea absolută (modulul) unui număr în C++Cum să calculezi instant 2 la puterea N în C++Interschimbarea a două variabile în C++ (3 metode)Maximul și minimul unui vector în C++Vectori de frecvență (de apariții) în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Numărul de apariții al unui număr într-un vector în C++Instrucțiunea de decizie în C++: if, else, switch, caseCel mai semnificativ bit în C++Comentarii în C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Funcții predefinite în C++ (matematice, șiruri de caractere)Numărul aranjamentelor în C++ (formula aranjamentelor)Tipuri de date în C++: numere întregi, reale, caractere și alteleVectorii în C++: citire și afișareCalculul combinărilor de n luate câte k (nCk) în C++Aflarea sumei primelor N sume GaussMatrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicCe este o funcție void în C++?Verifică dacă un număr este par sau impar fără modulo în C++Cel mai frecvent element dintr-un șir în C++Mediana unui șir de valori în C++Află secolul unui an citit de la tastatură în C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăVerifică dacă o literă este vocală în C++Maximul și minimul a trei valori în C++Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Transformarea unui număr din baza 10 în baza 2 în C++Numărul permutărilor în C++ (formula permutărilor)Cum să afișezi partea întreagă a unui număr real în C++Verificare dacă șir de caractere este palindrom în C++Inversarea unui șir de caractere în C++Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortDivide et Impera (metodă de programare C++)Afișarea divizorilor primi ai unui număr în C++Numere triunghiulare. Verificarea unui număr triunghiularSuma divizorilor unui număr în C++Instrucțiunea for (structuri repetitive)Tipul struct în C++. Ce sunt structurile de date neomogeneCel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Al N-lea termen Fibonacci în C++Indicatorul lui Euler în C++Cifra maximă și minimă a unui număr în C++Structuri repetitive (while, do while, for, etc)Factorialul unui număr în C++Oglinditul recursiv al unui număr în C++Tutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Numărul de cifre ale factorialului unui numărBordarea unei matrice în C++De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Instrucțiunea break (structuri repetitive)Instrucțiunea continue (structuri repetitive)Matrice în C++. Declararea și parcurgerea tablourilor bidimensionaleAplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorNumărul de divizori primi ai unui număr în C++Numărul minim de peroane pentru o gară în C++Ciurul lui Eratostene în C++Instrucțiunea while (structuri repetitive)Instrucțiunea do while (structuri repetitive)Numărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Cel mai mic număr cu suma cifrelor N în C++Verificare număr prim în C++ (Clasa a IX-a)Prima cifră a unui număr în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Maximul și minimul a n valori în C++Oglinditul unui număr în C++Do while vs while în C++ - Care e diferența?CMMDC recursiv a două numere naturale în C++Verifică dacă o literă este mică sau mare în C++Codul ASCII (tabel complet)Câte numere naturale sunt într-un interval dat? (C++)Funcții în C++. Ce sunt subprogrameleTransformarea unei litere mari în literă mică în C++Afișarea elementelor unui vector recursiv în C++Aria și circumferința unui cerc în C++Aria unui triunghi folosind coordonatele acestora în C++Șiruri de caractere în C++. Tot ce trebuie să știiCitirea și afișarea matricelor în C++Cum să citești și să afișezi în fișiere în C++Al N-lea termen dintr-o progresie aritmeticăCifra de control a unui numărSuma 1 + 2 + 3 + ... + N în C++Transformarea unui număr din baza 2 în baza 10 în C++Maximul și minimul a două valori în C++Cel mai puțin semnificativ bit în C++Transformarea unei litere mici în literă mare în C++

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont