0x55555556 3 हैक काम से विभाजित क्यों करता है?

Question

32-बिट संख्या को तीन से विभाजित करने के लिए एक (अपेक्षाकृत) प्रसिद्ध हैक है। वास्तविक महंगी विभाजन का उपयोग करने के बजाय, संख्या को जादू संख्या 0x55555556 द्वारा गुणा किया जा सकता है, और परिणाम के ऊपरी 32 बिट्स हम जो खोज रहे हैं। उदाहरण के लिए, निम्नलिखित सी कोड:

int32_t div3(int32_t x) 
{ 
    return x/3; 
} 

इस में, जीसीसी और -O2 साथ संकलित परिणाम:

08048460 <div3>: 
8048460: 8b 4c 24 04    mov ecx,DWORD PTR [esp+0x4] 
8048464: ba 56 55 55 55   mov edx,0x55555556 
8048469: 89 c8     mov eax,ecx 
804846b: c1 f9 1f    sar ecx,0x1f 
804846e: f7 ea     imul edx 
8048470: 89 d0     mov eax,edx 
8048472: 29 c8     sub eax,ecx 
8048474: c3      ret 

मैं sub अनुदेश अनुमान लगा रहा हूँ ऋणात्मक संख्याओं फिक्सिंग के लिए जिम्मेदार है, क्योंकि उसके द्वारा यदि तर्क नकारात्मक है, तो अनिवार्य रूप से 1 जोड़ना है, और यह NOP अन्यथा है।

लेकिन क्यों यह काम करता है? मैं इस मुखौटा के 1-बाइट संस्करण द्वारा मैन्युअल रूप से छोटी संख्याओं को गुणा करने की कोशिश कर रहा हूं, लेकिन मैं एक पैटर्न देखने में असफल रहा हूं, और मुझे वास्तव में कहीं भी कोई स्पष्टीकरण नहीं मिल रहा है। ऐसा लगता है कि यह एक रहस्य जादू संख्या है जिसका मूल किसी के लिए स्पष्ट नहीं है, जैसे 0x5f3759df।

क्या कोई इस के पीछे अंकगणित का स्पष्टीकरण प्रदान कर सकता है?

Answer 1

ऐसा इसलिए है क्योंकि 0x55555556 वास्तव में 0x100000000/3 है, जो गोलाकार है।

राउंडिंग महत्वपूर्ण है। चूंकि 0x100000000 समान रूप से 3 तक विभाजित नहीं होता है, इसलिए पूर्ण 64-बिट परिणाम में कोई त्रुटि होगी। अगर वह त्रुटि नकारात्मक थी, तो निम्न 32 बिट्स के छंटनी के बाद परिणाम बहुत कम होगा। गोलाकार करके, त्रुटि सकारात्मक है, और यह सब 32 बिट्स में कम है, इसलिए छंटनी इसे मिटा देती है।