Thuật toán để mở rộng/sao chép bit?

Question

Có thuật toán hiệu quả (nhanh) nào sẽ thực hiện mở rộng/sao chép bit không?

Ví dụ, mở rộng mỗi bit trong một giá trị 8 bit bằng 3 (tạo ra một giá trị 24bit):

1101 0101 => 11111100 01110001 11000111 

Phương pháp brute force mà đã được đề xuất là để tạo ra một bảng tra cứu. Trong tương lai, giá trị mở rộng có thể cần phải thay đổi. Tức là, trong ví dụ trên chúng ta đang mở rộng 3 nhưng có thể cần phải mở rộng bằng một số giá trị khác. Điều này sẽ yêu cầu nhiều bảng tra cứu mà tôi muốn tránh nếu có thể.

Answer 1

Có một cơ hội để làm cho nó nhanh hơn so với bảng tra cứu nếu tính toán số học là vì lý do nào đó nhanh hơn truy cập bộ nhớ. Điều này có thể xảy ra nếu các phép tính được vector hóa (PPC AltiVec hoặc Intel SSE) và/hoặc nếu các phần khác của chương trình cần sử dụng từng bit bộ nhớ cache.

Nếu hệ số mở rộng = 3, chỉ có 7 hướng dẫn là cần thiết:

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

Hoặc thay thế khác, với 10 hướng dẫn:

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

Đối với yếu tố mở rộng khác> = 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; 

Hoặc giải pháp thay thế khác, cho các yếu tố mở rộng> = 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 và mask giá trị tốt hơn để được tính toán trước khi xử lý luồng bit.

Answer 2

Bạn có thể thực hiện một bit đầu vào tại thời điểm. Tất nhiên, nó sẽ chậm hơn một bảng tra cứu, nhưng nếu bạn đang làm một cái gì đó giống như viết cho một vi điều khiển nhỏ 8 bit mà không có đủ chỗ cho một bảng, nó sẽ có dấu chân ROM nhỏ nhất có thể.