비트 확장/복제 알고리즘?

Question

비트 확장/복제를 수행하는 효율적인 (빠른) 알고리즘이 있습니까?

1101 0101 => 11111100 01110001 11000111 

제안되었다 무력 방법은 룩업 테이블을 생성하는 것이다

예를 들어, (3)에 의한 8 비트 값을 각 비트 (24 비트 값을 생성)를 확장. 나중에 확장 값을 가변 할 필요가 있습니다. 즉, 위의 예에서 우리는 3으로 확장하고 있지만 다른 값으로 확장해야 할 수도 있습니다. 가능하다면 피해야 할 다중 조회 테이블이 필요합니다.

Answer 1

산술 계산이 메모리 액세스보다 빠르면 조회 테이블보다 더 빨리 처리 할 수 ​​있습니다. 이것은 계산이 벡터화 (PPC AltiVec 또는 Intel SSE)되거나 프로그램의 다른 부분이 모든 비트의 캐시 메모리를 사용해야하는 경우에 가능할 수 있습니다.

은 팽창 계수 = 3 만 7 지침이 필요한 경우 :

out = (in | in << 8) & 0x0F00F; 
out = (out | out << 4) & 0x0C30C3; 
out = (out | out << 2) & 0x249249; 
out *= 7; 

다른 확장 요인> = 3 :

unsigned mask = 0x0FF; 
unsigned out = in; 
for (scale = 4; scale != 0; scale /= 2) 
{ 
    shift = scale * (N - 1); 
    mask &= ~(mask << scale); 
    mask |= mask << (scale * N); 
    out = out * ((1 << shift) + 1) & mask; 
} 
out *= (1 << N) - 1; 

out = (((in * 0x101 & 0x0F00F) * 0x11 & 0x0C30C3) * 5 & 0x249249) * 7; 

또는 다른 대안, 10 개 지침

또는 다른 대안 인 확장 요소> = 2 :

unsigned mask = 0x0FF; 
unsigned out = in; 
for (scale = 4; scale != 0; scale /= 2) 
{ 
    shift = scale * (N - 1); 
    mask &= ~(mask << scale); 
    mask |= mask << (scale * N); 
    out = (out | out << shift) & mask; 
} 
out *= (1 << N) - 1; 

shift 및 mask 값을 비트 스트림 처리 전에 계산하는 것이 더 좋습니다.

Answer 2

한 번에 하나의 입력 비트를 사용할 수 있습니다. 물론 룩업 테이블보다 느릴 수 있지만 테이블을위한 충분한 공간이없는 초소형 8 비트 마이크로 컨트롤러와 같은 작업을 수행하는 경우 ROM 풋 프린트를 최소화해야합니다.