Сила на две Leetcode разтвор  


Ниво на трудност Лесно
Често задавани в ябълка
алгоритми Манипулация на битове Bits кодиране Интервю интерпретация LeetCode LeetCodeSolutions Математически

Дадено ни е цяло число и целта е да се провери дали цялото число е степен на две, тоест може да се представи като някаква цялостна степен на '2'.

Сила на две решения с Leetcodeщифт

Пример  

16
Yes
13
No

Подход  

Тривиално решение може да бъде: Проверете дали всички основни фактори на цялото число са всички '2". Сложността във времето на този метод ще бъде O (log2N). За да го направим по оптимален начин, можем да се възползваме от битови манипулации.

„Всяко число, което е степен на две, може да има само един бит, зададен в двоично представяне“

Как може да се провери дали има само набор от единични битове в двоична форма?

Помислете за всяко число, x.

Сега, ако x е степен на две, тогава (х - 1) ще изключи всички десни битове към зададения бит (задайте ги като „0“) и зададеният бит ще бъде деактивиран.

x = 8 [1000], x - 1 = 7 [0111]

Така че, използвайки BITWISE-AND на x и (x - 1), можем да кажем, ако числото е степен на две, тогава, x & (x - 1) = 0

Алгоритъм (тривиален)  

  1. Продължавайте да разделяте числото на "2" докато не се дели на "2" вече.
  2. Ако броят е равен на „1“:
    • Цялото число е степен на две
  3. Още
    • Цялото число не е степен на две
Вижте също
Сила на четири Leetcode разтвор

Алгоритъм (битово манипулиране)  

  1. Проверете дали x & (x - 1) е равно на нула
    • Ако да, числото е степен 2
    • Цялото число не е степен на 2, в противен случай

изпълнение  

C ++ програма за мощност на две Leetcode Solution

Наивен метод

#include <bits/stdc++.h>
using namespace std;

bool powerOfTwo(int n)
{
    while(n % 2 == 0)
        n /= 2;
    return (n == 1);
}


int main()
{
    int n = 16;
    if(powerOfTwo(n))
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';


    return 0;
}

Оптимален метод

#include <bits/stdc++.h>
using namespace std;

bool powerOfTwo(int n)
{
    //16 = [10000]
    //15 = [01111]
    //16 & 15 = 0
    return (n & (n - 1)) == 0;
}


int main()
{
    int n = 16;
    if(powerOfTwo(n))
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';


    return 0;
}
Yes

Java програма на Power of Two Leetcode Solution

Наивен метод

class power_of_two
{
    public static boolean powerOfTwo(int n)
    {
        while(n % 2 == 0)
            n /= 2;
        return (n == 1);
    }

    public static void main(String args[])
    {
        int n = 16;
        if(powerOfTwo(n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Оптимален метод

class power_of_two
{
    public static boolean powerOfTwo(int n)
    {
        return (n & (n - 1)) == 0;
    }

    public static void main(String args[])
    {
        int n = 16;
        if(powerOfTwo(n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
Yes

Анализ на сложността  

Сложност във времето на мощността на две Leetcode решения

Сложността във времето на наивния подход е O (log2N), където N = дадено цяло число. Оптималният подход обаче е по-бърз, тъй като Bitwise-And е по-бърз и следователно има времева сложност от O (1).

Космическа сложност на мощността на две Leetcode решения

Подписът на функцията е само място, използвано в програмата. Следователно се използва постоянно пространство - O (1).