የሁለት ሌቲኮድ መፍትሔ ኃይል


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ ፓም
ቢት ማባከን ቢት ሒሳብ

ተሰጠን ኢንቲጀር እና ግቡ ኢንቲጀር የሁለት ኃይል መሆኑን ማረጋገጥ ነው ፣ ማለትም ፣ እንደ አጠቃላይ የ ‹ኃይል› ሊወከል ይችላል ፡፡2'.

የሁለት ሌቲኮድ መፍትሔዎች ኃይል

ለምሳሌ

16
Yes
13
No

ቀረበ

ጥቃቅን መፍትሔ ሊሆን ይችላል-የቁጥሩ ዋና ዋና ምክንያቶች ሁሉም መሆናቸውን ያረጋግጡ ፡፡2' የዚህ ዘዴ የጊዜ ውስብስብነት O ይሆናል (መዝገብ 2 ኤን) በተመጣጣኝ መንገድ ለማድረግ ፣ የ Bit manipulations እገዛን መውሰድ እንችላለን ፡፡

"የሁለት ኃይል የሆነ ማንኛውም ቁጥር በሁለትዮሽ ውክልና ውስጥ አንድ ነጠላ ቢት ብቻ ሊኖረው ይችላል"

አንድ ብቻ እንዳለ እንዴት ሊጣራ ይችላል ነጠላ ቢት ስብስብ በሁለትዮሽ ቅርፅ?

ማንኛውንም ቁጥር ግምት ውስጥ ያስገቡ ፣ x.

አሁን ፣ x የሁለት ኃይል ከሆነ ፣ ከዚያ (x - 1) ሁሉንም ያጠፋቸዋል ትክክለኛ ቢቶች ወደ የተቀመጠው ቢት (እንደ ‹0› አድርገው ያዋቅሯቸው) እና የተቀመጠው ቢት ያልተስተካከለ ይሆናል ፡፡

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

ስለዚህ, በመጠቀም ቢትዊዝ-እና የ x እና (x - 1) ፣ አንድ ቁጥር የሁለት ኃይል ከሆነ ማለት እንችላለን ፣ ከዚያ ፣ x & (x - 1) = 0

ስልተ-ቀመር (ተራ)

  1. ቁጥሩን በ ቁጥር መከፋፈልዎን ይቀጥሉ «2» እስከማይከፋፈል ድረስ «2» ከእንግዲህ ወዲያ.
  2. ቁጥሩ እኩል ከሆነ '1':
    • ኢንቲጀር የሁለት ኃይል ነው
  3. ሌሎች
    • ኢንቲጀርሩ የሁለት ኃይል አይደለም

ስልተ-ቀመር (ቢት-ማባዣ)

  1. X & (x - 1) ከዜሮ ጋር እኩል መሆኑን ያረጋግጡ
    • አዎ ከሆነ ቁጥሩ የ 2 ኃይል ነው
    • ኢንቲጀር የ 2 ኃይል አይደለም ፣ አለበለዚያ

አፈጻጸም

C ++ የሁለት ሌቲኮድ መፍትሔ የኃይል ፕሮግራም

የዋህ ዘዴ

#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

የጃቫ መርሃግብር የሁለት ሌቲኮድ መፍትሔ

የዋህ ዘዴ

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

ውስብስብነት ትንተና

የሁለት ሌቲኮድ መፍትሔ የጊዜ ኃይል ውስብስብነት

Naive Approach የጊዜ ውስብስብነት ነው ኦ (ሎግ 2 ኤን)፣ N = የተሰጠ ኢንቲጀር። ሆኖም ፣ እንደ Bitwise-And ፈጣን እና ስለሆነም የጊዜ ውስብስብነት ያለው እንደመሆኑ አመች አቀራረብ ፈጣን ነው ኦ (1)

የሁለት ሌቲኮድ መፍትሄ የቦታ ውስብስብነት

በፕሮግራሙ ውስጥ ጥቅም ላይ የዋለው ቦታ ብቻ የተግባር ፊርማ ነው። ስለዚህ ቋሚ ቦታ ጥቅም ላይ ይውላል - ኦ (1)