마스크 된 비트를 lsb로 이동

Question

and 마스크가있는 일부 데이터는 데이터/마스크와 크기가 같은 결과를 얻습니다. 내가하고 싶은 것은 (마스크에 1이 있던) 마스크 된 비트를 가져 와서 오른쪽으로 이동시켜 서로 옆에 놓고 CTZ (Count Trailing Zeroes)를 수행 할 수 있습니다. 그들.

Google이 나를 실패 시키므로 그러한 프로 시저의 이름을 지정하는 방법을 알지 못했습니다. 작업은 루프가 아니어야합니다 (가능한 한 빠른 작업이어야 함) 솔루션입니다.

그리고 여기 MS 그림판에서 만든 놀라운 이미지입니다.

Answer 1

이 작업을 compress right이라고합니다. 이것은 Haswell 현재 Intel 프로세서에서 의 일부로 PEXT 명령어로 구현됩니다.

하드웨어 지원이 없으면 불편을 겪습니다. 물론 명백한 해결책은 단지 루프에 의해 비트를 하나씩 이동이 여기에 해커 기쁨에 의해 주어진 하나입니다

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; 
} 

는하지만도 않습니다 해커 기쁨에 의해 주어진 다른 방법이있다 이하 루핑 (비트 수의 반복 대수 수) 반복하지만 당 : 값이 많이 m에만 존재 의존한다는

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; 
} 

통지. 당신은 단지 512 개 다른 마스크를 가지고 있기 때문에, 당신은 사람들을 미리 계산하고이 모든이, 두 번째를 줄이기로 "하지 루프"로 설정할 수 있습니다 물론

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; 
} 

이 같은 (테스트하지)에 코드를 단순화 할 수있다 아마도 세 번째 방법이 더 적합 할 것입니다. 그러나 그것은 약간의 속임수입니다.

Answer 2

here과 비슷한 pack-by-multiplication 기술을 사용할 수 있습니다. 이렇게하면 루프가 필요 없습니다. 상기 8 비트의 데이터 abcdefgh 일부 오버랩이있는 이러한 경우 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); 
} 

를 얻기 위해 다음 식을 사용하여 (아 8 비트)와 같은 마스크 0b10101001 == 0xA9와 예

곱해질 때의 4 비트를 2 부분으로 나누었습니다. 첫 번째 부분은 비트 a와 c를 추출한 다음 e와 h는 후자 부분에서 추출됩니다.

할 수 있습니다 참조는 결과의 비트가 쉽게 따라 마법의 수를 변경할 수 있습니다 반전하려면 해롤드의 기능 live on ideone

과 비교하여 그 결과.

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

아니면 인해 일부 중복 비트로 별도로 시간을두고, 동시에 3 비트 E, C 및 추출 할 수

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

정확성 확인하십시오 들어 http://ideone.com/PYUkty

더 많은 수의 마스크는 해당 마스크에 해당하는 매직 번호를 사전 계산하여 나중에 사용할 수 있도록 배열에 저장할 수 있습니다.

---

설명 우리는 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 

마찬가지로이

abcdefgh & mask2 = 0000e00h

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

=> (r2 >> 30) = 000000eh 

따라서

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