Có thể xác định số lượng chuyển tiếp bitwise trong một số nguyên 8 bit không?

Question

Tôi dường như không tìm thấy chút phép thuật nào về điều này, vì vậy tôi hy vọng một ai đó ở đây có thể làm sáng tỏ một chút nếu điều này thậm chí có thể xảy ra.

Tôi đang cố gắng tìm số lượng chuyển tiếp bit theo số nguyên 8 bit (số nguyên thực sự là số nguyên 32 bit, nhưng tôi chỉ sử dụng 8 bit đầu tiên) để xác định xem 8 bit có đồng nhất hay không (2 hoặc ít chuyển tiếp hơn).

Ví dụ:

00100000 - two transitions - uniform 
00100001 - three transitions - not uniform 
10101010 - seven transitions - not uniform 
00000000 - no transitions - uniform 

Có cách nào nhanh hơn để tìm ra số hiệu ứng chuyển tiếp khác hơn là lặp qua từng bit (lặp qua từng chút hiện đang là giải pháp duy nhất tôi có thể đưa ra)?

Answer 1

Bạn có thể x-hoặc giá trị với giá trị được dịch chuyển một bit và sau đó đếm số lượng 1 trong kết quả.

unsigned v = (x^(x>>1)) & 0x7F; 
unsigned count = 0; 
while (v) { 
    count++; 
    v &= (v - 1); 
} 

Lưu ý rằng một byte chỉ có thể có 256 cấu hình, vì vậy việc tính toán có thể được thực hiện một lần và đặt trong một bảng rất nhỏ 256 byte.

Nếu bạn chỉ muốn biết nếu có 2 hoặc ít thay đổi vòng lặp có thể được trải ra:

unsigned v = (x^(x >> 1)) & 0x7F; 
v &= v - 1; 
v &= v - 1; 
uniform = (v == 0); 

Lưu ý rằng tính toán này là độc lập vào độ lớn là số lượng và bạn có thể sử dụng ví dụ trực tiếp một Số không dấu 32 bit (điều duy nhất thay đổi là mặt nạ trở thành 0x7FFFFFFF)

Answer 2

Để biết định nghĩa thống nhất, số phải ở dạng 00011111 hoặc 11110000. Hãy xem xét cái cũ (số không theo sau là cái).

Thêm một giá trị. Nếu nó là đồng nhất, nó sẽ có chính xác một bit 1, có nghĩa là một sức mạnh của 2.

Để kiểm tra xem một giá trị có phải là công suất của hai hay không, sử dụng (x & (x - 1)) == 0. Để rút ngắn mã, chúng tôi không cần phải thêm mã vào bước trước đó. Thay vào đó, chúng tôi kiểm tra (x & (x + 1)) == 0

Áp dụng điều này cho trường hợp khác bằng cách KHÔNG nhập giá trị ban đầu và lặp lại quy trình trên.

#include <cstdio> 
bool isuniform(unsigned char x) { 
    unsigned char y = ~x; 
    return (x & (x + 1)) == 0 || (y & (y + 1)) == 0; 
} 
int main() { 
    printf("%d\n", isuniform(0)); // 00000000 
    printf("%d\n", isuniform(1)); // 00000001 
    printf("%d\n", isuniform(3)); // 00000011 
    printf("%d\n", isuniform(7)); // 00000111 
    printf("%d\n", isuniform(15)); // 00001111 
    printf("%d\n", isuniform(31)); // 00011111 
    printf("%d\n", isuniform(63)); // 00111111 
    printf("%d\n", isuniform(127)); // 01111111 
    printf("%d\n", isuniform(255)); // 11111111 
    printf("%d\n", isuniform(254)); // 11111110 
    printf("%d\n", isuniform(252)); // 11111100 
    printf("%d\n", isuniform(248)); // 11111000 
    printf("%d\n", isuniform(240)); // 11110000 
    printf("%d\n", isuniform(224)); // 11100000 
    printf("%d\n", isuniform(192)); // 11000000 
    printf("%d\n", isuniform(128)); // 10000000 
    //---------- 
    printf("%d\n", isuniform(2)); 
    printf("%d\n", isuniform(4)); 
    printf("%d\n", isuniform(50)); 
    printf("%d\n", isuniform(123)); 
    printf("%d\n", isuniform(129)); 
    printf("%d\n", isuniform(253)); 
    return 0; 
}