რა არის ბიტის მანიპულირების გავრცელებული ხრიკები?

Question

Accepted Answer

**Bit manipulation** მოქმედებს მთელი რიცხვების ორობითი წარმოდგენაზე პირდაპირი AND, OR, XOR, NOT და shift ოპერაციების გამოყენებით. ეს გაძლევთ კომპაქტური, განშტოების გარეშე და ძალიან სწრაფი ოპერაციების შესაძლებლობას. ## ძირითადი ოპერაციები ```python x & 1 # is x odd? (lowest bit) x << 1 # multiply by 2 x >> 1 # integer divide by 2 x & (1 << k) # is bit k set? x | (1 << k) # set bit k x & ~(1 << k) # clear bit k x ^ (1 << k) # toggle bit k ``` ## სასარგებლო ხრიკები ```python x & (x - 1) # clears the lowest set bit x & (x - 1) == 0 # is x a power of two? (x>0) x & (-x) # isolates the lowest set bit bin(x).count('1') # popcount (number of set bits) ``` ## მაგალითი: ერთი რიცხვის პოვნა (XOR ხრიკი) ```python def single_number(nums): result = 0 for n in nums: result ^= n # pairs cancel: a ^ a == 0 return result # the lone unpaired value remains single_number([4, 1, 2, 1, 2]) # -> 4 ``` ## რთულობა ბიტის ოპერაციები არის O(1); ზემოთ მოთავილებული XOR სკანი არის **O(n) დრო, O(1) სივრცე**. ## როდის გამოიყენება / ხაფანგები იმოიყენეთ **bitmask**-ისთვის (ქვესიმრავლის ჩამეტებული, DP სახელმწიფოზე), დროშა, სწრაფი მათემატიკა და დაბალი დონის/ჩაშენებული კოდისთვის. ზედაბალი ნიშნების, ენის სპეციფიკური shift ქცევის და წაკითხვადობის შესახებ. კომენტარი არა აშკარა ხრიკებზე. ## რატომ არის ეს მნიშვნელოვანი ბიტის მანიპულირება წარმოქმნის ელეგანტურ O(1)-სივრცის გადაწყვეტილებებს (მაგალითად XOR ერთეული რიცხვის ხრიკი), რომელიც გასაოცარია ინტერვიუში. Bitmask DP აქცევს მრავალ კომბინატორულ სახელმწიფო-სივრცის პრობლემებს გამოსაყენებელი. ეს არის აუცილებელი სისტემებში, გრაფიკაში, კომპრესიაში და ყველა ციკლის მნიშვნელოვანი კოდში.