एक int

Question

में nth SET बिट ढूंढें केवल सबसे कम सेट बिट के बजाय, मैं n वें सबसे कम सेट बिट की स्थिति ढूंढना चाहता हूं।

उदाहरण के लिए (मैं नहींn वें बिट स्थिति पर मूल्य के बारे में बात कर रहा हूँ), का कहना है कि मेरे पास है:
0000 1101 1000 0100 1100 1000 1010 0000

और मैं 4 बिट, जिसमें सेट लगाना चाहते हैं। तब मैं इसे वापस करना चाहते हैं:
0000 0000 0000 0000 0100 0000 0000 0000

तो popcnt(v) < n, यह मतलब है कि इस समारोह 0 लौटे हैं, लेकिन इस मामले के लिए किसी भी व्यवहार मेरे लिए स्वीकार्य है।

यदि संभव हो तो मैं लूप से कुछ तेज़ी से ढूंढ रहा हूं।

Answer 1

यह पता चला है कि बिना किसी लूप के ऐसा करना संभव है। इस समस्या के (कम से कम) 8 बिट संस्करण को प्रीकंप्यूट करना सबसे तेज़ है। बेशक, ये टेबल कैश स्पेस का उपयोग करते हैं, लेकिन अभी भी लगभग सभी आधुनिक पीसी परिदृश्यों में नेट स्पीडअप होना चाहिए। इस कोड में, n = 0 रिटर्न कम से कम सेट बिट, एन = 1 सेकंड करने वाली कम से कम आदि

__popcnt साथ समाधान

वहाँ एक समाधान __popcnt आंतरिक उपयोग कर रहा है (आप __popcnt की जरूरत है, एक साधारण लूप समाधान पर बेहद तेज़ या किसी भी लाभ लाभ होने के लिए मंथन होगा। सौभाग्य से अधिकांश एसएसई 4 + युग प्रोसेसर इसका समर्थन करते हैं)।

// lookup table for sub-problem: 8-bit v 
byte PRECOMP[256][8] = { .... } // PRECOMP[v][n] for v < 256 and n < 8 

ulong nthSetBit(ulong v, ulong n) { 
    ulong p = __popcnt(v & 0xFFFF); 
    ulong shift = 0; 
    if (p <= n) { 
     v >>= 16; 
     shift += 16; 
     n -= p; 
    } 
    p = __popcnt(v & 0xFF); 
    if (p <= n) { 
     shift += 8; 
     v >>= 8; 
     n -= p; 
    } 

    if (n >= 8) return 0; // optional safety, in case n > # of set bits 
    return PRECOMP[v & 0xFF][n] << shift; 
} 

यह दर्शाता है कि कैसे विभाजित और जीत दृष्टिकोण काम करता है।

जनरल समाधान

वहाँ भी है __popcnt बिना "सामान्य" architectures- के लिए एक समाधान। यह 8-बिट भाग में प्रसंस्करण करके किया जा सकता है। आप एक और लुकअप तालिका है कि आप एक बाइट की popcnt बताता है की जरूरत है:

byte PRECOMP[256][8] = { .... } // PRECOMP[v][n] for v<256 and n < 8 
byte POPCNT[256] = { ... } // POPCNT[v] is the number of set bits in v. (v < 256) 

ulong nthSetBit(ulong v, ulong n) { 
    ulong p = POPCNT[v & 0xFF]; 
    ulong shift = 0; 
    if (p <= n) { 
     n -= p; 
     v >>= 8; 
     shift += 8; 
     p = POPCNT[v & 0xFF]; 
     if (p <= n) { 
      n -= p; 
      shift += 8; 
      v >>= 8; 
      p = POPCNT[v & 0xFF]; 
      if (p <= n) { 
       n -= p; 
       shift += 8; 
       v >>= 8; 
      } 
     } 
    } 

    if (n >= 8) return 0; // optional safety, in case n > # of set bits 
    return PRECOMP[v & 0xFF][n] << shift; 
} 

यह, ज़ाहिर है, एक पाश के साथ किया जा सकता है, लेकिन unrolled प्रपत्र तेजी से होता है और लूप के असामान्य रूप में यह होगा संभावना नहीं है कि संकलक स्वचालित रूप से आपके लिए इसे अनलॉक कर सकता है।

Answer 2

मैं एक लूप के बिना एक विधि नहीं देख सकता, क्या दिमाग में दिमाग होगा;

int set = 0; 
int pos = 0; 
while(set < n) { 
    if((bits & 0x01) == 1) set++; 
    bits = bits >> 1; 
    pos++; 
} 

जिसके बाद, स्थिति वें सबसे कम मान सेट बिट की स्थिति बनाए रखने के हैं।

एकमात्र अन्य चीज जिसे मैं सोच सकता हूं वह एक विभाजन और विजय दृष्टिकोण होगा, जो ओ (एन) के बजाय ओ (लॉग (एन)) उत्पन्न कर सकता है ... लेकिन शायद नहीं।

संपादित करें: आपने कहा कोई व्यवहार, इसलिए गैर-समाप्ति ठीक है, है ना? : पी

Answer 3

Bit Twiddling Hacks

संपादित करें: वहाँ नहीं इस समस्या का एक विशिष्ट जवाब है, लेकिन वहाँ सब buildign इसे हल करने के लिए आवश्यक ब्लॉक हैं।

Answer 4

v-1 शून्य है जहां v में कम से कम महत्वपूर्ण "एक" बिट है, जबकि सभी महत्वपूर्ण बिट्स समान हैं। यह निम्न समारोह की ओर जाता है:

int ffsn(unsigned int v, int n) { 
    for (int i=0; i<n-1; i++) { 
     v &= v-1; // remove the least significant bit 
    } 
    return v & ~(v-1); // extract the least significant bit 
} 

Answer 5

def bitN (l: Long, i: Int) : Long = { 
    def bitI (l: Long, i: Int) : Long = 
    if (i == 0) 1L else 
    2 * { 
     if (l % 2 == 0) bitI (l/2, i) else bitI (l /2, i-1) 
    } 
    bitI (l, i)/2 
} 

एक पुनरावर्ती विधि (स्केला में)। विघटन I, स्थिति, यदि एक modulo2 है 1. लौटने के दौरान, गुणा करके 2. गुणा को अंतिम ऑपरेशन के रूप में आविष्कार किया जाता है, यह पूंछ रिकर्सिव नहीं है, लेकिन चूंकि लंबे समय से ज्ञात आकार पहले से ही हैं, अधिकतम ढेर भी नहीं है बड़े।

scala> n.toBinaryString.replaceAll ("(.{8})", "$1 ") 
res117: java.lang.String = 10110011 11101110 01011110 01111110 00111101 11100101 11101011 011000 

scala> bitN (n, 40) .toBinaryString.replaceAll ("(.{8})", "$1 ") 
res118: java.lang.String = 10000000 00000000 00000000 00000000 00000000 00000000 00000000 000000 

Answer 6

आजकल यह BMI2 instruction set से PDEP के साथ बहुत आसान है। यहाँ कुछ उदाहरण के साथ एक 64-बिट संस्करण है: जुक्का Suomela है, जो एक मशीन विशिष्ट अनुदेश जरूरी है कि उपलब्ध नहीं हो सकता है का उपयोग करता है के द्वारा दिए गए जवाब पर

#include <cassert> 
#include <cstdint> 
#include <x86intrin.h> 

inline uint64_t nthset(uint64_t x, unsigned n) { 
    return _pdep_u64(1ULL << n, x); 
} 

int main() { 
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 0) == 
        0b0000'0000'0000'0000'0000'0000'0010'0000); 
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 1) == 
        0b0000'0000'0000'0000'0000'0000'1000'0000); 
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 3) == 
        0b0000'0000'0000'0000'0100'0000'0000'0000); 
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 9) == 
        0b0000'1000'0000'0000'0000'0000'0000'0000); 
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 10) == 
        0b0000'0000'0000'0000'0000'0000'0000'0000); 
} 

Answer 7

बिल्डिंग, यह भी संभव है एक समारोह लिखने के लिए कि किसी भी मशीन निर्भरता के बिना _pdep_u64 जैसा बिल्कुल वही काम करता है। इसे तर्कों में से एक में सेट बिट्स पर लूप होना चाहिए, लेकिन अभी भी सी ++ 11 के लिए कॉन्स्टेक्स फ़ंक्शन के रूप में वर्णित किया जा सकता है।

constexpr inline uint64_t deposit_bits(uint64_t x, uint64_t mask, uint64_t b, uint64_t res) { 
    return mask != 0 ? deposit_bits(x, mask & (mask - 1), b << 1, ((x & b) ? (res | (mask & (-mask))) : res)) : res; 
} 

constexpr inline uint64_t nthset(uint64_t x, unsigned n) { 
    return deposit_bits(1ULL << n, x, 1, 0); 
}