Làm thế nào để tách rời các bit (UnMortonizing?)

Question

Cách hiệu quả nhất để loại bỏ các bit xen kẽ từ một int 32 bit là gì? Đối với trường hợp cụ thể này, tôi chỉ quan tâm đến các bit lẻ, mặc dù tôi chắc chắn nó đơn giản để khái quát hóa bất kỳ giải pháp nào cho cả hai bộ. Ví dụ, tôi muốn chuyển đổi 0b01000101 thành 0b1011. Cách nhanh nhất là gì?

EDIT:

Trong ứng dụng này, tôi có thể đảm bảo rằng các bit đều là 0. Tôi có thể tận dụng lợi thế của thực tế đó để cải thiện tốc độ hoặc giảm không gian?

Answer 1

Cho rằng bạn biết rằng tất cả các bit khác là 0 trong ứng dụng của bạn, bạn có thể làm điều đó như thế này:

x = (x | (x >> 1)) & 0x33333333; 
x = (x | (x >> 2)) & 0x0f0f0f0f; 
x = (x | (x >> 4)) & 0x00ff00ff; 
x = (x | (x >> 8)) & 0x0000ffff; 

Bước đầu tiên trông như thế này:

0a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p x 
| 00a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0 x >> 1 
    -------------------------------- 
= 0aabbccddeeffgghhiijjkkllmmnnoop x | (x >> 1) 
& 00110011001100110011001100110011 0x33333333 
    -------------------------------- 
= 00ab00cd00ef00gh00ij00kl00mn00op (x | (x >> 1)) & 0x33333333 

Sau đó, bước thứ hai hoạt động với hai bit cùng một lúc, v.v.

Answer 2

Xét về tốc độ, bảng tra cứu rộng 16 bit với 2^32 mục sẽ khó đánh bại! Nhưng nếu bạn không có nhiều bộ nhớ để rảnh, bốn tra cứu trong một bảng 256-entry, cộng với một vài ca và AND để ghép chúng lại với nhau, có thể là một lựa chọn tốt hơn. Hoặc có lẽ điểm ngọt ở đâu đó ở giữa ... nó phụ thuộc vào tài nguyên bạn có sẵn và cách chi phí khởi tạo bảng tra cứu sẽ được phân bổ theo số lần tra cứu bạn cần thực hiện.

Answer 3

Tôi không chắc chắn như thế nào nhanh nó sẽ được, nhưng bạn có thể làm điều gì đó như

int a = 0b01000101; 
int b = 0; 
int i = 0; 
while (a > 0) { 
    b |= (a & 1) << i; 
    a >>= 2; 
} 

Trong đó sẽ kéo tất cả các bit lẻ tắt của a và đặt chúng trên b.