Cách nhanh nhất để có được chữ số thập phân cao nhất của một số nguyên là gì?

Question

cách nhanh nhất để thực hiện

template <typename T> 
unsigned highest_decimal_digit(T x); 

(trả về ví dụ 3 cho 356.431, 7 cho 71 và 9 trong 9) là gì?

Điều tốt nhất tôi có thể nghĩ đến là:

• constexpr-tính "kích thước trung" sức mạnh của 10 mà phù hợp với T.
• thực hiện tìm kiếm nhị phân (trong quyền hạn của 10, có thể sử dụng bảng tra cứu được cấu thành bằng constexpr) để tìm p, công suất cao nhất trong số 10 thấp hơn x.
• trả lại x chia cho p

... nhưng có thể có cách tiếp cận khác.

Ghi chú:

• tôi bày tỏ câu hỏi và cách tiếp cận của tôi trong C++ 14ish điều khoản, và một giải pháp trong mã sẽ được tốt đẹp, nhưng một giải pháp trừu tượng (hoặc thậm chí là một giải pháp trong lắp ráp x86_64) sẽ ổn thôi. Tôi muốn một cái gì đó mà sẽ làm việc cho tất cả các loại số nguyên (unsigned), mặc dù.
• Bạn có thể bỏ qua các loại tích phân đã ký.
• Tôi không chỉ định "nhanh" là gì, nhưng vui lòng nhận thức về phần cứng.

Answer 1

Tùy chọn xảy ra với tôi;

Lực lượng vũ phu: giữ nguyên chia cho 10 cho đến khi bạn đạt được 0; cho bạn biết thứ tự của số bạn đang xem (ví dụ 860 có 3 ca (86, 8, 0) nên đó là 10^3) sau đó trả lại n/(10^order)

Tìm kiếm nhị phân: như bạn nói, tìm kiếm trên quyền hạn của 10, nhưng nó đòi hỏi các biến bổ sung và các bài tập và mối quan tâm sẽ là, liệu có thêm thông tin theo dõi trả tiền cho chính nó trên các loại số bạn quan tâm? Ví dụ, nếu hầu hết các số của bạn là nhỏ, lực lượng vũ phu chỉ có thể nhanh hơn.

Tối ưu hóa bithift: đếm số lần bạn cần làm x >> 1 cho đến khi bạn đạt đến 0; điều này đặt phạm vi cho tìm kiếm của bạn. Ví dụ: 94 mất 7 ca để xóa số. Vì vậy, nó là < 128. Vì vậy, bắt đầu tìm kiếm brute-force tại 10^3. Bạn sẽ cần tra cứu bit => order.

Answer 2

Chip x86 mới hơn hỗ trợ lệnh lzcnt cho bạn biết số bit rõ ràng khi bắt đầu số nguyên. Bạn có thể truy cập nó bằng cách sử chức năng biên dịch tích hợp như sau (từ GCC):

unsigned short __builtin_ia32_lzcnt_16(unsigned short); 
unsigned int __builtin_ia32_lzcnt_u32(unsigned int); 
unsigned long long __builtin_ia32_lzcnt_u64 (unsigned long long); 

Bạn có thể kết hợp điều này với một bảng tra cứu 640 giá trị chỉ ra các giới hạn thấp hơn và trên các số nguyên bắt đầu với mỗi chữ số từ 0-9 bắt đầu với số bit rõ ràng tương ứng. Trong thực tế, bạn có thể tiết kiệm không gian bằng cách dịch chuyển đúng giá trị lzcnt 3 vị trí; sự tương ứng với các chữ số thập phân đầu tiên sẽ vẫn là duy nhất.

Answer 3

Với lệnh lzcnt, bạn có thể tạo bảng chia cho mỗi số bit không có hàng đầu. Ví dụ, đối với số lượng 64 bit unsigned:

lz | range | div 
---+---------+---- 
64 | 0  | 1 
63 | 1  | 1 
62 | 2-3 | 1 
61 | 4-7 | 1 
60 | 8-15 | 1 
59 | 16-31 | 10 
58 | 32-63 | 10 
57 | 64-127 | 10 
56 | 128-255 | 100 
... 
0 | 9223372036854775808-18446744073709551615 | 1000000000000000000 

Sau đó, việc tính toán trở thành:

leading_zero_bits = lzcnt(x); 
leading_digit = x/divisor_table[leading_zero_bits]; 
if (leading_digit >= 10) leading_digit = 1; 

Kết quả của việc phân chia sẽ luôn là dưới 20, vì vậy chỉ một kiểm tra đơn giản là cần thiết cho thương số giữa 10 và 19. Phép chia theo hằng số cũng có thể được tối ưu hóa.

Answer 4

Các lựa chọn tốt nhất có vẻ là kết hợp cách tiếp cận CLZ và chia cho điện precalculated 10. Vì vậy, trong giả:

powers10=[1,1,1,1,10,10,10,10,100,100...]; // contains powers of 10 map to CLZ values 
int firstDigit(unsigned INT_TYPE a) { 
    if (a<10) return a; // one digit, screw it 
    int j=typesize(a)-clz(a); 
    if (j==3) return 1; // 10-16 hit this, return 1 
    int k=a/powers10[j]; 
    if (k>9) return 1; else return k; 
} 

typesize() lợi nhuận 64 cho long long, 32 cho int và 16 cho short int.