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




multiplication bit-manipulation (4)

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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


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

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

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

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

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


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

"कुछ 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 आपको शुरू करना चाहिए।


(मैंने इसे पहले कभी नहीं देखा होगा। यह चाल बहुत बढ़िया है!)

मैं फ्लोरिस के इस धारणा पर थोड़ा सा विस्तार करूंगा कि n बिट्स निकालने पर आपको किसी भी गैर-लगातार बिट्स के बीच n-1 स्पेस की आवश्यकता होती है:

मेरा प्रारंभिक विचार (हम एक मिनट में देखेंगे कि यह कैसे काम नहीं करता है) यह था कि आप बेहतर कर सकते हैं: यदि आप n बिट्स निकालना चाहते हैं, तो आपके पास कोई निकालना होगा यदि आप किसी को भी निकालने / स्थानांतरित कर रहे हैं (बिट i साथ लगातार नहीं) i-1 बिट्स के बाद या बाद में ni बिट्स में।

मैं उदाहरण के लिए कुछ उदाहरण दूंगा:

...a..b...c... काम करता है (किसी के बाद 2 बिट्स a , थोड़ा पहले और b बाद थोड़ा, और c से पहले 2 बिट्स में कोई भी नहीं है):

  a00b000c
+ 0b000c00
+ 00c00000
= abc.....

...ab...c... विफलता है क्योंकि b a बाद 2 बिट्स में a (और जब हम a स्थानांतरित करते हैं तो किसी और के स्थान में खींच लिया जाता a ):

  a0b0000c
+ 0b0000c0
+ 00c00000
= abX.....

...a...bc.. विफलता है क्योंकि b c पहले 2 बिट्स में है (और जब हम c स्थानांतरित करते हैं तो किसी और के स्थान पर धकेल जाता है):

  a000b0c0
+ 0b0c0000
+ b0c00000
= Xbc.....

...a...bc...d... काम करता है क्योंकि लगातार बिट्स एक साथ स्थानांतरित होते हैं:

  a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000

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

...a...b..c...d... ले जाने के लिए संभावित विफलता, c b बाद n-1 , लेकिन n-1 मानदंडों को पूरा करता है:

  a000b00c000d
+ 0b00c000d000
+ 00c000d00000
+ 000d00000000
= abcdX.......

तो हम वापस "अंतरिक्ष के n-1 बिट्स" आवश्यकता पर वापस क्यों नहीं जाते? क्योंकि हम बेहतर कर सकते हैं :

...a....b..c...d.. "अंतरिक्ष के n-1 बिट्स" परीक्षण विफल रहता है, लेकिन हमारे बिट निकालने वाली चाल के लिए काम करता है :

+ a0000b00c000d00
+ 0b00c000d000000
+ 00c000d00000000
+ 000d00000000000
= abcd...0X......

मैं इन क्षेत्रों को दर्शाने के लिए एक अच्छे तरीके से नहीं आ सकता हूं जिनके पास महत्वपूर्ण बिट्स के बीच n-1 स्पेस नहीं है, लेकिन फिर भी हमारे ऑपरेशन के लिए काम करेंगे। हालांकि, चूंकि हम समय से पहले जानते हैं कि जिन बिट्स में हम रुचि रखते हैं, हम यह सुनिश्चित करने के लिए अपने फ़िल्टर की जांच कर सकते हैं कि हमें कैर-बिट टकराव का अनुभव नहीं होता है:

तुलना करें (-1 AND mask) * shift अपेक्षित सभी परिणामों के खिलाफ (-1 AND mask) * shift , -1 << (64-n) (64-बिट के लिए हस्ताक्षरित)

जादू शिफ्ट / हमारे बिट्स निकालने के लिए गुणा करते हैं यदि केवल और दोनों बराबर हैं तो काम करता है।





bit-manipulation