सबसे कम ऑर्डर बिट का सूचकांक

Question

मैं लंबे समय तक निम्नतम आदेश बिट की अनुक्रमणिका प्राप्त करने का सबसे तेज़ तरीका ढूंढना चाहता हूं। अर्थात्:

00101001001000 -> 3 

पाशन और स्थानांतरण शामिल समाधान बहुत धीमी गति से कर रहे हैं। अर्थात्:

int i; 
if(bits == 0ULL) { 
    i = 64; 
} else { 
    for(i = 0;!(bits & 1ULL);i++) 
    bits >>= 1; 
} 

संपादित करें: उपयोग

समारोह ffsll वास्तव में इसके उपयोग को कम नहीं कर सकते हैं का उपयोग करता है, लेकिन यहाँ यह (बेशक सरलीकृत) है पर जानकारी। यह सिर्फ सूचकांक के माध्यम से पुनरावृत्त करता है और उनके साथ कुछ करता है। यह फ़ंक्शन शायद अपने पूरे एप्लिकेशन में सबसे अधिक व्यापक रूप से उपयोग किया जाने वाला फ़ंक्शन है, इसके मूल्य के बहुत सारे कैशिंग के बावजूद। यह मेरे alpha-beta खोज इंजन में एक कानूनी चाल जनरेटर है।

while(bits){ 
    index = ffsll(bits); 
    doSomething(index); 
    index &= index-1; 
} 

Answer 1

इंटेल या तो सबसे कम या सर्वोच्च क्रम सेट बिट खोजने के लिए दिए गए निर्देशों का विशेष गया है। BSF आपको जो चाहिए वह लगता है। जहां तक ​​इसे सादा सी में किया जा रहा है, शायद bit twiddling hacks page में आपको जो चाहिए वह है।

कम से कम आप निबल या बाइट्स का एक तालिका का उपयोग चीजों में तेजी लाने के कर सकते हैं। ऐसा कुछ (int के लिए प्रदर्शित, लेकिन आवश्यकतानुसार लंबे समय तक आसानी से बदलने योग्य)।

/* 
0000 - 0 
0001 - 1 
0010 - 2 
0011 - 1 
0100 - 3 
0101 - 1 
0110 - 2 
0111 - 1 
1000 - 4 
1001 - 1 
1010 - 2 
1011 - 1 
1100 - 3 
1101 - 1 
1110 - 2 
1111 - 1 
*/ 

int ffs(int i) { 
    int ret = 0; 
    int j = 0; 
    static const int _ffs_tab[] = 
     { 0, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 }; 

    while((i != 0) && (ret == 0)) { 
     ret = _ffs_tab[i & 0x0f]; 

     if(ret > 0) { 
      break; 
     } 

     i >>= 4; 
     j += 4; 

     /* technically the sign bit could stay, so we mask it out to be sure */ 
     i &= INT_MAX; 
    } 

    if(ret != 0) { 
     ret += j; 
    } 

    return ret; 
} 

Answer 2

सबसे तेज़ मुझे मिला है ffsll(long long) स्ट्रिंग.h में।

Answer 3

एक प्रकार की बाइनरी खोज को कार्यान्वित करने के बारे में कैसे? कम बिट्स थोड़ा बुद्धिमान से और एक मुखौटा मूल्य कम छमाही में सभी लोगों को है कि जिसके परिणामस्वरूप में

देखो। यदि वह मान शून्य है तो आप जानते हैं कि सबसे छोटी संख्या संख्या के ऊपरी भाग में है।

अन्य बुद्धिमान चीज आधे में कटौती करें और फिर जाएं।

Answer 4

इस तरह कुछ कैसे? यह लूप की संख्या को काफी कम करता है।

int shifts = 0; 
if ((bits & 0xFFFFFFFFFFFFULL) == 0) // not in bottom 48 bits 
{ 
    shifts = 48; 
} 
else if ((bits & 0xFFFFFFFFFFULL == 0) // not in bottom 40 bits 
{ 
    shifts = 40; 
} 
else 
// etc 

bits >>= shifts; // do all the shifts at once 

// this will loop at most 8 times 
for(i = 0;!(bits & 1ULL);i++) 
    bits >>= 1; 

index = shifts + i; 

Answer 5

आप x & (~x + 1) के साथ सबसे कम सेट बिट को अलग कर सकते हैं; यह आपको सबसे कम बिट मान देता है, सूचकांक नहीं (उदा।, यदि x = 01101000, तो परिणाम 00001000 है)। सबसे तेज़ तरीका है मैं वहाँ से एक सूचकांक के लिए प्राप्त करने के बारे में पता शायद एक स्विच बयान है:

switch(x & (~x + 1)) 
{ 
    case  0ULL: index = -1; break; 
    case  1ULL: index = 0; break; 
    case  2ULL: index = 1; break; 
    case  4ULL: index = 2; break; 
    ... 
    case 9223372036854775808ULL: index = 63; break; 
} 

बदसूरत, लेकिन कोई शामिल पाशन।

Answer 6

मैंने दो कार्यों को लिखा, वे ffsll() के समान परिणाम लौट रहे हैं।

int func1(uint64_t n){ 
    if(n == 0) return 0; 
    n ^= n-1; 
    int i = 0; 
    if(n >= 1ull<<32){ n>>=32; i+=32; } 
    if(n >= 1ull<<16){ n>>=16; i+=16; } 
    if(n >= 1ull<< 8){ n>>= 8; i+= 8; } 
    if(n >= 1ull<< 4){ n>>= 4; i+= 4; } 
    if(n >= 1ull<< 2){ n>>= 2; i+= 2; } 
    if(n >= 1ull<< 1){   i+= 1; } 
    return i+1; 
} 

int func2(uint64_t n){ 
    return n? ((union ieee754_float)((float)(n^(n-1)))).ieee.exponent-126: 0; 
} 

मुझे नहीं पता कि सबसे तेज़ कौन सा है: ffsll(), func1() या func2()?

Answer 7

आप पहली बार जाँच अपने एल्गोरिथ्म की जटिलता को आधा कर सकते हैं अगर आपका नंबर अजीब या भी है। यदि यह भी आपके पास सबसे कम ऑर्डर बिट है तो पहला है।

अजीब मामलों आप इस तरह के एक द्विआधारी खोज लागू कर सकते हैं के लिए ...

Answer 8

यह 32 बिट के लिए काम कर सकते हैं। 64 तक विस्तार करने के लिए काफी आसान होना चाहिए।

// all bits left of lsb become 1, lsb & right become 0 
y = x^(-x); 

// XOR a shifted copy recovers a single 1 in the lsb's location 
u = y^(y >> 1); 

// .. and isolate the bit in log2 of number of bits 
i0 = (u & 0xAAAAAAAA) ? 1 : 0; 
i1 = (u & 0xCCCCCCCC) ? 2 : 0; 
i2 = (u & 0xF0F0F0F0) ? 4 : 0; 
i3 = (u & 0xFF00FF00) ? 8 : 0; 
i4 = (u & 0xFFFF0000) ? 16 : 0; 
index = i4 | i3 | i2 | i1 | i0; 

जाहिर है, अगर वहाँ हार्डवेयर के लिए किसी तरह है यह, जैसे कि, अगर विशेष सीपीयू निर्देश उपलब्ध हैं, कि जाने का रास्ता है।

Answer 9

तो दृश्य स्टूडियो का उपयोग कर, _BitScanForward:

• http://msdn.microsoft.com/en-us/library/wfd9z0bb(VS.80).aspx (_BitScanForward)

जीसीसी के लिए, __builtin_ctz या __builtin_ffs कोशिश:

• http://developer.apple.com/mac/library/documentation/DeveloperTools/gcc-4.0.1/gcc/Other-Builtins.html (random gcc intrinsics documentation)

हमेशा के रूप में जेनरेट कोड से परामर्श किया जाना चाहिए ताकि सही निर्देश उत्पन्न किए जा सकें।

Answer 10

यहाँ दो कार्यान्वयन, पहले intrinsics/विधानसभा द्वारा कर रहे हैं, दूसरी C/C++ (सूचकांक 0 से शुरू होता है) के द्वारा होता है

unsigned int bsf_asm(unsigned int b) 
{ 

    // b == 0 is undefined 

#if defined(\__GNUC__) 

    return __builtin_ctz(b); 

#else 

    __asm bsf eax, b; 

#endif 

} 


unsigned int bsf(unsigned int b) 
{ 

    // b == 0 is undefined 

    static const unsigned char btal[] = {0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0}; 

    int i = 0; 
    if(!(b & 0x0000ffff)) 
    { 
     b>>=16; 
     i+=16; 
    } 

    if(!(b & 0x000000ff)) 
    { 
     b>>=8; 
     i+=8; 
    } 

    if(!(b & 0x0000000f)) 
    { 
     b>>=4; 
     i+=4; 
    } 

    return i+btal[b&0x0f]; 

} 

Answer 11

सबसे सेट निम्नलिखित अभिव्यक्ति इस्तेमाल किया जा सकता सा सही प्राप्त करने के लिए

एक्स के रूप में चर पर विचार करें

एक्स & ~ (एक्स - 1) एक द्विआधारी संख्या जो बाकी के साथ ही सेट बिट शामिल देता है सभी शून्यों

उदाहरण

x  = 0101 
x-1 = 0100 
~(x-1) = 1011 

x & ~ (x - 1) = 0100 

अब लगातार सही करने के लिए इस द्विआधारी संख्या शिफ्ट जब तक संख्या शून्य है और जो सही सबसे सेट बिट संख्या देता है बदलाव की संख्या की गणना।