Chuyển các bit được che vào lsb

Question

Khi bạn and một số dữ liệu có mặt nạ, bạn nhận được một số kết quả có cùng kích thước với dữ liệu/mặt nạ. Điều tôi muốn làm là lấy các bit mặt nạ trong kết quả (trong đó có 1 mặt nạ) và dịch chuyển sang phải để chúng nằm cạnh nhau và tôi có thể thực hiện một CTZ (Count Trailing Zeroes) trên chúng.

Tôi không biết cách đặt tên thủ tục như vậy nên Google đã thất bại với tôi. Hoạt động tốt nhất là không phải là giải pháp vòng lặp, điều này phải hoạt động nhanh nhất có thể.

Và đây là một hình ảnh đáng kinh ngạc được thực hiện trong MS Paint.

Answer 1

Thao tác này được gọi là compress right. Nó được thực hiện như một phần của BMI2 làm hướng dẫn PEXT, trong bộ xử lý Intel là Haswell.

Thật không may, không hỗ trợ phần cứng là một hoạt động khá khó chịu. Tất nhiên có một giải pháp rõ ràng, chỉ cần di chuyển các bit từng người một trong một vòng lặp, đây là một trong những do hacker Delight:

unsigned compress(unsigned x, unsigned m) { 
    unsigned r, s, b; // Result, shift, mask bit. 

    r = 0; 
    s = 0; 
    do { 
     b = m & 1; 
     r = r | ((x & b) << s); 
     s = s + b; 
     x = x >> 1; 
     m = m >> 1; 
    } while (m != 0); 
    return r; 
} 

Nhưng có một cách khác, cũng do hacker Delight, mà không ít vòng lặp (số lần lặp logarit trong số bit) nhưng nhiều hơn mỗi lần lặp:

unsigned compress(unsigned x, unsigned m) { 
    unsigned mk, mp, mv, t; 
    int i; 

    x = x & m;   // Clear irrelevant bits. 
    mk = ~m << 1;  // We will count 0's to right. 

    for (i = 0; i < 5; i++) { 
     mp = mk^(mk << 1);    // Parallel prefix. 
     mp = mp^(mp << 2); 
     mp = mp^(mp << 4); 
     mp = mp^(mp << 8); 
     mp = mp^(mp << 16); 
     mv = mp & m;      // Bits to move. 
     m = m^mv | (mv >> (1 << i)); // Compress m. 
     t = x & mv; 
     x = x^t | (t >> (1 << i));  // Compress x. 
     mk = mk & ~mp; 
    } 
    return x; 
} 

ý rằng rất nhiều các giá trị chỉ có phụ thuộc vào m. Vì bạn chỉ có 512 mặt nạ khác nhau, bạn có thể precompute những người và đơn giản hóa mã để một cái gì đó như thế này (không kiểm tra)

unsigned compress(unsigned x, int maskindex) { 
    unsigned t; 
    int i; 

    x = x & masks[maskindex][0]; 

    for (i = 0; i < 5; i++) { 
     t = x & masks[maskindex][i + 1]; 
     x = x^t | (t >> (1 << i)); 
    } 
    return x; 
} 

Tất nhiên tất cả những có thể chuyển thành "không phải là một vòng lặp" bởi unrolling, thứ hai và cách thứ ba có lẽ phù hợp hơn cho điều đó. Đó là một chút gian lận tuy nhiên.

Answer 2

Bạn có thể sử dụng kỹ thuật đóng gói bằng phép nhân giống như được mô tả here. Bằng cách này bạn không cần bất kỳ vòng lặp nào.

Ví dụ với mặt nạ 0b10101001 == 0xA9 như trên và các dữ liệu 8-bit abcdefgh (với ah là 8 bit), bạn có thể sử dụng các biểu hiện dưới đây để có được 0000aceh

unsigned compress_maskA9(unsigned x) 
{ 
    const unsigned mask = 0xA9; 
    const unsigned mask1 = mask & 0xF0; 
    const unsigned mask2 = mask & 0x0F; 
    return (((x & mask1)*0x03000000 >> 28) & 0x0C) | ((x & mask2)*0x50000000 >> 30); 
} 

Trong trường hợp này có một số chồng chéo của 4 bit khi nhân nên tôi chia chúng thành 2 phần, phần đầu tiên trích bit a và c, sau đó e và h sẽ được trích xuất ở phần sau.

Bạn có thể xem kết quả của nó so với chức năng của Harold live on ideone

Nếu bạn muốn bit của kết quả đảo ngược, bạn có thể dễ dàng thay đổi con số kỳ diệu cho phù hợp.

unsigned compress_maskA9_reversed1(unsigned x) 
{ 
    // result: he00 | 00ca; 
    return (((x & 0x09)*0x88000000 >> 28) & 0x0C) | (((x & 0xA0)*0x04800000) >> 30); 
} 

hoặc bạn có thể trích xuất các 3 bit e, c và cùng một lúc, để lại h riêng do một số bit chồng chéo:

unsigned compress_maskA9_reversed(unsigned x) 
{ 
    return ((x & 0xA8)*0x12400000 >> 29) | (x & 0x01) << 3; // result: 0eca | h000 
} 

đúng đắn kiểm tra: http://ideone.com/PYUkty

Đối với một số lượng mặt nạ lớn hơn bạn có thể tính toán trước các số ma thuật tương ứng với mặt nạ đó và lưu chúng vào một mảng để sử dụng sau này.

---

Giải thích

Chúng tôi có abcdefgh & mask1 = a0c00000

 ........................a0c00000 
x 00000011000000000000000000000000 (magic1 = 0x03000000) 
__________________________________________________________________ 
    a0c00000........................ 
+ a0c00000......................... (the leading "a" bit is outside int's range so it'll be truncated 
    ↓↓ 
__________________________________________________________________  
r1 = acc............................. 

=> (r1 >> 28) & 0x0C = 0000ac00 

Tương tự abcdefgh & mask2 = 0000e00h

 ........................0000e00h 
x  01010000000000000000000000000000 (magic2 = 0x50000000) 
__________________________________________________________________ 
    0000e00h............................ 
+ 0000e00h.............................. 
     ↓↓ 
__________________________________________________________________  
    r2 = eh.............................. 

=> (r2 >> 30) = 000000eh 

Do đó

((r1 >> 28) & 0x0C) | (r2 >> 30) = 0000aceh