Cilat janë trikot e zakonshëm për manipulimin e biteve?

Question

Accepted Answer

**Manipulimi i biteve** funksionon drejtpërdrejt në përfaqësimin binar të numrave të plotë duke përdorur AND, OR, XOR, NOT dhe zhvendosje. Ai mundëson operacione kompakte, pa degë dhe shumë të shpejta. ## Operacionet bërthamore ```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 ``` ## Trikot të dobishëm ```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) ``` ## Shembull: gjeni numrin e vetëm (triku 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 ``` ## Kompleksitet Operacionet e biteve janë O(1); skanimi XOR më lart është **O(n) kohë, O(1) hapësirë**. ## Kur të përdorni / kurthe Përdorni për **maskën e biteve** (enumarimi i nënbashkësive, DP mbi gjendjet), flamuj, matematikë të shpejtë dhe kod në nivel të ulët/të ngulitur. Kujdes ndaj biteve të shenjës, sjelljes së zhvendosjes specifike për gjuhën dhe lexueshmërisë — komentoni trikot jo të dukshëm. ## Pse është e rëndësishme Manipulimi i biteve jep zgjidhje elegante O(1)-hapësire (si triku XOR i numrit të vetëm) që mahnitin në intervista. Bitmask DP e bën shumë problemet e hapësirës kombinator të gjendjeve të arritshme. Është thelbësor në sistemet, grafikën, kompresimet dhe kodin kritik për performancën ku çdo cikël numëron.