Nini ni tricks za kawaida za kidhibiti cha bits?

Question

Accepted Answer

**Kidhibiti cha bits** kinafanya kazi moja kwa moja juu ya uwakilishi wa binary wa nambari kamili kwa kutumia AND, OR, XOR, NOT, na mabadiliko. Inakuwezesha operesheni nyingi, zisizo na tawi, na haraka sana. ## Operesheni za msingi ```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 ``` ## Tricks muhimu ```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) ``` ## Mfano: tafuta nambari moja (XOR trick) ```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 ``` ## Utata Bit ops ni O(1); XOR scan hapo juu ni **O(n) wakati, O(1) nafasi**. ## Wakati wa kutumia / hatari Tumia kwa **bitmasks** (kuhesabu sehemu ndogo, DP juu ya hali), bayani, hesabu ya haraka, na msimbo wa kiwango cha chini/iliyozamishwa. Kusubiri bits za ishara, tabia ya kugeuka mahususi ya lugha, na urahisi wa kusoma — komenti tricks zisizokuwa na kawaida. ## Kwa nini ni muhimu Kidhibiti cha bits kunatoa suluhisho duni za O(1)-nafasi (kama trick ya XOR ya nambari moja) zinazostajabu katika mahojiano. Bitmask DP inafanya matatizo mengi ya nafasi ya hali ya combinatorial kuwa yanayoshughulikika. Ni muhimu katika mifumo, picha, ukamalizaji, na msimbo muhimu wa utendaji ambapo kila mzunguko unahusu.