बिट मास्किंग और स्थानांतरण

बिट स्थानांतरण को अक्सर निम्न स्तर के ग्राफिक्स प्रोग्रामिंग में उपयोग किया जाता है। उदाहरण के लिए 32-बिट शब्द में एन्कोड किए गए दिए गए पिक्सेल रंग मान।

 Pixel-Color Value in Hex:    B9B9B900
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

बेहतर समझने के लिए, वही द्विआधारी मूल्य लेबल करता है जो अनुभागों का प्रतिनिधित्व करता है जो रंग भाग का प्रतिनिधित्व करता है।

                                 Red     Green     Blue       Alpha
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

आइए उदाहरण के लिए हम इस पिक्सल रंग का हरा मान प्राप्त करना चाहते हैं। हम मास्किंग और स्थानांतरण द्वारा आसानी से उस मूल्य को प्राप्त कर सकते हैं।

हमारा मुखौटा:

                  Red      Green      Blue      Alpha
 color :        10111001  10111001  10111001  00000000
 green_mask  :  00000000  11111111  00000000  00000000

 masked_color = color & green_mask

 masked_color:  00000000  10111001  00000000  00000000

तार्किक & ऑपरेटर यह सुनिश्चित करता है कि केवल वे मान जहां मास्क 1 रखा जाता है। आखिरी चीज जो हमें अब करना है, वह उन सभी बिट्स को 16 स्थानों (तार्किक दाएं शिफ्ट) से दाएं स्थानांतरित करके सही पूर्णांक मान प्राप्त करना है।

 green_value = masked_color >>> 16

और voilá, हमारे पास पिक्सल रंग में हरे रंग की मात्रा का प्रतिनिधित्व करने वाला पूर्णांक है:

 Pixels-Green Value in Hex:     000000B9
 Pixels-Green Value in Binary:  00000000 00000000 00000000 10111001 
 Pixels-Green Value in Decimal: 185

यह अक्सर एन्कोडिंग या डीकोडिंग छवि प्रारूपों जैसे jpg , png , ... लिए प्रयोग किया जाता है।

इस बारे में जागरूक रहें कि विंडोज प्लेटफ़ॉर्म पर PHP का केवल 32 बिट संस्करण उपलब्ध है।

फिर यदि आप उदाहरण के लिए << या >> 31 बिट्स से अधिक स्थानांतरित करते हैं, तो परिणाम अप्रत्याशित होते हैं। आमतौर पर शून्य के बजाय मूल संख्या वापस कर दी जाएगी, और यह वास्तव में एक मुश्किल बग हो सकता है।

बेशक यदि आप PHP (यूनिक्स) के 64 बिट संस्करण का उपयोग करते हैं, तो आपको 63 बिट्स से अधिक स्थानांतरित होने से बचना चाहिए। हालांकि, उदाहरण के लिए, MySQL 64-बिट बिगिनट का उपयोग करता है, इसलिए कोई संगतता समस्या नहीं होनी चाहिए।

अद्यतन: PHP7 विंडोज़ से, php builds अंततः पूर्ण 64 बिट पूर्णांक का उपयोग करने में सक्षम हैं: पूर्णांक का आकार प्लेटफ़ॉर्म-निर्भर है, हालांकि अधिकतम दो बिल का अधिकतम मूल्य सामान्य मान है (यह 32 बिट्स हस्ताक्षरित है)। 64-बिट प्लेटफार्मों में आमतौर पर लगभग 9ई 18 का अधिकतम मूल्य होता है, विंडोज 7 को विंडोज़ से पहले छोड़कर, जहां यह हमेशा 32 बिट था।

ध्यान दें कि जावा कार्यान्वयन में, बिट्स की संख्या को स्थानांतरित करने के लिए स्रोत के आकार से संशोधित किया जाता है।

उदाहरण के लिए:

(long) 4 >> 65

बराबर 2. आप उम्मीद कर सकते हैं कि बिट्स को सही तरीके से 65 गुना स्थानांतरित करने की उम्मीद हो सकती है, लेकिन यह वास्तव में बराबर है:

(long) 4 >> (65 % 64)

यह <<, >>, और >>> के लिए सच है। मैंने इसे अन्य भाषाओं में नहीं देखा है।

बिट स्थानांतरण ऑपरेटरों वास्तव में उनके नाम का तात्पर्य करते हैं। वे बिट्स को स्थानांतरित करते हैं। विभिन्न शिफ्ट ऑपरेटरों के लिए यहां एक संक्षिप्त (या संक्षिप्त नहीं) परिचय दिया गया है।

ऑपरेटर

• >> अंकगणित (या हस्ताक्षरित) सही शिफ्ट ऑपरेटर है।
• >>> तार्किक (या हस्ताक्षरित) सही शिफ्ट ऑपरेटर है।
• << बाएं शिफ्ट ऑपरेटर है, और दोनों तार्किक और अंकगणितीय बदलावों की आवश्यकताओं को पूरा करता है।

इन सभी ऑपरेटरों को पूर्णांक मानों ( int , long , संभवतः short और byte या char ) पर लागू किया जा सकता है। कुछ भाषाओं में, शिफ्ट ऑपरेटरों को int से कम किसी भी डेटाटाइप पर लागू करने से स्वचालित रूप से ऑपरेंड का आकार बदल जाता है।

ध्यान दें कि <<< एक ऑपरेटर नहीं है, क्योंकि यह अनावश्यक होगा। यह भी ध्यान रखें कि सी और सी ++ सही शिफ्ट ऑपरेटरों के बीच अंतर नहीं करते हैं। वे केवल >> ऑपरेटर प्रदान करते हैं, और दाएं-स्थानांतरण व्यवहार को हस्ताक्षरित प्रकारों के लिए परिभाषित किया गया है।

बाएं शिफ्ट (<<)

बिट्स की श्रृंखला के रूप में, स्मृति में, इंटीजर संग्रहीत होते हैं। उदाहरण के लिए, 32-बिट int रूप में संग्रहीत नंबर 6 होगा:

00000000 00000000 00000000 00000110

इस बिट पैटर्न को बाएं एक स्थिति में स्थानांतरित करना ( 6 << 1 ) परिणामस्वरूप संख्या 12:

00000000 00000000 00000000 00001100

जैसा कि आप देख सकते हैं, अंक बाईं ओर एक स्थान से स्थानांतरित हो गए हैं, और दाईं ओर अंतिम अंक शून्य से भरा हुआ है। आप यह भी ध्यान दे सकते हैं कि बाएं स्थानांतरित करना 2 की शक्तियों के गुणा के बराबर है। इसलिए 6 << 1 6 * 2 बराबर है, और 6 << 3 6 * 8 बराबर है। एक अच्छा अनुकूलन संकलक जब संभव हो तो बदलावों के साथ गुणाओं को प्रतिस्थापित करेगा।

गैर परिपत्र स्थानांतरण

कृपया ध्यान दें कि ये गोलाकार बदलाव नहीं हैं। इस मान को बाईं ओर एक स्थान पर स्थानांतरित करना ( 3,758,096,384 << 1 ):

11100000 00000000 00000000 00000000

परिणाम 3,221,225,472:

11000000 00000000 00000000 00000000

वह अंक जो "अंत से बाहर" स्थानांतरित हो जाता है, खो जाता है। यह चारों ओर लपेट नहीं है।

तार्किक सही शिफ्ट (>>>)

एक तार्किक दायां शिफ्ट बाएं शिफ्ट के विपरीत है। बाईं ओर बिट्स को स्थानांतरित करने के बजाय, वे बस दाईं ओर जाते हैं। उदाहरण के लिए, संख्या 12 स्थानांतरित करना:

00000000 00000000 00000000 00001100

एक स्थिति से दाएं ( 12 >>> 1 ) हमारे मूल 6 वापस आ जाएगा:

00000000 00000000 00000000 00000110

तो हम देखते हैं कि दाईं ओर स्थानांतरित करना 2 की शक्तियों के विभाजन के बराबर है।

खोया बिट्स चले गए हैं

हालांकि, एक बदलाव "खो" बिट्स को पुनः प्राप्त नहीं कर सकता है। उदाहरण के लिए, यदि हम इस पैटर्न को बदलते हैं:

00111000 00000000 00000000 00000110

बाएं 4 पदों पर ( 939,524,102 << 4 9, 939,524,102 << 4 ), हमें 2,147,483,744 मिलते हैं:

10000000 00000000 00000000 01100000

और फिर वापस स्थानांतरित ( (939,524,102 << 4) >>> 4 ) हमें 134,217,734 मिलते हैं:

00001000 00000000 00000000 00000110

एक बार जब हम बिट्स खो देते हैं तो हम अपने मूल मूल्य को वापस नहीं प्राप्त कर सकते हैं।

अंकगणित सही शिफ्ट (>>)

अंकगणितीय दायां शिफ्ट शून्य के साथ पैडिंग के बजाय, तार्किक दाएं शिफ्ट की तरह है, यह सबसे महत्वपूर्ण बिट के साथ पैड है। ऐसा इसलिए है क्योंकि सबसे महत्वपूर्ण बिट साइन बिट है, या बिट जो सकारात्मक और नकारात्मक संख्याओं को अलग करता है। सबसे महत्वपूर्ण बिट के साथ पैडिंग करके, अंकगणित सही शिफ्ट साइन-संरक्षित है।

उदाहरण के लिए, यदि हम इस बिट पैटर्न को ऋणात्मक संख्या के रूप में समझते हैं:

10000000 00000000 00000000 01100000

हमारे पास संख्या -2,147,483,552 है। अंकगणितीय शिफ्ट (-2,147,483,552 >> 4) के साथ इसे सही 4 पदों पर स्थानांतरित करने से हमें यह मिल जाएगा:

11111000 00000000 00000000 00000110

या संख्या -134,217,722।

इसलिए हम देखते हैं कि हमने तर्कसंगत दाएं शिफ्ट की बजाय अंकगणित सही शिफ्ट का उपयोग करके हमारी नकारात्मक संख्याओं के संकेत को संरक्षित किया है। और एक बार फिर, हम देखते हैं कि हम 2 की शक्तियों से विभाजन कर रहे हैं।

मान लें कि हमारे पास एक बाइट है:

0110110

एक बाएं बिट्सफिफ्ट को लागू करने से हमें मिलता है:

1101100

बाएं सबसे शून्य को बाइट से बाहर कर दिया गया था, और बाइट के दाहिने सिरे पर एक नया शून्य जोड़ा गया था।

बिट्स रोलओवर नहीं करते हैं; उन्हें त्याग दिया जाता है। इसका मतलब है कि यदि आपने शिफ्ट 1101100 छोड़ दिया है और फिर इसे सही स्थानांतरित कर दिया है, तो आपको वही परिणाम नहीं मिलेगा।

एन द्वारा छोड़ा गया स्थानांतरण 2 ^एन से गुणा करने के बराबर है।

एन द्वारा सही स्थानांतरित करना (यदि आप किसी के पूरक का उपयोग कर रहे हैं ) 2 ^एन द्वारा विभाजित करने और शून्य से घूर्णन के बराबर है।

बिट्सफ़िफ्टिंग का उपयोग अत्यधिक तेज़ गुणा और विभाजन के लिए किया जा सकता है, बशर्ते आप 2 की शक्ति के साथ काम कर रहे हों। लगभग सभी निम्न-स्तरीय ग्राफिक्स दिनचर्या बिट्सफिफ्टिंग का उपयोग करते हैं।

उदाहरण के लिए, पुराने दिनों में वापस रास्ता, हमने गेम के लिए मोड 13h (320x200 256 रंग) का उपयोग किया। मोड 13h में, वीडियो मेमोरी अनुक्रमिक रूप से प्रति पिक्सल रखी गई थी। इसका मतलब पिक्सेल के लिए स्थान की गणना करना था, आप निम्न गणित का उपयोग करेंगे:

memoryOffset = (row * 320) + column

अब, उस दिन और उम्र में, गति महत्वपूर्ण थी, इसलिए हम इस ऑपरेशन को करने के लिए बिट्सफिफ्ट का उपयोग करेंगे।

हालांकि, 320 दो की शक्ति नहीं है, इसलिए इसके आस-पास पहुंचने के लिए हमें यह पता लगाना होगा कि एक साथ जोड़े गए दो की शक्ति क्या है 320:

(row * 320) = (row * 256) + (row * 64)

अब हम इसे बाएं बदलावों में परिवर्तित कर सकते हैं:

(row * 320) = (row << 8) + (row << 6)

के अंतिम परिणाम के लिए:

memoryOffset = ((row << 8) + (row << 6)) + column

अब हम एक ही ऑफसेट को पहले के रूप में प्राप्त करते हैं, महंगे गुणात्मक संचालन के बजाय, हम दो बिट्सफिफ्ट का उपयोग करते हैं ... x86 में यह ऐसा कुछ होगा (नोट, यह हमेशा के लिए रहा है क्योंकि मैंने असेंबली की है (संपादक का नोट: सही कुछ गलतियों और 32-बिट उदाहरण जोड़ा)):

mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]

; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov

कुल: जो भी प्राचीन सीपीयू पर इन चक्रों पर 28 चक्र थे।

वीआरएस

mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6;  2
shl di, 8;  2
add di, ax; 2    (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]

एक ही प्राचीन सीपीयू पर 12 चक्र।

हां, हम 16 सीपीयू चक्रों को दाढ़ी देने के लिए इस कड़ी मेहनत करेंगे।

32 या 64-बिट मोड में, दोनों संस्करणों को बहुत छोटा और तेज़ मिलता है। इंटेल स्काइलेक जैसे आधुनिक आउट ऑफ़ ऑर्डर निष्पादन सीपीयू ( http://agner.org/optimize/ ) बहुत तेज हार्डवेयर गुणा (कम विलंबता और उच्च थ्रूपुट) है, इसलिए लाभ बहुत छोटा है। एएमडी बुलडोजर-परिवार थोड़ा धीमा है, खासकर 64-बिट गुणा के लिए। इंटेल सीपीयू, और एएमडी रेजेन पर, दो बदलाव थोड़ा कम विलंबता हैं लेकिन गुणा से अधिक निर्देश (जो निम्न थ्रूपुट का कारण बन सकता है):

imul edi, [row], 320    ; 3 cycle latency from [row] being ready
add  edi, [column]      ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column],  in 4 cycles from [row] being ready.

बनाम

mov edi, [row]
shl edi, 6               ; row*64.   1 cycle latency
lea edi, [edi + edi*4]   ; row*(64 + 64*4).  1 cycle latency
add edi, [column]        ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column],  in 3 cycles from [row] being ready.

कंपाइलर्स यह आपके लिए करेंगे: देखें कि जीसीसी, क्लैंग, और एमएसवीसी सभी स्विच = लीए का उपयोग करते समय स्विच return 320*row + col; ली + का उपयोग करते हैं return 320*row + col; ।

यहां ध्यान देने योग्य सबसे दिलचस्प बात यह है कि x86 में एक शिफ्ट-एंड-एड निर्देश ( LEA ) है जो छोटे बाएं बदलाव कर सकता है और साथ ही प्रदर्शन के साथ-साथ निर्देश add । एआरएम और भी शक्तिशाली है: किसी भी निर्देश का एक ऑपरेंड छोड़ा जा सकता है या दाएं मुफ्त में स्थानांतरित किया जा सकता है। तो एक संकलन-समय-स्थिरता से स्केलिंग जो कि शक्ति-2 के रूप में जाना जाता है, गुणा करने से भी अधिक कुशल हो सकता है।

ठीक है, आधुनिक दिनों में वापस ... कुछ और उपयोगी अब बिट्सफिफ्टिंग का उपयोग 16-बिट पूर्णांक में दो 8-बिट मानों को स्टोर करने के लिए करना होगा। उदाहरण के लिए, सी # में:

// Byte1: 11110000
// Byte2: 00001111

Int16 value = ((byte)(Byte1 >> 8) | Byte2));

// value = 000011111110000;

सी ++ में, कंपाइलर्स को यह आपके लिए करना चाहिए यदि आपने दो 8-बिट सदस्यों के साथ एक struct उपयोग किया है, लेकिन अभ्यास में हमेशा नहीं होता है।

मैं केवल युक्तियाँ और चाल लिख रहा हूं, परीक्षण / परीक्षाओं में उपयोगी पा सकता हूं।

1. n = n*2 : n = n<<1
2. n = n/2 : n = n>>1
3. जांच रहा है कि एन 2 की शक्ति है (1,2,4,8, ...): जांचें !(n & (n-1))
4. X का x ^वें प्राप्त करना n : n |= (1 << x)