Бит тоолох


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Apple-ийн
Бит манипуляци Бит Динамик програмчлал

Бит тоолох тухай бүх зүйл!

Хүн бүтээсэн компьютертэйгээ холбогдоход бэрхшээлтэй байдаг.

Яагаад тэр вэ?

Хүмүүс олон жилийн турш ярих, сонсохоор ирсэн хэлээр ярьж, ойлгодог боловч ядуу компьютеруудад 0, 1-ийг зааж сургадаг байв.

Тиймээс өнөөдөр компьютерээ заацгаая тоог тоолох Бидний асуудлын илэрхийлэл болох тооны 1-ээс (тоолох битийн хувьд).

Өгөгдсөн: Аливаа эерэг бүхэл тоо байж болох бүхэл тоо

Бид юу хийх ёстой вэ?

1-ээс нум хүртэлх тоо тус бүрийн тоог мэд. Хариултыг нэг мөрөнд хэвлэ.

арга барил Бит тоолоход энгийн бит боловсруулалтыг ашиглах

Дэлгэрэнгүй мэдээллийг авахаасаа өмнө хэд хэдэн Бит үйлдлүүдийг авч үзье

“>>” энэ нь баруун ээлжийн операторыг илэрхийлнэ.

"&"    Энэ нь AND операторыг илэрхийлнэ.

Одоо тоолох бит рүү шилжихээс өмнө зарим жишээг үзээрэй.

A = 1001 байг

a >> 1 = 100

a & 1 = 1

Бид тоог нэг нэгжээр зөв шилжүүлэх бүрдээ хоёр хуваадаг гэж хэлж болно.

B = 100100 бол

b >> 1 = 10010

Үүнийг аль хэдийн массив дахь b / 2-т багтааж хадгалах болно

b & 1 = 0

Энэ ажиллагаа нь сүүлчийн бит 1 эсвэл 0 эсэхийг олоход тусална

c = 1

c >> 1 = 0

c & 1 = 1

Тиймээс num бүрийн хувьд 1-ийн тоо = (num / 2) + (num & 1) -д байгаа тоо

Хэрэгжүүлэх

Бит тоолох Java програм

class Solution 
{
    public int[] countBits(int num) 
    {
    int a[]=new int[num+1];
    for(int i=0;i<=num;i++)
    {
        a[i]=a[i/2]+(i&1);
    }
    return a;
    }
}

Бит тоолох зориулалттай C ++ програм

class Solution 
{
public:
    vector<int> countBits(int num) 
    {
    vector<int>a(num+1);
    for(int i=0;i<=num;i++)
    {
        a[i]=a[i/2]+(i&1);
    }
    return a;    
    }
};

8
13

Нарийн төвөгтэй байдлын шинжилгээ

Дээрх хандлагын цаг хугацааны нарийн төвөгтэй байдал = O (n)

Дээрх хандлагын орон зайн нарийн төвөгтэй байдал = O (n), энд n нь оролтод өгөх утга юм.

Ашигласан материал