c एक गुणा के साथ बिट्स निकालना




multiplication bit-manipulation (4)

मैंने एक और सवाल के answer में इस्तेमाल की जाने वाली एक रोचक तकनीक देखी, और इसे थोड़ा बेहतर समझना चाहूंगा।

हमें एक हस्ताक्षरित 64-बिट पूर्णांक दिया गया है, और हम निम्नलिखित बिट्स में रूचि रखते हैं:

1.......2.......3.......4.......5.......6.......7.......8.......

विशेष रूप से, हम उन्हें शीर्ष आठ पदों पर ले जाना चाहते हैं, जैसे:

12345678........................................................

हम संकेतित बिट्स के मूल्य के बारे में परवाह नहीं करते हैं . , और उन्हें संरक्षित नहीं किया जाना चाहिए।

answer अवांछित बिट्स को मुखौटा करना था, और परिणाम 0x2040810204081 गुणा करना था। यह, जैसा कि यह निकलता है, चाल करता है।

यह विधि कितनी सामान्य है? क्या इस तकनीक का उपयोग बिट्स के किसी भी सबसेट को निकालने के लिए किया जा सकता है? यदि नहीं, तो यह कैसे पता लगाता है कि विधि बिट्स के किसी विशेष सेट के लिए काम करती है या नहीं?

अंत में, दिए गए बिट्स निकालने के लिए (ए?) सही गुणक को खोजने के बारे में कोई कैसे जाएगा?


गुणक में प्रत्येक 1-बिट का उपयोग बिट्स में से किसी एक को अपनी सही स्थिति में कॉपी करने के लिए किया जाता है:

  • 1 पहले से ही सही स्थिति में है, इसलिए 0x0000000000000001 गुणा करें।
  • 2 को 7 बिट पदों को बाईं ओर स्थानांतरित किया जाना चाहिए, इसलिए हम 0x0000000000000080 (बिट 7 सेट है) से गुणा करें।
  • 3 को 14 बिट पदों को बाईं ओर स्थानांतरित किया जाना चाहिए, इसलिए हम 0x0000000000000400 (बिट 14 सेट) से गुणा करते हैं।
  • और इतने पर
  • 8 को 49 बिट पदों को बाईं ओर स्थानांतरित किया जाना चाहिए, इसलिए हम 0x0002000000000000 (बिट 49 सेट) से गुणा करते हैं।

गुणक व्यक्तिगत बिट्स के लिए गुणक का योग है।

यह केवल इसलिए काम करता है क्योंकि एकत्रित बिट्स एक साथ बहुत करीब नहीं हैं, ताकि बिट्स का गुणा जो हमारी योजना में एक साथ नहीं है या तो 64 बिट से कम या निचले हिस्से में भाग नहीं लेता है।

ध्यान दें कि मूल संख्या में अन्य बिट्स 0 होना चाहिए। इसे एक और ऑपरेशन के साथ मास्क करके हासिल किया जा सकता है।


इस बहुत ही रोचक सवाल के पहले से ही उत्कृष्ट उत्तर के अलावा, यह जानना उपयोगी हो सकता है कि 2007 के बाद से कंप्यूटर शतरंज समुदाय में यह बिटवाई गुणात्मक चाल ज्ञात है, जहां यह मैजिक बिटबोर्ड के नाम पर है।

कई कंप्यूटर शतरंज इंजन विभिन्न टुकड़े सेट (1 वर्ग प्रति कब्जे वाले वर्ग) का प्रतिनिधित्व करने के लिए कई 64-बिट पूर्णांक (बिटबोर्ड कहा जाता है) का उपयोग करते हैं। मान लीजिए कि एक निश्चित मूल वर्ग पर एक स्लाइडिंग टुकड़ा (रूक, बिशप, रानी) अधिकांश K वर्गों में स्थानांतरित हो सकता है यदि कोई अवरुद्ध टुकड़ा मौजूद नहीं था। Bitwise का उपयोग करना और कब्जे वाले वर्गों के बिटकबोर्ड के साथ बिखरे हुए बिट बिट्स का एक 64-बिट पूर्णांक के भीतर एम्बेडेड एक विशिष्ट K बिट शब्द देता है।

मैजिक गुणा का उपयोग इन बिखरे हुए K बिट्स को 64-बिट पूर्णांक के निचले K बिट्स पर मैप करने के लिए किया जा सकता है। इन निचले K बिट्स का उपयोग पूर्व-गणना वाले बिटबोर्ड की एक तालिका को इंडेक्स करने के लिए किया जा सकता है जो अनुमत वर्गों का प्रतिनिधित्व करते हैं कि इसके मूल वर्ग का टुकड़ा वास्तव में स्थानांतरित हो सकता है (टुकड़ों को अवरुद्ध करने की देखभाल आदि)

इस दृष्टिकोण का उपयोग करते हुए एक ठेठ शतरंज इंजन में 64 प्रविष्टियों (एक प्रति मूल वर्ग) में 2 टेबल (एक रशों के लिए, बिशप के लिए एक, दोनों के संयोजन का उपयोग करके क्वींस) होते हैं जिनमें पूर्व-गणना वाले परिणाम होते हैं। उच्चतम रेटेड बंद स्रोत ( Houdini ) और ओपन सोर्स शतरंज इंजन ( Stockfish ) दोनों वर्तमान में अपने उच्च प्रदर्शन के लिए इस दृष्टिकोण का उपयोग करते हैं।

इन जादू गुणकों को ढूंढना या तो एक संपूर्ण खोज (प्रारंभिक कटऑफ के साथ अनुकूलित) या परीक्षण और erorr (उदाहरण के लिए यादृच्छिक 64-बिट पूर्णांक की कोशिश कर रहा है) का उपयोग कर किया जाता है। चाल पीढ़ी के दौरान उपयोग किए जाने वाले कुछ पैटर्न नहीं थे जिसके लिए कोई जादू निरंतर नहीं पाया जा सकता था। हालांकि, बिट-कैप्चर प्रभाव आमतौर पर आवश्यक होते हैं जब टू-मैप किए गए बिट्स (लगभग) आसन्न सूचकांक होते हैं।

AFAIK, @Syzygy द्वारा बहुत सामान्य एसएटी-सॉल्वर दृष्टिकोण का उपयोग कंप्यूटर शतरंज में नहीं किया गया है, और न ही ऐसे जादू स्थिरांक के अस्तित्व और विशिष्टता के संबंध में कोई औपचारिक सिद्धांत प्रतीत होता है।


वास्तव में बहुत दिलचस्प सवाल है। मैं अपने दो सेंट के साथ चिंतन कर रहा हूं, यही वह है, यदि आप बिटकवेक्टर सिद्धांत पर प्रथम क्रम तर्क के संदर्भ में इस तरह की समस्याओं को राज्य में प्रबंधित कर सकते हैं, तो प्रमेय समर्थक आपका मित्र हैं, और संभावित रूप से आपको बहुत तेजी से प्रदान कर सकते हैं आपके सवालों के जवाब। आइए प्रमेय के रूप में पूछे जाने वाले समस्या को दोबारा बताएं:

"कुछ 64-बिट स्थिरांक 'मास्क' और 'मल्टीप्लिकैंड' मौजूद हैं, जैसे सभी 64-बिट बिटवेक्टर x के लिए, अभिव्यक्ति y = (x & mask) * multiplicand में, हमारे पास y.63 == x.63 है , y.62 == x.55, y.61 == x.47, आदि "

यदि यह वाक्य वास्तव में एक प्रमेय है, तो यह सच है कि स्थिरांक 'मास्क' और 'मल्टीप्लिकैंड' के कुछ मूल्य इस संपत्ति को संतुष्ट करते हैं। तो आइए इसे ऐसा कुछ बताएं जो एक प्रमेय समर्थक समझ सकता है, अर्थात् एसएमटी-एलआईबी 2 इनपुट:

(set-logic BV)

(declare-const mask         (_ BitVec 64))
(declare-const multiplicand (_ BitVec 64))

(assert
  (forall ((x (_ BitVec 64)))
    (let ((y (bvmul (bvand mask x) multiplicand)))
      (and
        (= ((_ extract 63 63) x) ((_ extract 63 63) y))
        (= ((_ extract 55 55) x) ((_ extract 62 62) y))
        (= ((_ extract 47 47) x) ((_ extract 61 61) y))
        (= ((_ extract 39 39) x) ((_ extract 60 60) y))
        (= ((_ extract 31 31) x) ((_ extract 59 59) y))
        (= ((_ extract 23 23) x) ((_ extract 58 58) y))
        (= ((_ extract 15 15) x) ((_ extract 57 57) y))
        (= ((_ extract  7  7) x) ((_ extract 56 56) y))
      )
    )
  )
)

(check-sat)
(get-model)

और अब प्रमेय समर्थक जेड 3 से पूछें कि क्या यह एक प्रमेय है:

z3.exe /m /smt2 ExtractBitsThroughAndWithMultiplication.smt2

परिणाम है:

sat
(model
  (define-fun mask () (_ BitVec 64)
    #x8080808080808080)
  (define-fun multiplicand () (_ BitVec 64)
    #x0002040810204081)
)

बिंगो! यह मूल पोस्ट में 0.06 सेकंड में दिए गए परिणाम को पुन: उत्पन्न करता है।

इसे एक और सामान्य परिप्रेक्ष्य से देखते हुए, हम इसे पहली ऑर्डर प्रोग्राम संश्लेषण समस्या का उदाहरण मान सकते हैं, जो शोध के नवजात क्षेत्र के बारे में है जिसके बारे में कुछ कागजात प्रकाशित किए गए हैं। "program synthesis" filetype:pdf लिए एक खोज "program synthesis" filetype:pdf आपको शुरू करना चाहिए।


बहुत ही रोचक सवाल, और चालाक चाल।

आइए एक बाइट छेड़छाड़ करने का एक सरल उदाहरण देखें। सादगी के लिए हस्ताक्षर किए गए 8 बिट का उपयोग करना। कल्पना करें कि आपका नंबर xxaxxbxx और आप ab000000 चाहते हैं।

समाधान में दो कदम होते थे: थोड़ी मास्किंग, गुणा के बाद। बिट मास्क एक साधारण और ऑपरेशन है जो शून्य के लिए अनिच्छुक बिट्स को बदल देता है। उपरोक्त मामले में, आपका मुखौटा 00100100 होगा और परिणाम 00a00b00

अब कठिन हिस्सा: इसे ab...... में बदल रहा है ab......

एक गुणा शिफ्ट-एंड-एड ऑपरेशंस का एक गुच्छा है। कुंजी है कि ओवरफ्लो को बिट्स को "दूर" करने की अनुमति दें, जिनकी हमें आवश्यकता नहीं है और जिन्हें हम सही जगह पर रखना चाहते हैं।

4 ( 00000100 ) द्वारा गुणा सबकुछ 2 से छोड़ा जाएगा और आपको a00b0000b को आगे बढ़ने के लिए हमें 1 से गुणा करने की आवश्यकता है (सही स्थान पर रखने के लिए) + 4 (बी को स्थानांतरित करने के लिए)। यह योग 5 है, और पहले 4 के साथ संयुक्त हम 20, या 00010100 का जादू संख्या प्राप्त 00010100 । मास्किंग के बाद मूल 00a00b00 था; गुणा देता है:

000000a00b000000
00000000a00b0000 +
----------------
000000a0ab0b0000
xxxxxxxxab......

इस दृष्टिकोण से आप बड़ी संख्या और अधिक बिट्स तक बढ़ा सकते हैं।

आपके द्वारा पूछे गए प्रश्नों में से एक था "क्या यह किसी भी बिट्स के साथ किया जा सकता है?" मुझे लगता है कि जवाब "नहीं" है, जब तक आप कई मास्किंग परिचालनों, या कई गुणाओं की अनुमति नहीं देते। समस्या "टकराव" का मुद्दा है - उदाहरण के लिए, ऊपर की समस्या में "भटकना बी"। कल्पना कीजिए कि हमें xaxxbxxcx जैसे नंबर पर ऐसा करने की आवश्यकता है। पहले के दृष्टिकोण के बाद, आपको लगता है कि हमें {x 2, x {1 + 4 + 16}} = x 42 (ओह - सब कुछ का जवाब चाहिए!) की आवश्यकता है। परिणाम:

00000000a00b00c00
000000a00b00c0000
0000a00b00c000000
-----------------
0000a0ababcbc0c00
xxxxxxxxabc......

जैसा कि आप देख सकते हैं, यह अभी भी काम करता है, लेकिन "केवल बस"। वे यहां कुंजी हैं कि बिट्स के बीच "पर्याप्त जगह" है जो हम चाहते हैं कि हम सब कुछ निचोड़ सकें। मैं सी के बाद चौथा बिट डी नहीं जोड़ सका, क्योंकि मुझे ऐसे उदाहरण मिलेंगे जहां मुझे सी + डी मिलती है, बिट्स ले जा सकते हैं ...

तो औपचारिक प्रमाण के बिना, मैं आपके प्रश्न के अधिक दिलचस्प हिस्सों का उत्तर निम्नानुसार दूंगा: "नहीं, यह किसी भी बिट्स के लिए काम नहीं करेगा। एन बिट्स निकालने के लिए, आपको उन बिट्स के बीच रिक्त स्थान (एन -1) रिक्त स्थान चाहिए जिन्हें आप चाहते हैं निकालें, या अतिरिक्त मुखौटा-गुणा कदम है। "

एकमात्र अपवाद जो मैं सोच सकता हूं "बिट्स के बीच शून्य (एन -1) शून्य होना चाहिए" नियम यह है: यदि आप मूल में एक-दूसरे के समीप दो बिट्स निकालना चाहते हैं, और आप उन्हें रखना चाहते हैं एक ही आदेश, तो आप अभी भी कर सकते हैं। और (एन -1) नियम के उद्देश्य के लिए वे दो बिट्स के रूप में गिना जाता है।

एक और अंतर्दृष्टि है - नीचे @ टर्नरी के जवाब से प्रेरित (वहां मेरी टिप्पणी देखें)। प्रत्येक रोचक बिट के लिए, आपको इसके दाईं ओर केवल ज़ीरो की आवश्यकता होती है क्योंकि आपको वहां जाने की आवश्यकता वाले बिट्स के लिए स्थान की आवश्यकता होती है। लेकिन इसके अलावा, इसे बाईं ओर कई बिट्स की आवश्यकता है क्योंकि इसके परिणामस्वरूप बाएं हैं। तो यदि थोड़ा बी बी की स्थिति एम में समाप्त होता है, तो इसके बाईं ओर एम-1 शून्य होना चाहिए, और एनएम शून्य अपने दाहिने ओर होना चाहिए। खासकर जब बिट्स मूल संख्या में उसी क्रम में नहीं होते हैं क्योंकि वे पुन: क्रम के बाद होंगे, यह मूल मानदंडों में एक महत्वपूर्ण सुधार है। इसका मतलब है, उदाहरण के लिए, यह एक 16 बिट शब्द है

a...e.b...d..c..

में स्थानांतरित किया जा सकता है

abcde...........

भले ही ई और बी के बीच केवल एक स्थान है, डी और सी के बीच दो, दूसरों के बीच तीन। एन -1 के साथ जो भी हुआ ?? इस मामले में, a...e "एक ब्लॉक" बन जाता है - उन्हें सही स्थान पर समाप्त होने के लिए 1 से गुणा किया जाता है, और इसलिए "हमें मुफ्त में ई मिल गया"। बी और डी के लिए भी यही सच है (बी को दाईं ओर तीन रिक्त स्थान की आवश्यकता है, डी को अपने बाईं ओर एक ही तीन की जरूरत है)। तो जब हम जादू संख्या की गणना करते हैं, तो हम पाते हैं कि डुप्लिकेट हैं:

a: << 0  ( x 1    )
b: << 5  ( x 32   )
c: << 11 ( x 2048 )
d: << 5  ( x 32   )  !! duplicate
e: << 0  ( x 1    )  !! duplicate

जाहिर है, अगर आप इन नंबरों को एक अलग क्रम में चाहते थे, तो आपको उन्हें आगे स्थान देना होगा। हम (N-1) नियम को सुधार सकते हैं: "यह हमेशा काम करेगा यदि बिट्स के बीच कम से कम (एन -1) रिक्त स्थान हैं; या, यदि अंतिम परिणाम में बिट्स का क्रम ज्ञात है, तो यदि थोड़ा बी समाप्त होता है एन की स्थिति एम में, इसके बाईं ओर एम -1 शून्य, और एनएम शून्य अपने दाहिनी ओर होना चाहिए। "

@ टर्नरी ने इंगित किया कि यह नियम काफी काम नहीं करता है, क्योंकि "लक्ष्य क्षेत्र के दाहिने ओर" जोड़कर बिट्स से एक कैरी हो सकती है - यानी, जब हम जिन बिट्स की तलाश कर रहे हैं वे सभी हैं। उदाहरण के साथ मैंने 16 बिट शब्द में पांच कसकर पैक किए गए बिट्स के साथ ऊपर दिया: यदि हम साथ शुरू करते हैं

a...e.b...d..c..

सादगी के लिए, मैं बिट स्थिति ABCDEFGHIJKLMNOP नाम दूंगा

गणित हम करने जा रहे थे

ABCDEFGHIJKLMNOP

a000e0b000d00c00
0b000d00c0000000
000d00c000000000
00c0000000000000 +
----------------
abcded(b+c)0c0d00c00

अब तक, हमने सोचा था कि abcde (पदों ABCDE ) से कोई फर्क नहीं पड़ता, लेकिन वास्तव में, जैसा कि @ टर्नरी ने बताया, यदि b=1, c=1, d=1 फिर (b+c) स्थिति G एक कारण होगा स्थिति F को ले जाने के लिए थोड़ा, जिसका मतलब है कि स्थिति में (d+1) F में थोड़ा सा होगा - और हमारा परिणाम खराब हो गया है। ध्यान दें कि ब्याज के कम से कम महत्वपूर्ण बिट (इस उदाहरण में c ) के दायरे में कोई फर्क नहीं पड़ता है, क्योंकि गुणा से कम से कम महत्वपूर्ण बिट से शून्य के साथ पैडिंग का कारण बनता है।

इसलिए हमें अपने (एम -1) / (एनएम) नियम को संशोधित करने की आवश्यकता है। यदि एक से अधिक बिट हैं जिनमें "बिल्कुल (एनएम) अप्रयुक्त बिट्स दाईं ओर हैं (पैटर्न में अंतिम बिट की गणना नहीं - उपरोक्त उदाहरण में" सी "), तो हमें नियम को मजबूत करने की आवश्यकता है - और हमें ऐसा करो!

हमें न केवल उन बिट्स की संख्या पर देखना होगा जो (एनएम) मानदंड को पूरा करते हैं, लेकिन जो भी हैं (एन-एम + 1), आदि। चलो अपने नंबर Q0 (बिल्कुल अगले बिट पर अगली बिट) पर कॉल करें, क्यू 1 (एन-एम + 1), क्यू (एन -1) (एन -1) तक। फिर हम जोखिम लेते हैं अगर

Q0 > 1
Q0 == 1 && Q1 >= 2
Q0 == 0 && Q1 >= 4
Q0 == 1 && Q1 > 1 && Q2 >=2
... 

यदि आप इसे देखते हैं, तो आप देख सकते हैं कि यदि आप एक साधारण गणितीय अभिव्यक्ति लिखते हैं

W = N * Q0 + (N - 1) * Q1 + ... + Q(N-1)

और परिणाम W > 2 * N , तो आपको एक बिट से (n-m+1) आरएचएस मानदंड बढ़ाने की जरूरत है। इस बिंदु पर, ऑपरेशन सुरक्षित है जब तक W < 4 ; अगर यह काम नहीं करता है, तो मानदंड को और बढ़ाएं, इत्यादि।

मुझे लगता है कि उपरोक्त के बाद आपको अपने उत्तर का लंबा रास्ता मिल जाएगा ...





bit-manipulation