एक पूर्णांक के बिट्स के माध्यम से गणना करने का सबसे तेज़ तरीका

Question

एक पूर्णांक के माध्यम से गणना करने का सबसे तेज़ तरीका क्या है और प्रत्येक बिट के एक्सपोनेंट को वापस करने का सबसे तेज़ तरीका क्या है? < < और दूसरा Math.Pow का उपयोग करके एक उदाहरण देखा है। आश्चर्य है कि अगर कुछ और है जो वास्तव में तेज़ है।

धन्यवाद।

Answer 1

मुझे लगता है कि बिट-स्थानांतरण सबसे तेज़ होगा। अनचाहे, लेकिन मुझे लगता है कि निम्नलिखित तेजी से होना चाहिए (जितना तेज़ी से IENumerables कम से कम हैं)।

IEnumerable<int> GetExponents(Int32 value) 
{ 
    for(int i=0; i<32; i++) 
    { 
     if(value & 1) 
      yield return i; 
     value >>= 1; 
    } 
} 

आप यह तेजी से होना चाहते हैं, आप के बजाय एक List<int> लौटने की सोच सकते हैं।

Answer 2

मुझे लगता है कि बिट स्थानांतरण (< <) सबसे तेज़ है।

Answer 3

एक बाइट के लाइट बिट्स के लिए एक लुकअप सरणी सुरक्षित सी # कोड में आप जितनी तेजी से कर सकते हैं, उसके करीब होना चाहिए। पूर्णांक से 4 बाइट्स में से प्रत्येक को शिफ्ट करें (आवश्यकतानुसार यूआईटी कास्टिंग करें) और सरणी में अनुक्रमणिका।

लुकअप सरणी के तत्व एक्सपोनेंट्स की एक सरणी हो सकते हैं, या बिट्स के साथ आप जो कर रहे हैं उसके आधार पर, शायद काम करने वाले प्रतिनिधियों के आधार पर।

Answer 4

सबसे तेज़ इनपुट के लिए क्या वितरण दिया गया? यदि आमतौर पर केवल एक बिट सेट किया जाता है, तो यह सेट बिट्स की तलाश में लूपिंग से तेज़ हो सकता है।

position of the least significant bit, जो Bit Twiddling Hacks से ले लिया खोजने के लिए स्वीकार किए जाते हैं जवाब से लेते हुए इस समाधान लूप होता है, पाने के समाशोधन और प्रत्येक लगातार कम से कम-महत्वपूर्ण बिट की स्थिति लौटने।

static int[] MulDeBruijnBitPos = new int[32] 
    { 
     0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
     31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
    }; 

    static IEnumerable<int> GetExponents(UInt32 v) 
    { 
     UInt32 m; 

     while(v != 0) { 
      m = (v & (UInt32) (-v)); 
      yield return MulDeBruijnBitPos[((UInt32) (m * 0x077CB531U)) >> 27]; 
      v ^= m; 
     } 
    } 

यह बिट्स सेट के रूप में कई बार लूप करता है।

Answer 5

सबसे तेज़ रास्ता? लुकअप टेबल लगभग हमेशा सबसे तेज़ तरीका हैं। चार int प्रविष्टियों के साथ एक int [] [] सरणी बनाएं, प्रत्येक int के लिए एक, जिसमें आप चाहते हैं कि संख्याओं की एक सरणी शामिल है। तालिका शुरू करने में निश्चित रूप से कुछ समय लगेगा, लेकिन लुकअप अविश्वसनीय रूप से तेज़ होगा।

मुझे लगता है कि आपने यह नहीं कहा है कि किसी के लिए वास्तव में प्रश्न का उत्तर देने के लिए पर्याप्त "सटीक" का अर्थ क्या है। क्या इसका मतलब स्टार्टअप समय सहित सबसे तेज़ अमूर्त समय है, या मामूली लुकअप समय यह मानते हुए कि स्टार्टअप लागत को उपेक्षित किया जा सकता है? मेरा समाधान स्केच बाद वाले मानता है।

स्पष्ट रूप से 2 बिलियन बाइट्स एड्रेस स्पेस के साथ 32 बिट मशीन में तीस अरब बाइट ऑफ एरे स्टोर करने के लिए पर्याप्त पता स्थान नहीं होगा। खुद को एक 64 बिट मशीन प्राप्त करें। आपको कम से कम इतनी भौतिक मेमोरी स्थापित करने की आवश्यकता होगी, साथ ही यदि आप इसे तेज करना चाहते हैं - पेजिंग आपको अन्यथा मारने जा रही है।

मुझे यकीन है कि आप प्रत्येक लुकअप पर सहेजे गए नैनोसेकंड के जोड़े को अतिरिक्त हार्डवेयर खरीदने के लायक हैं। या शायद आप वास्तव मेंसबसे तेज़ तरीका चाहते हैं?

:-)

Answer 6

बस मस्ती के लिए, यहाँ एक एक लाइनर LINQ का उपयोग कर रहा है।

यह निश्चित रूप से ऐसा करने का सबसे तेज़ तरीका नहीं है, हालांकि यह yield और इटरेटर ब्लॉक का उपयोग करने वाले अन्य उत्तरों के पीछे नहीं है।

int test = 42; 

// returns 1, 3, 5 
// 2^1 + 2^3 + 2^5 
// = 2 + 8 + 32 
// = 42 
var exponents = Enumerable.Range(0, 32).Where(x => ((test >> x) & 1) == 1); 

एक तेज समाधान के लिए मैं शायद एक इटरेटर ब्लॉक का उपयोग करने के बजाय एक सादा संग्रह वापस कर दूंगा। कुछ ऐसा:

int test = 2458217; 

// returns 0, 3, 5, 6, 9, 15, 16, 18, 21 
// 2^0 + 2^3 + 2^5 + 2^6 + 2^9 + 2^15 + 2^16 + 2^18 + 2^21 
// = 1 + 8 + 32 + 64 + 512 + 32768 + 65536 + 262144 + 2097152 
// = 2458217 
var exponents = GetExponents(test); 

// ... 

public static List<int> GetExponents(int source) 
{ 
    List<int> result = new List<int>(32); 

    for (int i = 0; i < 32; i++) 
    { 
     if (((source >> i) & 1) == 1) 
     { 
      result.Add(i); 
     } 
    } 

    return result; 
} 

Answer 7

IEnumerable प्रदर्शन करने वाला नहीं है।

static uint[] MulDeBruijnBitPos = new uint[32] 
{ 
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
}; 

static uint[] GetExponents(uint value) 
{ 
    uint[] data = new uint[32]; 
    int enabledBitCounter = 0; 

    while (value != 0) 
    { 
     uint m = (value & (0 - value)); 
     value ^= m; 
     data[enabledBitCounter++] = MulDeBruijnBitPos[(m * (uint)0x077CB531U) >> 27]; 
    } 

    Array.Resize<uint>(ref data, enabledBitCounter); 
    return data; 
} 

एक और संस्करण (दूसरा सबसे तेज - 10M रन देकर 3 सेकंड, रेंज: -

पहले एक (10M रन रेंज 1..10M के लिए 2.35 सेकंड सबसे तेजी से): इस विषय में कुछ उदाहरण के अनुकूलन 1..10M):

static uint[] GetExponents(uint value) 
{ 
    uint[] data = new uint[32]; 
    int enabledBitCounter = 0; 

    for (uint i = 0; value > 0; ++i) 
    { 
     if ((value & 1) == 1) 
      data[enabledBitCounter++] = i; 
     value >>= 1; 
    } 

    Array.Resize<uint>(ref data, enabledBitCounter); 
    return data; 
} 

Answer 8

आप एक छोटे से सी ++ पर गला घोंटना नहीं होगा:

void func(int i, int& n, int a[]){ 
    n = 0; 
    if (i < 0) a[n++] = 31; 
    i <<= 1; 
    if (i < 0) a[n++] = 30; 
    i <<= 1; 
    if (i < 0) a[n++] = 29; 
    i <<= 1; 

    ... 

    if (i < 0) a[n++] = 0; 
}