Найдите все степени двойки, меньшие или равные заданному числу

Опубликовано: 1 Января, 2022

Учитывая положительное число N , задача состоит в том, чтобы найти все совершенные степени двойки, которые меньше или равны заданному числу N.

Примеры:

Input: N = 63
Output: 32 16 8 4 2 1
Explanation:
There are total of 6 powers of 2, which are less than or equal to the given number N.
Input: N = 193
Output: 128 64 32 16 8 4 2 1
Explaination:
There are total of 8 powers of 2, which are less than or equal to the given number N.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: идея состоит в том, чтобы пройти каждое число от N до 1 и проверить, является ли оно идеальной степенью 2 или нет. Если да, то распечатайте это число.

Другой подход: идея состоит в том, чтобы найти все степени двойки и просто вывести степени, которые меньше или равны N.

Другой подход: идея основана на концепции, согласно которой для всех степеней двойки все биты установлены в двоичной форме. Функция Bitset, используемая в этом подходе, решает указанную выше проблему. Ниже приведены шаги:

Найдите наибольшую степень двойки (скажем, temp ), которая используется для вычисления числа, меньшего или равного N.
Инициализировать битовый массив arr [] максимального размера 64 для хранения двоичного представления заданного числа N.
Сбросьте все биты в массиве битов с помощью функции reset ().
Итерируйте цикл от общего числа до 0 и последовательно сделайте каждый бит 1 , найдите значение этого двоичного выражения и затем сбросьте бит.

Ниже представлена реализация описанного выше подхода:

 // C++ program for the above approach
 
#include <bits/stdc++.h>
 using namespace std;
 const int MAX = 64;
 
// Function to return max exponent of
 // 2 which evaluates a number less
 // than or equal to N
 int max_exponent( int n)
 {
    return ( int )(log2(n));
 }
 
// Function to print all the powers
 // of 2 less than or equal to N
 void all_powers( int N)
 {
    bitset<64> arr(N);
 
    // Reset all the bits
    arr.reset();
 
    int total = max_exponent(N);
 
    // Iterate from total to 0
    for ( int i = total; i >= 0; i--) {
 
        // Reset the next bit
        arr.reset(i + 1);
 
        // Set the current bit
        arr.set(i);
 
        // Value of the binary expression
        cout << arr.to_ulong() << " " ;
    }
 }
 
// Driver Code
 int main()
 {
    // Given Number
    int N = 63;
 
    // Function Call
    all_powers(N);
    return 0;
 }

Выход:

32 16 8 4 2 1

Сложность времени: O (log N)
Вспомогательное пространство: O (1)

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Олимпиады по программированию Алгоритмы

Найдите все степени двойки, меньшие или равные заданному числу

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

РЕКОМЕНДУЕМЫЕ СТАТЬИ