Tìm tất cả các giá trị 2 bit khớp với một mẫu nhị phân khác rồi tổng hợp chúng

Question

Giá trị đầu tiên:

Tôi có một giá trị nhị phân thực sự là một chuỗi giá trị 2 bit nhỏ gọn. (Tức là, mỗi 2 bit trong giá trị nhị phân đại diện cho 0, 1, 2, hoặc 3.) Vì vậy, ví dụ, 0, 3, 1, 2 trở thành 00110110. Trong chuỗi nhị phân này, tất cả những gì tôi quan tâm là số 3 (hoặc luân phiên, tôi có thể lật các bit và chỉ quan tâm đến số 0, nếu điều đó làm cho câu trả lời của bạn dễ dàng hơn). Tất cả các số khác không liên quan (vì lý do chúng ta sẽ đi vào trong một chút).

Giá trị thứ hai:

Tôi có một giá trị nhị phân thứ hai cũng là một loạt đầm giá trị 2-bit đại diện theo cùng một cách. Nó có chiều dài giống hệt với Giá trị đầu tiên.

Math:

Tôi muốn tổng các số 2-bit trong giá trị thứ hai có vị trí giống như một 3 từ giá trị đầu tiên. Nói cách khác, nếu tôi có:

First: 11000011 
Second: 01111101 

Sau đó, câu trả lời của tôi sẽ là "2" (tôi đã thêm số đầu tiên và số cuối cùng từ "thứ hai" với nhau, bởi vì đó là những những người duy nhất có một "11 "trong Giá trị Đầu tiên khớp với chúng.)

Tôi muốn thực hiện việc này trong vài chu kỳ đồng hồ nhất có thể (trên GPU hoặc trên kiến ​​trúc x86). Tuy nhiên, tôi thường tìm kiếm một thuật toán, không phải là một giải pháp lắp ráp. Có cách nào nhanh hơn che giấu hai bit tại một thời điểm từ mỗi số và chạy một số vòng?

Answer 1

Chắc chắn.

// the two numbers 
unsigned int a; 
unsigned int b; 

Bây giờ, hãy tạo mặt nạ từ mặt nạ chứa bit '1' ở vị trí lẻ chỉ khi có '11' kết thúc ở cùng một vị trí.

unsigned int mask = a & (a >> 1) & 0x55555555; 

Mở rộng nó để có được những mẫu '11' trở lại:

mask = mask | (mask << 1); 

Vì vậy, bây giờ nếu một là 1101100011, mặt nạ là 1100000011.

Sau đó, mặt nạ b với mặt nạ:

b = b & mask; 

Sau đó, bạn có thể thực hiện việc thêm các số (được che giấu) từ b song song:

b = (b & 0x33333333) + ((b & 0xcccccccc) >> 2); 
b = (b & 0x0f0f0f0f) + ((b & 0xf0f0f0f0) >> 4); 
b = (b & 0x00ff00ff) + ((b & 0xff00ff00) >> 8); 
b = (b & 0x0000ffff) + ((b & 0xffff0000) >> 16); 

Đối với số 32 bit, tổng bây giờ ở các bit thấp nhất của b. Đây là một mẫu thường được biết đến để bổ sung song song các trường bit. Đối với số lớn hơn 32 bit, bạn sẽ thêm một vòng nữa cho số 64 bit và hai vòng cho số 128 bit.