أفضل طريقة للحصول على أرقام فردية من INT لفرز Radix في C/C ++

Question

ما هي أفضل طريقة للحصول على أرقام فردية من int مع عدد n من الأرقام لاستخدامها في خوارزمية فرز Radix؟ أنا أتساءل عما إذا كانت هناك طريقة جيدة بشكل خاص للقيام بذلك في C/C ++ ، إن لم يكن ما هو الحل الأفضل؟

تحرير: فقط للتوضيح ، كنت أبحث عن حل بخلاف تحويله إلى سلسلة ومعاملته مثل مجموعة من الأرقام.

Answer 1

استخدم أرقام الحجم 2^k. لاستخراج nالرقم:

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

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

باستخدام التحول والقناع (الممكّن من خلال كونه قوة 2) يتجنب تعليمات العدد الصحيح باهظ الثمن.

بعد ذلك ، يعد اختيار أفضل قاعدة هو سؤال تجريبي (Time/Space Bonstoff لأجهزةك الخاصة). المحتمل k==3 (قاعدة 8) يعمل بشكل جيد ويحد من عدد الدلاء ، ولكن k==4 (قاعدة 16) تبدو أكثر جاذبية لأنها تقسم حجم الكلمة. ومع ذلك ، لا يوجد شيء خاطئ حقًا في قاعدة لا تقسم حجم الكلمة ، وقد تجد أن القاعدة 32 أو قاعدة 64 أداء أفضل. إنه سؤال تجريبي وقد يختلف على الأرجح عن طريق الأجهزة ، وفقًا لكيفية تصرف ذاكرة التخزين المؤقت وعدد العناصر الموجودة في صفيفك.

ملاحظة أخيرة: إذا كنت تقوم بالفرز وقعت تعد حياة الأعداد الصحيحة ألمًا أكبر بكثير ، لأنك تريد علاج الشيء الأكثر أهمية كما تم التوقيع عليه. أوصي بمعالجة كل شيء على أنه غير موقّع ، ثم إذا كنت بحاجة حقًا إلى التوقيع ، في الخطوة الأخيرة من نوع Radix الخاص بك ، ستقوم بتبديل الدلاء ، بحيث تأتي الدلاء ذات الأهم 1 قبل أكثر أهمية 0. هذه المشكلة بالتااكيد أسهل إذا k يقسم حجم كلمة.

Answer 2

لا تستخدم قاعدة 10 ، استخدم قاعدة 16.

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

نظرًا لأن الأعداد الصحيحة يتم تخزينها داخليًا في الثنائي ، فإن هذا سيكون أكثر كفاءة من التقسيم على 10 لتحديد عدد عشري الأرقام.