استخراج ن أهم بت غير صفرية من كثافة العمليات في ج without بدون حلقات
-
16-12-2019 - |
سؤال
أريد استخراج ن أهم بت من عدد صحيح في ج convert وتحويل تلك ن بت إلى عدد صحيح.
على سبيل المثال
int a=1200;
// its binary representation within 32 bit word-size is
// 00000000000000000000010010110000
الآن أريد استخراج 4 أرقام الأكثر أهمية من هذا التمثيل ، أي.1111
00000000000000000000010010110000
^^^^
وتحويلها مرة أخرى إلى عدد صحيح (1001 في عشري = 9).
كيف هو ممكن مع ج simple وظيفة بسيطة دون الحلقات?
المحلول
تحتوي بعض المعالجات على تعليمات لحساب الأصفار الثنائية البادئة لعدد صحيح ، وبعض المجمعين لديهم معلومات أساسية للسماح لك باستخدام هذه التعليمات.على سبيل المثال ، استخدام دول مجلس التعاون الخليجي:
uint32_t significant_bits(uint32_t value, unsigned bits) {
unsigned leading_zeros = __builtin_clz(value);
unsigned highest_bit = 32 - leading_zeros;
unsigned lowest_bit = highest_bit - bits;
return value >> lowest_bit;
}
من أجل البساطة ، تركت الشيكات التي تتوفر العدد المطلوب من البتات.لمترجم مايكروسوفت ، ويسمى جوهري __lzcnt
.
إذا كان المترجم الخاص بك لا يوفر ذلك جوهريا ، ولم يكن لدى المعالج تعليمات مناسبة ، فإن إحدى طرق حساب الأصفار بسرعة هي البحث الثنائي:
unsigned leading_zeros(int32_t value) {
unsigned count = 0;
if ((value & 0xffff0000u) == 0) {
count += 16;
value <<= 16;
}
if ((value & 0xff000000u) == 0) {
count += 8;
value <<= 8;
}
if ((value & 0xf0000000u) == 0) {
count += 4;
value <<= 4;
}
if ((value & 0xc0000000u) == 0) {
count += 2;
value <<= 2;
}
if ((value & 0x80000000u) == 0) {
count += 1;
}
return count;
}
نصائح أخرى
انها ليست سريعة ، ولكن (int)(log(x)/log(2) + .5) + 1
سوف اقول لكم موقف أهم بت غير الصفر.الانتهاء من الخوارزمية من هناك إلى حد ما على التوالي إلى الأمام.
يبدو أن هذا يعمل (تم في C # مع UINT32 ثم تم نقله حتى اعتذار إلى Bjarne):
giveacodicetagpre.افترضت أنك تعني استخدام الرياضيات الصحيحة فقط.
استخدمت بعض الرموز من رابط @ olicharlesworth's، يمكنك إزالة الشرطية أيضا باستخدام LUT للحصول على رمز زائدة الأصفار هناك.