पता लगाएँ कि कितने द्विआधारी अंकों एक विशेष पूर्णांक

Question

संभव डुप्लिकेट है:
Compute fast log base 2 ceiling

क्या कितने द्विआधारी अंकों एक विशेष पूर्णांक है जब यह पता लगाने के लिए सबसे तेजी से संभव तरीका है सी/सी ++ में दशमलव से बाइनरी में परिवर्तित किया गया है?

पूर्व। 47 ₍₁₀₎ = 101111 ₍₂₎

तो 47 6 अंक बाइनरी में प्रतिनिधित्व किया है।

Answer 1

my favorite collection of bit twiddling hacks पर प्रस्तुत किया गया सबसे तेज़ समाधान Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup है। किसी संख्या में उच्चतम सेट बिट खोजने के लिए इसे 13 निर्देशों की आवश्यकता है।

uint32_t v; // find the log base 2 of 32-bit v 
int r;  // result goes here 

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

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2; 
v |= v >> 4; 
v |= v >> 8; 
v |= v >> 16; 

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27]; 

Answer 2

लघुगणक का उपयोग करने का प्रयास करें: आवश्यक बिट्स होगा पूर्णांक कम से कम 1 है

ceil(log2(n)) 

Answer 3

एक आधार -2 लघुगणक का प्रयास करें

floor(log2(x)) + 1 

Answer 4

,:

ceil(log2(x)) 

Answer 5

गणित कार्यों कॉल करने के लिए की जरूरत के बिना ऐसा करने का एक त्वरित मजेदार तरीके के लिए, यह एक बाहर की जाँच:

for (digits = 0; val > 0; val >>= 1) 
     digits++; 

एक बोनस के रूप में, यह नीचे एक स्मृति लोड करने के लिए और में 2 रजिस्टरों खाना बनाना चाहिए अतिरिक्त whiz-bang के लिए उपयोग करें।

Answer 6

यदि आप प्रदर्शन के मामले में "सबसे तेज़" तरीके की तलाश में हैं, तो आपको प्लेटफ़ॉर्म-विशिष्ट तरीकों का सहारा लेना होगा।

कुछ आर्किटेक्चर में वास्तव में एक निर्देश होता है जो ऐसा करता है।

x86 पर, आपके पास bsr निर्देश है।

MSVC में, यह पहुँचा जा सकता है के रूप में:

inline int bitlength(unsigned long x){ 
    if (x == 0) 
     return 0; 

    unsigned long index; 
    _BitScanReverse(&index,x); 
    return (int)(index + 1); 
} 

जीसीसी__builtin_clz() intrinsic है - जो कुछ ऐसा ही।

Answer 7

परंपरागत तरीके से

int count = 32; 
for(int i = 1 << 31; i != 0; i >>= 1, count--) 
    if((number & i) != 0) return count; 

आप अनुकूलन के साथ और अधिक कल्पना कर सकते हैं।

EDIT 2 बिट स्कैन रिवर्स ऑपोड के उपयोग के बिना मैं सबसे तेज़ कोड सोच सकता हूं। आप एक बड़ी (256 प्रविष्टि) LUT का उपयोग कर सकते हैं और अंतिम IF कथन को हटा सकते हैं। मेरे परीक्षण में यह बार-बार OR-SHIFT से तेज़ था, फिर LUT विधि किसी अन्य पोस्ट में वर्णित है।

int[] Log2_LUT = new int[16]{0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4}; 
int Log2 (number) { 
int count = 0; 
if((number & 0xFFFF0000) != 0) { 
    number >>= 16; 
    count += 16; 
} 
if((number & 0x0000FF00) != 0) { 
    number >>= 8; 
    count += 8 
} 
if((number & 0x000000F0) != 0) { 
    number >>= 4; 
    count += 4; 
} 
return count + Log2_LUT[number]; 
} 

या अगर अपने 86 या x86-64 बिट संरचना आप बीएसआर (बिट स्कैन रिवर्स) opcode का उपयोग कर सकते है। आप C++ आंतरिक पा सकते हैं के लिए यह http://msdn.microsoft.com/en-us/library/fbxyd7zd%28v=vs.80%29.aspx

इसके अलावा, आप सवाल यह एक What is the fastest way to calculate the number of bits needed to store a number

संपादित के समान है क्यों log2 जवाब इष्टतम नहीं हैं ... जबकि गणितीय सही, जटिल चल बिन्दु आपरेशनों (साइन, कोसाइन, तन, लॉग) आधुनिक कंप्यूटर पर सबसे धीमे प्रदर्शन कर रहे हैं। यह एक फ्लोट में पूर्णांक को परिवर्तित करने और इसे छत/मंजिल के साथ जोड़कर मिश्रित किया जाता है।

Answer 8

एक तरीका यह ...

unsigned int count_bits(unsigned int n) 
{ 
    unsigned int count = 0; 

    if (n <= 1) 
     return 1; 

    do 
     count++; 
    while(n >>= 1); 

    return count; 
} 

Answer 9

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

CHAR_BIT * sizeof x - __builtin_clz(x)