Cách nhanh nhất để tính số lượng bit cần thiết để lưu trữ một số

Question

Tôi đang cố gắng tối ưu hóa một số quy trình đóng gói và giải nén bit. Để thực hiện việc đóng gói, tôi cần tính toán số bit cần thiết để lưu trữ các giá trị số nguyên. Đây là mã hiện tại.

if (n == -1) return 32; 
if (n == 0) return 1; 
int r = 0; 
while (n) 
{ 
    ++r; 
    n >>= 1; 
} 
return r; 

Answer 1

Bạn đang tìm cách xác định số nguyên bản ghi 2 của một số (bộ l = bit cao nhất). Trang "Bit Twiddling Hacks" của Sean Anderson có một số phương pháp khác nhau, từ các bit đếm rõ ràng trong một vòng lặp đến các phiên bản sử dụng tra cứu bảng. Lưu ý rằng hầu hết các phương pháp được chứng minh sẽ cần phải được sửa đổi một chút để làm việc với các bit int-bit nếu kiểu di động đó quan trọng đối với bạn.

• http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

Chỉ cần chắc chắn rằng bất kỳ thay đổi bạn đang sử dụng để tìm ra các thiết lập bit cao nhất cần phải làm' trên một phiên bản unsigned số từ một việc thực hiện biên dịch có thể hoặc có thể không ký hiệu mở rộng hoạt động >> trên giá trị đã ký.

Answer 2

Không có khả năng sử dụng mã vạch ngược quét bit có sẵn trên hầu hết các kiến ​​trúc hiện đại. Nó được hiển thị dưới dạng intrinsic trong Visual C++.

Có thể, mã trong câu hỏi không cần xử lý cạnh trường hợp. Tại sao bạn cần một chút để lưu trữ 0? Trong mọi trường hợp, tôi sẽ bỏ qua các cạnh của vấn đề. Can đảm có thể được thực hiện một cách hiệu quả như sau:

if (n >> 16) { r += 16; n >>= 16; } 
if (n >> 8) { r += 8; n >>= 8; } 
if (n >> 4) { r += 4; n >>= 4; } 
if (n >> 2) { r += 2; n >>= 2; } 
if (n - 1) ++r; 

Answer 3

Bạn sẽ phải kiểm tra thời gian thực hiện để tìm các chi tiết, nhưng tôi đoán là làm 4 bit tại một thời điểm, và sau đó quay trở lại một chút tại một thời gian sẽ lam no nhanh hơn. Các hoạt động nhật ký có thể sẽ chậm hơn các phép toán logic/bit.

if (n < 0) return 32; 
int r = 0; 
while (n && 0x7FFFFFF0) { 
    r+=4; 
    n >>= 4; } 
while (n) { 
    r++; 
    n >>= 1; } 
return r; 

Answer 4

Những gì bạn đang cố gắng làm là tìm bit quan trọng nhất. Một số kiến ​​trúc có một hướng dẫn đặc biệt chỉ dành cho mục đích này. Đối với những người không sử dụng phương pháp tra cứu bảng.

Tạo một bảng gồm 256 mục nhập, trong đó mỗi phần tử xác định bit trên cao nhất.

Hoặc lặp qua từng byte trong số hoặc sử dụng một vài câu lệnh if để ngắt để tìm byte không phải thứ tự cao nhất.

Tôi sẽ cho phép bạn lấy phần còn lại từ đây.

Answer 5

Thực hiện tìm kiếm nhị phân thay vì tìm kiếm tuyến tính.

if ((n >> 16) != 0) 
{ 
    r += 16; 
    n >>= 16; 
} 

if ((n >> 8) != 0) 
{ 
    r += 8; 
    n >>= 8;   
} 

if ((n >> 4) != 0) 
{ 
    r += 4; 
    n >>= 4;   
} 

// etc. 

Nếu phần cứng của bạn có bit-scan-reverse, cách tiếp cận nhanh hơn sẽ là viết thường trình của bạn bằng ngôn ngữ lắp ráp. Để giữ cho di động mã của bạn, bạn có thể làm

#ifdef ARCHITECTURE_WITH_BSR 
    asm // ... 
#else 
    // Use the approach shown above 
#endif 

Answer 6

number_of_bits = log2(integer_number) 

làm tròn đến số nguyên lớn hơn.