Cách tốt nhất để lấy các chữ số riêng lẻ từ int cho sắp xếp radix trong C/C++

Question

Cách tốt nhất để lấy các chữ số riêng lẻ từ một số int với số chữ số n để sử dụng trong thuật toán sắp xếp radix là gì? Tôi tự hỏi nếu có một cách đặc biệt tốt để làm điều đó trong C/C++, nếu không phải là giải pháp chung tốt nhất là gì?

chỉnh sửa: chỉ để làm rõ, tôi đã tìm kiếm một giải pháp khác ngoài việc chuyển đổi nó thành chuỗi và xử lý nó như một mảng chữ số.

Answer 1

Sử dụng các chữ số có kích thước 2^k. Để trích xuất các chữ số thứ n:

#define BASE (2<<k) 
#define MASK (BASE-1) 

inline unsigned get_digit(unsigned word, int n) { 
    return (word >> (n*k)) & MASK; 
} 

Sử dụng shift và mặt nạ (kích hoạt bởi cơ sở là một sức mạnh của 2) tránh được hướng dẫn nguyên-chia tốn kém.

Sau đó, chọn cơ sở tốt nhất là một câu hỏi thử nghiệm (cân bằng thời gian/không gian cho phần cứng cụ thể của bạn). Có lẽ k==3 (cơ sở 8) hoạt động tốt và giới hạn số lượng nhóm, nhưng k==4 (cơ sở 16) trông hấp dẫn hơn vì nó chia kích thước từ. Tuy nhiên, thực sự không có gì sai với một cơ sở không phân chia kích thước chữ, và bạn có thể thấy rằng base 32 hoặc base 64 hoạt động tốt hơn. Đó là một câu hỏi thử nghiệm và có thể khác nhau theo phần cứng, theo cách bộ nhớ cache hoạt động và có bao nhiêu phần tử trong mảng của bạn.

Lưu ý cuối cùng: nếu bạn sắp xếp , hãy ký số nguyên cuộc sống là nỗi đau lớn hơn nhiều, bởi vì bạn muốn xử lý bit quan trọng nhất khi được ký. Tôi khuyên bạn nên xử lý mọi thứ như unsigned, và sau đó nếu bạn thực sự cần ký, trong bước cuối cùng của bạn sắp xếp radix, bạn sẽ hoán đổi các thùng, để các thùng có ý nghĩa nhất 1 đến trước một ý nghĩa nhất 0. Vấn đề này là chắc chắn dễ dàng hơn nếu k chia kích thước chữ.

Answer 2

Không sử dụng cơ sở 10, sử dụng cơ sở 16.

for (int i = 0; i < 8; i++) { 
    printf("%d\n", (n >> (i*4)) & 0xf); 
} 

Kể từ khi các số nguyên được lưu trữ nội bộ trong hệ nhị phân, điều này sẽ có hiệu quả hơn chia cho 10 để xác định thập phân chữ số.