قم بخلط بتات N التالية N (على سبيل المثال كل 4 بايت) 00001111 -> 01010101

Question

كما يخبر عنوان هذا السؤال أنني أريد أن أعرف أفضل طريقة لخلط كتل البتات داخل عدد صحيح (خاصة 64 بت غير موقعة)

على سبيل المثال ، لدي عدد صحيح 8bit ، حيث تكون البتات 0000 1111 Mix 4Bits بمقدار 4 بت = 0101 0101

مثال 2: 0010 0110
0 1 1 0 اليمين 0.0.1.0 اليسار = 00011100 مزيج 4Bits بمقدار 4 بت = 0001 1100 بسيط هو ،. الأماكن المملوءة بأجزاء من الكتلة اليمنى

ما أفعله بشكل صحيح:

uint64_t mix32(uint64_t v) {
    uint64_t ret=0;
    int x=0;
    for(int i=0; i<32; i++) {
        setbit(ret, x, getbit(v, i));
        x++;
        setbit(ret, x, getbit(v, i+32));
        x++;
    }

    return ret;
}

عندما يكون setbit هو ماكرو يقوم بتعيين أو مسح البت في موضع معين. ما أحتاجه بالضبطامزج كل 32 بت مع مزج 32bits التالي كل 16 بت مع مزج 16 بتات كل 16 بت مع مزج بعد 16 بت التالي كل 8 بتات مع 8bits التاليةإلخ ... آمل أن أتمكن من القيام بالراحة إذا كان هناك مثال على عمليات البت هذه. لقد نظرت إلى Google كثيرًا ، لكن انتهى الأمر بالدروس التعليمية التي لا تظهر مثل هذا السيناريو.

البقاء جيدا.

Answer 1

تم العثور على حل من Bit Tweeding Hacks - على الرغم من أنه لم يكن جيدًا قضاء وقت كبير في هذه العملية الصغيرة. أنا متأكد من أنه يجب أن يكون هناك العديد من الطرق الجيدة للقيام بذلك ، لكنني كنت بحاجة إلى حل يمكن أن يبقيني التركيز على بحثي ، أنا متأكد من أنها أسوأ طريقة.

uint64_t mix32(uint64_t v, bool right_even=true) {
    unsigned uint32_t x;   // Interleave bits of x and y, so that all of the
    unsigned uint32_t y;   // bits of x are in the even positions and y in the odd;
    unsigned uint64_t z = 0; // z gets the resulting Morton Number.

    if(right_even)
        v = swap32(v); //swap 32bit blocks

    char *n = (char*)malloc(sizeof(v));
    memcpy(n, &v, sizeof(v));
    memcpy(&y, n, sizeof(y));
    memcpy(&x, n+sizeof(x), sizeof(x));

    for (int i = 0; i < sizeof(x) * 8; i++) // unroll for more speed...
       z |= (x & 1ULL << i) << i | (y & 1ULL << i) << (i + 1);

    return z;
}

البقاء جيدا.

Answer 2

نرى بت twiddling الاختراقات في ال بتات متداخلة قسم لبعض الحلول.

Answer 3

ما أود فعله هو أن يكون لديه جدول عناصر من 16 عنصرًا يحمل نتيجة لتوسيع كل حلقة لعملية التعدد. ثم مجرد تحريك يسار 1 حسب الحاجة و bitwise أو النتائج معا.

Answer 4

unsigned __int64 mix32(unsigned __int64 v, bool right_even=true) {
    unsigned __int64 z = 0; 

    if(right_even)
        v = swap32(v);

    unsigned __int32 x = (v&0xffffffffUL);
    unsigned __int32 y = (v&0xffffffffUL)>>32;

    for (int i = 0; i < sizeof(x) * 8; i++) 
       z |= (x & 1ULL << i) << i | (y & 1ULL << i) << (i + 1);

    return z;
}