Ποια είναι τα κοινά κόλπα χειρισμού bits;

Question

Accepted Answer

**Ο χειρισμός bits** λειτουργεί απευθείας στη δυαδική αναπαράσταση ακεραίων χρησιμοποιώντας AND, OR, XOR, NOT και shifts. Ενεργοποιεί συμπαγείς, χωρίς διακλάδωση και πολύ γρήγορες λειτουργίες. ## Βασικές λειτουργίες ```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 ``` ## Πολυπλοκότητα Οι λειτουργίες bits είναι O(1); η σάρωση XOR παραπάνω είναι **O(n) χρόνος, O(1) χώρος**. ## Πότε να χρησιμοποιήσετε / Παγίδες Χρησιμοποιήστε για **bitmasks** (απαρίθμηση υποσυνόλων, DP σε καταστάσεις), σημαίες, γρήγορα μαθηματικά και κώδικα χαμηλού επιπέδου/ενσωματωμένο. Προσέξτε τα bits σημείου, τη συμπεριφορά shift ειδική για τη γλώσσα και την αναγνωσιμότητα — σχολιάστε τα μη προφανή κόλπα. ## Γιατί έχει σημασία Ο χειρισμός bits αποδίδει κομψές O(1)-χώρου λύσεις (όπως το κόλπο XOR μοναδικού αριθμού) που εντυπωσιάζουν σε συνεντεύξεις. Το Bitmask DP κάνει πολλά συνδυαστικά προβλήματα χώρου καταστάσεων ευεπίλυτα. Είναι απαραίτητο σε συστήματα, γραφικά, συμπίεση και κώδικα κρίσιμο για την απόδοση όπου κάθε κύκλος μετράει.