मैं एक समारोह है:अनुकूलन सेट
inline uint32_t ShiftOf(uint32_t v)
{
for (uint32_t s = 0; s < 32; ++s)
{
if (v == 1 << s)
return s;
}
return -1;
}
वहाँ यह अनुकूलन करने के लिए कोई तरीका है?
कार्यों को अनुकूलित करने के कुछ तरीके हैं।
बिटवाइज़ ऑपरेटर्स के साथ अनुकूलन:
inline uint32_t ShiftOf(uint32_t v)
{
uint32_t s =
(bool)(v & 0xFFFF0000) * 16 +
(bool)(v & 0xFF00FF00) * 8 +
(bool)(v & 0xF0F0F0F0) * 4 +
(bool)(v & 0xCCCCCCCC) * 2 +
(bool)(v & 0xAAAAAAAA);
return v == 1 << s ? s : -1;
}
संकलक intrinsics साथ अनुकूलन:
const uint32_t g_divider = 37;
uint32_t g_hash[g_divider] = { 0 };
static void InitHash()
{
for (uint32_t s = 0; s < 32; ++s)
g_hash[(1 << s) % g_divider] = s;
}
inline uint32_t ShiftOf(uint32_t v)
{
uint32_t s = g_hash[v % g_divider];
return v == 1 << s ? s : -1;
}
मैं आम तौर पर संकलक आंतरिक की सिफारिश करता हूं, क्योंकि वे उच्च स्तर के होते हैं और इस प्रकार (सामान्य रूप से) लक्ष्य के लिए अनुकूलित कोड उत्पन्न करने की अधिक संभावना होती है। –
मुझे यकीन है कि नहीं कर रहा हूँ, लेकिन आप उतारना कर सकते हैं: एक हैश तालिका के साथ
inline uint32_t ShiftOf(uint32_t v)
{
#if defined(_MSC_VER)
DWORD s = 0;
if (!_BitScanForward(&s, v))
return -1;
#elif defined(__GNUC__)
uint32_t s = __builtin_ctz(v);
#else
# error This platform is unsupported!
#endif
return v == 1 << s ? s : -1;
}
अनुकूलन लूप:
inline uint32_t ShiftOf(uint32_t v)
{
switch (v)
{
case 0x00000001: return 0;
case 0x00000002: return 1;
case 0x00000004: return 2;
case 0x00000008: return 3;
case 0x00000010: return 4;
case 0x00000020: return 5;
case 0x00000040: return 6;
case 0x00000080: return 7;
case 0x00000100: return 8;
case 0x00000200: return 9;
case 0x00000400: return 10;
case 0x00000800: return 11;
case 0x00001000: return 12;
case 0x00002000: return 13;
case 0x00004000: return 14;
case 0x00008000: return 15;
case 0x00010000: return 16;
case 0x00020000: return 17;
case 0x00040000: return 18;
case 0x00080000: return 19;
case 0x00100000: return 20;
case 0x00200000: return 21;
case 0x00400000: return 22;
case 0x00800000: return 23;
case 0x01000000: return 24;
case 0x02000000: return 25;
case 0x04000000: return 26;
case 0x08000000: return 27;
case 0x10000000: return 28;
case 0x20000000: return 29;
case 0x40000000: return 30;
case 0x80000000: return 31;
default: return -1;
}
}
क्या इसके लिए कोई 'gcc' | 'clang' ध्वज नहीं है? '-फनोल-लूप' या कुछ? –
@ ब्लैकलाइटशिनिंग: यह एक लूप नहीं है। हालांकि मुझे लगता है कि एक लूप को अनलॉक करना जो बदले में प्रत्येक बिट स्थिति का परीक्षण करता है, अनुकूलन के साथ एक चालाक कंपाइलर में एक समान परिणाम उत्पन्न कर सकता है। – ShadowRanger
क्षमा करें, गलती से इस जवाब को कम किया। यदि आप उस उत्तर को संपादित करते हैं जो लॉक को हटा देगा और मैं इसे ठीक कर सकता हूं। –
यदि आप अधिकतम गति (कम कोड पोर्टेबिलिटी की कीमत पर) चाहते हैं, तो आधुनिक प्रोसेसर ने इसके लिए निर्देश अनुकूलित किए हैं, जो संकलक के आधार पर विभिन्न "आंतरिक फ़ंक्शन नामों" के माध्यम से सामने आते हैं।
इस ऑपरेशन के लिए सबसे आम नाम बीएसआर (बिट स्कैन रिवर्स = सबसे महत्वपूर्ण बिट का सूचकांक ढूंढें) है। एमएसवीसी के तहत, यह आंतरिक कार्यों _BitScanReverse, resps के साथ उत्पन्न किया जा सकता है। _BitScanReverse64 (उस कथन की एक अतिरिक्त मुखौटा लेने के लिए)
निम्नलिखित वेब पेज पर अधिक संदर्भ: https://en.wikipedia.org/wiki/Find_first_set
प्रति बुरा बुरा सलाह नहीं है, केवल लिंक के उत्तर की सराहना नहीं की जाती है। क्या आप कृपया उस आलेख को जोड़ सकते हैं जो आपने लिंक किया था? शायद सबसे आम कंपाइलर्स का हवाला देते हुए? –
@ मैथ्यूयू एम, अच्छा बिंदु (मैंने पोस्ट संपादित किया), धन्यवाद। – BrunoLevy
कि आप केवल तभी ठीक एक बिट सेट किया गया है पता लगाने के लिए की जरूरत है, नहीं जो एक, आप optimize this significantly कर सकते हैं:
int is_power_of_two(uint32_t v) {
return v && !(v & (v - 1));
}
आप वास्तव में गणना करने के लिए जो थोड़ा सेट किया गया है की जरूरत है, न सिर्फ एक बिट सेट कर दिया जाता है, आप a plethora of options है (या तुम सिर्फ धोखा और पुष्टि यह दोनों का एक शक्ति है के बाद C99 के log2 फ़ंक्शन का उपयोग करें और कच्चा परिणाम)।
संक्षिप्त उत्तर: बुकमार्क Bit Twiddling Hacks। यह आसान है।
आप सेट बिट्स की संख्या गिनती और देखें कि क्या वह 1.
Fast Bit Counting पेज से परामर्श करें और आप जल्दी से बिट्स की संख्या की गणना के लिए कई अलग अलग दिनचर्या मिलेगा कर सकते हैं।
सबसे तेज़ 4b है। Precompute-16bit (हालांकि यह सी में है):
static char bits_in_16bits [0x1u << 16];
int bitcount (unsigned int n) {
// works only for 32-bit ints
return bits_in_16bits [n & 0xffffu]
+ bits_in_16bits [(n >> 16) & 0xffffu];
}
Precompute_16bit कि एक सरणी bits_in_16bits [] दुकानों में Precompute_8bit का एक संस्करण है लगातार 16 बिट नंबर (शॉर्ट्स) में 1 बिट्स की संख्या।
लेकिन यह संस्करण मेमोरी की उचित मात्रा लेता है। आप अपनी आवश्यकताओं के अनुरूप एक खोजने के लिए विभिन्न संस्करणों के साथ प्रयोग कर सकते हैं।
क्या आप वास्तव में 'ShiftOf (6) == -1' चाहते हैं? – Hurkyl
@PeteBecker वह शायद "पूर्ण" log2 का मतलब था: अगर log2 (v) पूर्णांक है तो इसे वापस करें, और वापस -1। – jingyu9575
@ LưuVĩnhPhúc यह प्रश्न स्थिति को अनदेखा कर रहा है, अगर * कोई भी सेट सेट करने के लिए एक तरीका मांग रहा है। यह प्रश्न * कौन सा * सेट सेट करने के लिए एक तरीका मांग रहा है, जाहिर है कि इनपुट में केवल एक बिट सेट है। संबंधित, लेकिन डुप्लिकेट नहीं। – Bob