អំណាចនៃដំណោះស្រាយឡេឡេលេខកូដពីរ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ផ្លែប៉ោម
ការរៀបចំប៊ីត ប៊ីត គណិតវិទ្យា

យើងត្រូវបានផ្តល់ឱ្យ integer ហើយគោលដៅគឺត្រូវពិនិត្យមើលថាតើចំនួនគត់ជាថាមពលពីរឬអត់វាអាចត្រូវបានតំណាងថាជាអំណាចទាំងមូលនៃ2'។

ថាមពលនៃដំណោះស្រាយឡេឡេលេខកូដពីរ

ឧទាហរណ៍

16
Yes
13
No

វិធីសាស្រ្ត

ដំណោះស្រាយតូចតាចអាចជាៈពិនិត្យមើលថាតើកត្តាធំ ៗ នៃចំនួនគត់គឺទាំងអស់ '2'។ ភាពស្មុគស្មាញនៃពេលវេលានៃវិធីសាស្ត្រនេះគឺអូ (log2N) ។ ដើម្បីធ្វើវាតាមរបៀបដ៏ប្រសើរបំផុតយើងអាចជួយឧបាយកលប៊ីត។

លេខណាមួយដែលជាស្វ័យគុណនៃចំនួនពីរអាចមានតែមួយកំណត់ជាតំណាងគោលពីរ

តើវាអាចត្រូវបានធីកយ៉ាងដូចម្តេចថាមានតែវាទេ សំណុំប៊ីតតែមួយ នៅក្នុងសំណុំបែបបទគោលពីរ?

ពិចារណាលើលេខណាមួយ, x ។

ឥលូវប្រសិនបើ x ជាថាមពលនៃពីរអញ្ចឹង (x - ១) នឹងបិទទាំងអស់ ប៊ីតត្រឹមត្រូវ ទៅសំណុំប៊ីត (កំណត់ពួកវាជា '០') ហើយប៊ីតសំណុំមិនត្រូវបានកំណត់ទេ។

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

ដូច្នេះការប្រើប្រាស់ BITWISE-AND នៃ x និង (x - 1) យើងអាចនិយាយបានថាប្រសិនបើលេខមួយជាថាមពលខ្លះនៃពីរបន្ទាប់មក x & (x - 1) = 0

ក្បួនដោះស្រាយ (ភាពមិនសំខាន់)

  1. បន្ដចែកលេខតាម '១០០' រហូតដល់វាមិនអាចបែងចែកបានដោយ '១០០' ទៀតទេ។.
  2. ប្រសិនបើលេខស្មើនឹង '១'៖
    • ចំនួនគត់គឺជាថាមពលពីរ
  3. ផ្សេងទៀត
    • ចំនួនគត់មិនមែនជាថាមពលពីរទេ

ក្បួនដោះស្រាយ (ការធ្វើចលនាប៊ីត)

  1. ពិនិត្យមើលថាតើ x & (x - 1) ស្មើនឹងសូន្យ
    • បើមែនលេខគឺជាថាមពលមួយនៃលេខ ២
    • ចំនួនគត់មិនមែនជាថាមពល ២ ទេ

ការអនុវត្តន៍

កម្មវិធី 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

ការវិភាគស្មុគស្មាញ

ភាពស្មុគស្មាញនៃពេលវេលានៃថាមពលនៃដំណោះស្រាយឡេឡេលេខកូដពីរ

ភាពស្មុគស្មាញនៃពេលវេលានៃវិធីសាស្ត្រណាតូសគឺ O (log2N), ដែល N = ចំនួនគត់ដែលបានផ្តល់។ ទោះជាយ៉ាងណាវិធីសាស្រ្តល្អប្រសើរបំផុតគឺលឿនជាងមុន, ដូចដែល Bitwise - និងលឿនជាងមុនហើយដូច្នេះមានភាពស្មុគស្មាញពេលវេលានៃការ ឱ (១) ។

ភាពស្មុគស្មាញនៃលំហនៃថាមពលនៃឡេឡេហ្សិចសូលុយស្យុងពីរ

មានតែចន្លោះដែលត្រូវបានប្រើនៅក្នុងកម្មវិធីប៉ុណ្ណោះដែលជាហត្ថលេខាមុខងារ។ ដូច្នេះទំហំថេរត្រូវបានប្រើ - ឱ (១) ។