2009-02-05 12 views
8

मैं (या? :) का उपयोग किए बिना MAX या MIN के दो पूर्णांक को वापस करने के लिए एक शाखा रहित फ़ंक्शन लिखने की कोशिश कर रहा हूं। the usual technique का उपयोग करते हुए मैं यह आसानी से किसी दिए गए शब्द आकार के लिए पर्याप्त कर सकते हैं:टेम्पलेटलाइज्ड शाखा रहित int अधिकतम/मिनट फ़ंक्शन

inline int32 imax(int32 a, int32 b) 
{ 
    // signed for arithmetic shift 
    int32 mask = a - b; 
    // mask < 0 means MSB is 1. 
    return a + ((b - a) & (mask >> 31)); 
} 
अब

, arguendo कि मैं वास्तव में इन-आदेश प्रोसेसर की तरह है, जहां यह आवश्यक है पर आवेदन की तरह लिख रहा हूँ यह सोचते हैं, मेरे सवाल है क्या int के सभी आकारों में इसे सामान्यीकृत करने के लिए C++ टेम्पलेट्स का उपयोग करने का कोई तरीका है या नहीं।

>> 31 कदम केवल ज़ाहिर है, int32s के लिए काम करता है, और जब तक मैं int8, int16, और int64 के लिए समारोह पर भार के बाहर नकल कर सकता है, ऐसा लगता है जैसे मैं एक टेम्पलेट समारोह के बजाय का उपयोग करना चाहिए। लेकिन मैं बिट्स में टेम्पलेट तर्क का आकार कैसे प्राप्त करूं?

क्या इससे बेहतर करने का कोई बेहतर तरीका है? क्या मैं मुखौटा टी पर हस्ताक्षर करने के लिए मजबूर कर सकता हूं? यदि टी को हस्ताक्षर नहीं किया गया है तो मास्क-शिफ्ट चरण काम नहीं करेगा (क्योंकि यह अंकगणितीय शिफ्ट के बजाय तार्किक होगा)।

template< typename T > 
inline T imax(T a, T b) 
{ 
    // how can I force this T to be signed? 
    T mask = a - b; 
    // I hope the compiler turns the math below into an immediate constant! 
    mask = mask >> ((sizeof(T) * 8) - 1); 
    return a + ((b - a) & mask); 
} 

और, ऊपर किया है, मैं इसे कुछ भी लेकिन एक पूर्णांक प्रकार (उदाहरण के लिए, कोई तैरता या वर्ग) के लिए इस्तेमाल किया जा रहा से रोका जा सकता है?

+0

अधिकांश आधुनिक मशीनों में conditonal mov निर्देश होते हैं, जो उन्हें कोई शाखाओं के साथ न्यूनतम/अधिकतम करने में सक्षम बनाता है (उदाहरण के लिए, cmp a, b/movlt a, b)। यह उस कोड से तेज़ होगा जो आप उत्पन्न करने की योजना बना रहे हैं, और कंपाइलर्स उनके बारे में जानते हैं। क्या आप सुनिश्चित हैं कि आपका कंपाइलर पहले से ही आपके लिए ऐसा नहीं करता है? –

+1

@IraBaxter बिल्कुल यकीन है; मैं हमेशा इसके असेंबली आउटपुट को देखता हूं। इसके अलावा, मैं जिस प्रोसेसर को लक्षित करता हूं (ए पावरपीसी व्युत्पन्न) निश्चित रूप से एक cmov नहीं मिला है। – Crashworks

+1

जो भी कोड आप लिखते हैं, वह केवल सी ++ स्रोत के रूप में शाखा रहित होगा। कंपाइलर सशर्त कूद (यानी शाखाएं) उत्पन्न किए बिना उत्पन्न कर सकता है अगर/else /? /:, और इसके विपरीत अगर/अन्य स्रोत से अनुकूलित शाखा रहित निर्देश उत्पन्न हो सकते हैं। – galinette

उत्तर

8

आम तौर पर, अच्छा लग रहा है, लेकिन 100% पोर्टेबिलिटी के लिए, उस 8 को CHAR_BIT (या numeric_limits :: max()) से प्रतिस्थापित करें क्योंकि यह गारंटी नहीं है कि वर्ण 8-बिट हैं।

कोई भी अच्छा कंपाइलर संकलन समय पर सभी गणित स्थिरांक को मर्ज करने के लिए पर्याप्त स्मार्ट होगा।

आप इसे एक प्रकार के गुण पुस्तकालय का उपयोग करके हस्ताक्षरित करने के लिए मजबूर कर सकते हैं। जो आम तौर पर की तरह (अपने numeric_traits संभालने पुस्तकालय numeric_traits कहा जाता है) कुछ ऐसा दिखाई देगा:

typename numeric_traits<T>::signed_type x; 

एक मैन्युअल रूप से लुढ़का numeric_traits हैडर का एक उदाहरण ऐसा दिखाई दे सकता: http://rafb.net/p/Re7kq478.html (वहाँ अतिरिक्त के लिए कमरे के बहुत सारे है, लेकिन आप मिल विचार)।

या बेहतर अभी तक, उपयोग को बढ़ावा देने:

typename boost::make_signed<T>::type x; 

संपादित करें: IIRC, पर हस्ताक्षर किए सही बदलाव नहीं अंकगणित होना जरूरी है। यह आम है, और निश्चित रूप से मेरे द्वारा उपयोग किए गए प्रत्येक कंपाइलर के मामले में। लेकिन मेरा मानना ​​है कि मानक इसे कंपाइलर को छोड़ देता है चाहे सही बदलाव अंकगणित हों या हस्ताक्षरित प्रकार पर न हों। मसौदा मानक की मेरी कॉपी में निम्नलिखित लिखा है:

की E1 >> E2 मूल्य E1 E2 बिट पदों rightshifted है। ई 1 एक अहस्ताक्षरित प्रकार है या यदि E1 एक पर हस्ताक्षर किए प्रकार और ग़ैर-ऋणात्मक मान होता है, परिणाम का मूल्य E1 के भागफल मात्रा 2 बिजली E2 उठाया से विभाजित अभिन्न अंग है। यदि ई 1 पर हस्ताक्षरित प्रकार और ऋणात्मक मान है, तो परिणामी मान कार्यान्वयन परिभाषित किया गया है।

लेकिन जैसा कि मैंने कहा, यह मैंने देखा है कि हर कंपाइलर पर काम करेगा: -पी।

+4

मेरा दिमाग कल्पना करने के लिए कि कंपेलर कार्यान्वयनकर्ता के दिल में क्या हो सकता है, जो हस्ताक्षर को संरक्षित नहीं करता है। CHAR_BIT का उल्लेख करने के लिए – Crashworks

+0

+1 और हस्ताक्षरित दाएं बदलाव (मेरे लिए दोनों समाचार) की कार्यान्वयन-परिभाषा, लेकिन ध्यान दें कि स्वत: टेम्पलेट प्रकार की कटौती टी को किसी प्रकार के लिए टी नहीं कर सकती है जैसे "numeric_traits :: sign_type" - आपको आवश्यकता होगी इसके बजाय enable_if का उपयोग करने के लिए। (जैसा कि grepsedawk द्वारा उल्लिखित है।) –

+0

@j_random_hacker: मुझे नहीं लगता कि यह क्यों काम नहीं करेगा यदि आपने किया: int x = imax (5, 4); दुर्भाग्य से PowerPC पर enable_if –

2

आप Boost.TypeTraits लाइब्रेरी को देखना चाहते हैं। यह पता लगाने के लिए कि कोई प्रकार हस्ताक्षरित है या नहीं, आप is_signed विशेषता का उपयोग कर सकते हैं। आप कुछ प्रकार के लिए ओवरलोड को हटाने के लिए enable_if/disable_if पर भी देख सकते हैं।

2

यहां शाखा रहित अधिकतम और न्यूनतम के लिए एक और दृष्टिकोण है। इसके बारे में क्या अच्छा है कि यह किसी भी बिट चाल का उपयोग नहीं करता है और आपको इस प्रकार के बारे में कुछ भी नहीं पता है।

template <typename T> 
inline T imax (T a, T b) 
{ 
    return (a > b) * a + (a <= b) * b; 
} 

template <typename T> 
inline T imin (T a, T b) 
{ 
    return (a > b) * b + (a <= b) * a; 
} 
+2

की आवश्यकता नहीं है, पूर्णांक गुणा एक माइक्रोक्रोडेड ऑपरेशन है जो पाइपलाइन को मृत करता है, और यह भी एक गलत रिपोर्ट वाली शाखा से धीमा है। – Crashworks

+2

@ क्रैशवर्क्स मैंने x86_64 पर कुछ प्रोग्राम में यह कोशिश की, और यह सामान्य शाखा दृष्टिकोण से वास्तव में धीमी थी। –

+0

'(- (एक <= बी) और ए) के बारे में क्या है। (- (बी <= ए) और बी) '? –

संबंधित मुद्दे