Cad na cleas coitianta ionramhála giotán?

Question

Accepted Answer

**Ionramhála giotán** oibríonn go díreach ar dhíoluithe dénártha slánuimhreacha ag baint úsáide as AND, OR, XOR, NOT agus gluaiseachtaí. Tugann sé deis do oibríochtaí dlúth, gan bhranch, agus an-tapa. ## Oibríochtaí príomhúla ```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 ``` ## Cleas úsáideacha ```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) ``` ## Sampla: faigh an uimhir aonair (cleas 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 ``` ## Castacht Is O(1) iad oibríochtaí giotán; is **O(n) am, O(1) spás** an scan XOR thuas. ## Cathain a úsáidtear / gaothanna Úsáid do **bitmasks** (áirimh fo-thacar, DP ar stáit), bratáin, matamaitic thapa, agus cód íseal-leibhéal/fúthaithe. Bí i ngar do ghiotáin shínithe, gealadh iompar sonrach-teanga, agus inléiteacht — tabhair nóta ar chleasa neamh-dhénamhnithe. ## Cad is tábhacht ann Bíonn réitigh dhéagránacha O(1)-spás ag ionramhála giotán (ar nós an chleas XOR uimhir-aonair) a dhéanann dúisiú ag agallamh. Déanann bitmask DP go leor pointí spáis stáit chomhchoibhneasta inchomhchosúil. Tá sé riachtanach i gcórais, grafaic, comhbhrú agus cód mothúchánach-feidhmíochta áit ar thaitin gach timthriall.