ბიტური ოპერაციები

ყოველი მთელი რიცხვი უკვე ბიტების მასივია და პროცესორი ყველა მათგანს ერთი ინსტრუქციით ამუშავებს. ისწავლე რამდენიმე ოპერატორი და ალმებს, სიმრავლეებსა და ქვესიმრავლეებს თითქმის უფასოდ მიიღებ.

დამწყები⏱ 10 წთ

←ეყრდნობა

4ქვესიმრავლეებისა და გადანაცვლებების გენერაციაn ელემენტის ქვესიმრავლე n-ბიტიანი რიცხვია; 0-დან 2ⁿ − 1-მდე დათვლა ყველას ჩამოთვლის.5ფენვიკის ხე (ბინარული ინდექს-ხე)ფენვიკის ნახტომები idx += idx & -idx უმცროსი ერთიანი ბიტის ხერხია; ეს ეტაპი მას ზოგადად ხსნის.

გზას უხსნის→

9სწრაფი ახარისხება და მოდულური არითმეტიკაn-ის ორობითი ციფრები წყვეტს, რომელი კვადრატები გამრავლდება.10ბიტმასკური დპმონახულებული ქალაქების სიმრავლე ბიტმასკაში ინახება და ახლახან ნასწავლი ბიტური ხერხებით მოწმდება და ფართოვდება.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01რიცხვი ბიტების მწკრივია

ორობითად 12 არის 1100: ჩართულია მე-3 და მე-2 ბიტი, ღირებულებით 8 + 4. i-ე ბიტი ღირს 2^i-ს, პოზიციებს კი მარჯვნიდან, 0-დან ვითვლით.

ბიტური ოპერატორები ყოველ პოზიციაზე დამოუკიდებლად მუშაობს, გადატანის გარეშე:

a & b (AND): 1 მხოლოდ იქ, სადაც ორივე ბიტი 1-ია
a | b (OR): 1 იქ, სადაც ერთი მაინც 1-ია
a ^ b (XOR): 1 იქ, სადაც ბიტები განსხვავდება
~a (NOT): ყველა ბიტს აბრუნებს

ასე რომ 12 & 10 = 8, 12 | 10 = 14, 12 ^ 10 = 6. XOR-ს მშვენიერი თვისება აქვს: x ^ x = 0 და x ^ 0 = x, ამიტომ თუ სიაში ყველა მნიშვნელობა ორჯერ გვხვდება ერთის გარდა, ყველას XOR ზუსტად იმ მარტოხელა მნიშვნელობას დატოვებს.

02წანაცვლებები და ცალკეული ბიტის ხრიკები

a << k ყველა ბიტს k პოზიციით მარცხნივ წევს, რაც 2^k-ზე გამრავლებაა; a >> k მარჯვნივ წევს, ანუ 2^k-ზე ყოფს ქვემოთ დამრგვალებით. კერძოდ, 1 << i არის რიცხვი, რომელსაც ერთადერთი 1 აქვს i-ე პოზიციაზე: ნიღაბი.

ნიღბით ერთ ბიტს შეეხები და დანარჩენს ხელს არ ახლებ:

შემოწმება: (a >> i) & 1 ან a & (1 << i) არანულოვანია
ჩართვა: a | (1 << i)
გამორთვა: a & ~(1 << i)
გადართვა: a ^ (1 << i)

ეს ოთხი სტრიქონი დაიმახსოვრე: ყველა ბიტმასკურ ამოხსნაში გვხვდება. ერთი ხაფანგი: C++-სა და Java-ში 1 << 40 32-ბიტიან int-ს გადაავსებს. როცა i შეიძლება 31-ს მიაღწიოს ან გადააჭარბოს, დაწერე 1LL << 40 (ან 1L).

03x & (x − 1): ყველაზე დაბალი 1-ის მოშორება

x-ს 1-ის გამოკლება მის ყველაზე დაბალ 1-ს 0-ად აქცევს, მის ქვემოთ ყველა 0-ს კი 1-ად; ზედა ბიტები ადგილზე რჩება. საწყისთან AND მთელ ამ „კუდს“ აბათილებს, ასე რომ x & (x - 1) არის x, რომელსაც ყველაზე დაბალი ჩართული ბიტი მოაშორეს.

ორი კლასიკური გამოყენება:

ერთიანი ბიტების დათვლა: გაიმეორე x &= x - 1, სანამ x 0 არ გახდება. ციკლი თითო 1-ზე ერთხელ სრულდება და არა თითო პოზიციაზე.
არის თუ არა x ორის ხარისხი? ორის ხარისხს ზუსტად ერთი 1 აქვს, ამიტომ შემოწმებაა x > 0 && (x & (x - 1)) == 0.

მონათესავე ხრიკი, x & -x, მხოლოდ ყველაზე დაბალ 1-ს ტოვებს. სწორედ ესაა ფენვიკის ხის გული. პრაქტიკაში შეგიძლია __builtin_popcount (C++) ან Integer.bitCount (Java) გამოიძახო, მაგრამ იმის ცოდნა, რატომ მუშაობს, საკუთარი ხრიკების მოგონებაში გეხმარება.

180 = 10110100₂. 1-ის გამოკლება აბრუნებს „კუდს“ ყველაზე დაბალი 1-იდან; AND ტოვებს მხოლოდ იმას, რაზეც ორივე თანხმდება.

04ქვესიმრავლეები რიცხვებად

ავიღოთ n ელემენტი. რიცხვი 0-დან 2^n − 1-მდე შეიძლება ქვესიმრავლეს აღწერდეს: k-ე ბიტი 1-ია, როცა k-ე ელემენტი შედის. ნიღაბი 1011 ნიშნავს ელემენტებს 0, 1 და 3. ასე რომ ერთი მარტივი ციკლი ჩამოთვლის ყველა ქვესიმრავლეს:

for (mask = 0; mask < (1 << n); mask++), შიგნით კი mask & (1 << k) გვეკითხება, აღებულია თუ არა k-ე ელემენტი.

სიმრავლეებზე ოპერაციები ერთ ინსტრუქციად იქცევა: გაერთიანება |-ია, თანაკვეთა &, „k-ე ელემენტის დამატება“ | (1 << k), ზომა კი popcount. სწორედ ეს ხდის შესაძლებელს ბიტმასკურ დპ-ს: მდგომარეობა, როგორიცაა „რომელი ქალაქები მოვინახულე“, ერთ მთელ რიცხვში ეტევა და მასივის ინდექსად გამოდგება. ფასი 2^n მდგომარეობაა, ამიტომ მუშაობს n ≈ 20-მდე. ეს ზღვარი დასკვნით გაკვეთილში დაგვიბრუნდება.

ფასი ერთი შეხედვით

ერთი ბიტური ოპერაციაO(1)

popcount x & (x−1)-ითO(number of 1-bits)

ყველა ქვესიმრავლის ჩამოთვლაO(2ⁿ)

დაიმახსოვრე

AND საერთო 1-ებს ტოვებს, OR ყველა 1-ს აგროვებს, XOR განსხვავებებს აღნიშნავს, წანაცვლებები კი ორის ხარისხზე ამრავლებს ან ყოფს.
ნიღაბი 1 << i საშუალებას გაძლევს ერთი ბიტი შეამოწმო, ჩართო, გამორთო ან გადართო; x & (x−1) ყველაზე დაბალ 1-ს შლის.
n-ბიტიანი რიცხვი n ელემენტის ქვესიმრავლეა, ამიტომ ციკლი 0-დან 2ⁿ−1-მდე ყველა ქვესიმრავლეს გაივლის; ეს ბიტმასკური დპ-ის საფუძველია.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: ადევნე თვალი ყვითელ უჯრას: ყოველ რაუნდში x − 1 აბრუნებს „კუდს“ ყველაზე დაბალი 1-იდან ქვემოთ, AND კი ზუსტად იმ ერთ ბიტს შლის. შემდეგ სცადე op = and, set ან subsets.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

ბიტები: `popcount(182)`

პოზიცია

x

= 182

დავთვალოთ 182 = 10110110₂-ის ერთიანი ბიტები. 8-ვე პოზიციის შემოწმების ნაცვლად, ერთი 1-იდან პირდაპირ შემდეგზე ვხტებით.

ფსევდოკოდი

 1 a & b        // 1 only where both bits are 1 2 a | b        // 1 where at least one bit is 1 3 a ^ b        // 1 where the bits differ 4 a << k, a >> k   // multiply / divide by 2^k 5 mask = 1 << i 6 test: a & mask   set: a | mask   clear: a & ~mask   toggle: a ^ mask 7 count = 0 8 while x != 0: 9   // x - 1 flips the lowest 1 and every 0 below it10   x = x & (x - 1); count += 1   // lowest 1 is gone11 for mask in 0 .. 2^n - 1:12   subset = { item k : mask & (1 << k) != 0 }

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

x = 44 = 101100₂. რას უდრის x & (x − 1)?

№2

რომელი გამოსახულება გამორთავს a-ს i-ე ბიტს და დანარჩენს უცვლელს დატოვებს?

№3

n = 5 ელემენტისთვის რომელი ნიღაბი აღნიშნავს ქვესიმრავლეს {ელემენტი 0, ელემენტი 2, ელემენტი 4}?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

LeetCodeNumber of 1 Bits დამწყები↗LeetCodeSingle Number დამწყები↗LeetCodeSubsets საშუალო↗CSESApple Division საშუალო↗CSESGray Code საშუალო↗