సాధారణ బిట్-మానిపులేషన్ ట్రిక్‌లు ఏమిటి?

Question

Accepted Answer

**బిట్ మానిపులేషన్** AND, OR, XOR, NOT మరియు షిఫ్‌టులను ఉపయోగించి పూర్ణాంకాల బైనరీ ప్రాతిపదికన నేరుగా పనిచేస్తుంది. ఇది కాంపాక్ట్, శాఖ-రహిత మరియు చాలా వేగవంతమైన కార్యకలాపాలను ఎనేబుల్ చేస్తుంది. ## ప్రధాన ఆపరేషన్లు ```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) ఖాళీ**. ## ఎప్పుడు ఉపయోగించాలి / ఆపదలు **బిట్‌మాస్క్‌ల** (సబ్‌సెట్ ఎనుమరేషన్, స్థితుల పై DP), ఫ్లాగ్‌లు, వేగవంతమైన గణితం మరియు తక్కువ-స్థాయి/ఎంబెడ్‌డెడ్ కోడ్ కోసం ఉపయోగించండి. సంకేత బిట్‌లు, భాష-నిర్దిష్ట షిఫ్ট ప్రవర్తన మరియు పఠనీయత గురించి జాగ్రత్తగా ఉండండి — స్పష్టమైన ట్రిక్‌లను వ్యాఖ్యానించండి. ## ఇది ఎందుకు ముఖ్యమైనది బిట్ మానిపులేషన్ సొగసైన O(1)-స్పేస్ సమాధానాలను (XOR ఏకైక-సంఖ్య ట్రిక్ వంటివి) ఇస్తుంది, ఇవి ఇంటర్వ్యూలలో ఆశ్చర్యపరుస్తాయి. బిట్‌మాస్క్ DP చాలా కాంబినేటోరియల్ స్టేట్-స్పేస్ సమస్యలను పరిష్కారమైనవిగా చేస్తుంది. ఇది సిస్టమ్‌లు, గ్రాఫిక్‌లు, కంప్రెషన్ మరియు పারఫরమెన్స్-క్రిటికల్ కోడ్‌లో అవసరమైనది, ఇక్కడ ప్రతి సైకిల్ ముఖ్యమైనది.