오른쪽 비트 알고리즘 확장

Question

원래이 게시물은 역 양과 염소 작업을 요청했지만이 작업은 내가 필요로하는 것보다 많다는 것을 깨달았으므로 제목을 편집했습니다. expand-right algorithm 만 필요하기 때문에 더 간단합니다. 아래에서 설명한 예는 여전히 관련이 있습니다.

원래 포스트 : 나는, 더 나은 어느 역 양 - 및 - 염소 작업을하거나 어떻게 확장 오른쪽 플립을 알아 내려고 노력하고있어

.

가 Hacker's Delight에 따르면, 양 앤 염소 동작에 의해 표현 될 수있다 :

this site 따르면

SAG(x, m) = compress_left(x, m) | compress(x, ~m) 

, 반전에 의해 발견 될 수있다 : 그러나

INV_SAG(x, m, sw) = expand_left(x, ~m, sw) | expand_right(x, m, sw) 

, I '는 수 expand_left 및 expand_right 함수에 대한 코드를 찾으십시오. 그것들은 물론 compress의 역함수이지만 compress는 그 자체로 이해하기가 어렵습니다.

예 :

더, 내가 무엇을 찾고 설명과 같은 8 비트의 집합 고려해야 할

0000abcd 

변수를 A, B, C, D는 두 사람이 될 수 있습니다 또는 0입니다. 또한, 비트를 재배치하는 마스크가 있습니다.

0ab00c0d 

이는 역 양 및 염소 - 연산으로 수행 될 수있다 : 마스크 01100101라면 다음 그래서 예를 들어, 생성 된 비트가 재배치 될 것이다. 그러나 위에서 언급 한 사이트의 this section에 따르면 확장 - 오른쪽 - 뒤집기라고하는 더 효율적인 방법이 있습니다. 그의 사이트를 보면 어떻게 할 수 있는지 알 수 없었습니다.

Answer 1

Hacker 's Delight의 expand_right은 단지 expand으로 표시되지만 right 버전입니다.

unsigned expand(unsigned x, unsigned m) { 
    unsigned m0, mk, mp, mv, t; 
    unsigned array[5]; 
    int i; 
    m0 = m;  // Save original mask. 
    mk = ~m << 1; // We will count 0's to right. 
    for (i = 0; i < 5; i++) { 
     mp = mk^(mk << 1);    // Parallel suffix. 
     mp = mp^(mp << 2); 
     mp = mp^(mp << 4); 
     mp = mp^(mp << 8); 
     mp = mp^(mp << 16); 
     mv = mp & m;      // Bits to move. 
     array[i] = mv; 
     m = (m^mv) | (mv >> (1 << i)); // Compress m. 
     mk = mk & ~mp; 
    } 
    for (i = 4; i >= 0; i--) { 
     mv = array[i]; 
     t = x << (1 << i); 
     x = (x & ~mv) | (t & mv); 
    } 
    return x & m0;  // Clear out extraneous bits. 
} 

당신은 left 버전을 만들기 위해 expand_left(x, m) == expand_right(x >> (32 - popcnt(m)), m)을 사용할 수 있지만 아마도 가장 좋은 방법이 아니다.