2017-12-13 159 views
5

Tôi là một chút bối rối như thế nào short function này từ C++ fmtlib hoạt động.Toán học đằng sau * 1233 >> 12 trong mã này đếm số thập phân

inline std::uint32_t digits10_clz(std::uint32_t n) { 
    std::uint32_t t = (32 - __builtin_clz(n | 1)) * 1233 >> 12; 
    return t - (n < powers_of_10_u32[t]) + 1; 
} 

Tôi hiểu logic mà bạn có thể xấp xỉ log10 sử dụng log2 (__builtin_clz) và rằng bạn cần phải điều chỉnh cho giá trị chính xác, nhưng nhân là một bí ẩn đối với tôi.

Trả lời

7

Nhớ lại the formula for changing the base of logarithmb-d

log d x = log b x/log b d

Trong trường hợp của chúng tôi, b là 2 (nhị phân), và d là 10 (thập phân). Do đó, bạn cần chia cho nhật ký 10, giống như nhân với 1/log 10, tức là 0.30102999566.

Bây giờ hãy nhớ rằng việc dịch chuyển bằng 12 là giống như chia cho 2 , là 4096. Chia 1233 cho 4096 sản lượng 0.30102539062, là một xấp xỉ khá tốt cho mẫu số trong công thức thay đổi cơ sở.

+0

Tôi có thêm câu hỏi. Thủ thuật tối ưu hóa bộ phận này thường được trình biên dịch đưa ra và không cần phải ở trong mã nguồn. Bất kỳ lý do nào có thể nó xuất hiện trong mã nguồn lần này? –

+2

@NickyC Thật khó để nói - có lẽ họ đã sao chép điều này từ [nguồn gốc của các thủ thuật bit] (https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10), và tác giả đã viết nó ở đó không tin tưởng trình biên dịch để tối ưu hóa mã của mình. Tôi sẽ thay thế sự thay đổi bằng cách phân chia mà không do dự. – dasblinkenlight

+0

@NickyC: vì nó nhanh hơn và đáng tin cậy hơn. Các tùy chọn khác để sử dụng số học dấu chấm động là chậm hơn, và không đáng tin cậy giữa các nền tảng. Trình biên dịch không làm tối ưu hóa như vậy, vì vậy điều này phải có trong mã nguồn. – geza

Các vấn đề liên quan