CSC - SY

في حالتي ملفات الرأسية هي:

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

والشفرة التي قبل الحلقتين هي:

const unsigned int iterations = 1E9;
unsigned int number, i, j;
struct timeval time_start = {0}, time_end = {0};

والشفرة التي استخدمتها لعرض النتائج هي:

printf("Using the ... it is possible to execute %.1f million iterations"
    " per second.\n\n", (double) iterations / ((time_end.tv_sec - time_start.tv_sec) + 0.000001 *
    (time_end.tv_usec - time_start.tv_usec)) * 0.000001);

في حالتك فأنت تستخدم GetTickCount فإن كان ما ترجعه هذه الدالة معبرًا عن الزمن فإن النسبة يجب أن تكون قريبة إن كان المعالج هو نفسه. في حالتي فأنا أستخدم نظام iMac 24'' بمعالج Intel Core 2 Duo.

هل تستطيعون في بيئة وندز استخدام نفس شفرتي بالضبط وتشغيلها على معالج Intel Core 2 Duo؟ فأنا لا أستطيع استخدام GetTickCount فهي دالة وندز ولا يوجد مكافئ لها في بيئة الماكنتوش. شفرتي الكاملة قصيرة وهي تستخدم gettimeofday:

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
 
int main (int argc, const char * argv[]) {
    const unsigned int iterations = 1E9;
 
    unsigned int number, i, j;
    struct timeval time_start = {0}, time_end = {0};
 
    printf("Leading One Detector (comparison test)\n\n");
 
    gettimeofday(&time_start, NULL);
    for (i = 0; i < iterations; ++i) {
        number = rand();
        __asm {
            mov edx, number
            bsf edx, edx
        }
    }
    gettimeofday(&time_end, NULL);
 
    printf("Using the bit scan instruction it is possible to execute %.1f million iterations"
    " per second.\n\n", (double) iterations / ((time_end.tv_sec - time_start.tv_sec) + 0.000001 *
    (time_end.tv_usec - time_start.tv_usec)) * 0.000001);
 
    gettimeofday(&time_start, NULL);
    for (i = 0; i < iterations; ++i) {
        number = rand();
        for (j = 0; number; number >>= 1, ++j) ;
    }
    gettimeofday(&time_end, NULL);
 
    printf("Using a loop it is possible to execute %.1f million iterations"
    " per second.\n\n", (double) iterations / ((time_end.tv_sec - time_start.tv_sec) + 0.000001 *
    (time_end.tv_usec - time_start.tv_usec)) * 0.000001);
 
    return 0;
}

وجدت هذه الشفرة في واحد من الأمكنة والغرض منها إيجاد بديل لدالة gettimeofday من دوال API الوقتية في وندز. لا أعرف إن كانت تعمل جيدًا أم لا:

#include <time.h>
#include <windows.h>
#if defined(_MSC_VER) || defined(_MSC_EXTENSIONS)
#define DELTA_EPOCH_IN_MICROSECS  11644473600000000Ui64
#else
#define DELTA_EPOCH_IN_MICROSECS  11644473600000000ULL
#endif
 
struct timezone
{
    int  tz_minuteswest; /* minutes W of Greenwich */
    int  tz_dsttime;     /* type of dst correction */
};
 
int gettimeofday(struct timeval *tv, struct timezone *tz)
{
    FILETIME ft;
    unsigned __int64 tmpres = 0;
    static int tzflag;
 
    if (NULL != tv)
    {
        GetSystemTimeAsFileTime(&ft);
 
        tmpres |= ft.dwHighDateTime;
        tmpres <<= 32;
        tmpres |= ft.dwLowDateTime;
 
        /*converting file time to unix epoch*/
        tmpres -= DELTA_EPOCH_IN_MICROSECS; 
        tmpres /= 10;  /*convert into microseconds*/
        tv->tv_sec = (long)(tmpres / 1000000UL);
        tv->tv_usec = (long)(tmpres % 1000000UL);
    }
 
    if (NULL != tz)
    {
        if (!tzflag)
        {
            _tzset();
            tzflag++;
        }
        tz->tz_minuteswest = _timezone / 60;
        tz->tz_dsttime = _daylight;
	}
 
    return 0;
}

يبدو أن الشفرة أعلاه تعمل جيدًا (الشفرة المحاكية لـgettimeofday في بيئة وندز) فقد جربتها على محسابي المحمول في بيئة وندز وهو بمعالج Pentium 4 Mobile (من الإصدارات المبكرة الموجهة للحواسب المحمولة وقبل ذلك كانت المحاسيب المحمولة تستخدم معالجات مكتبية) وحصلت على هذه النتائج:

التشغيلة الأولى:

Using the bit scan instruction it is possible to execute 261.4 million iterations per second.
Using a loop it is possible to execute 18.1 million iterations per second.

التشغيلة الثانية:

Using the bit scan instruction it is possible to execute 254.7 million iterations per second.
Using a loop it is possible to execute 18.1 million iterations per second.

التشغيلة الثالثة:

Using the bit scan instruction it is possible to execute 252.2 million iterations per second.
Using a loop it is possible to execute 18.1 million iterations per second.

للمقارنة العادلة والتأكد الإضافي أنا أقترح استبدال:

__asm {
    mov edx, number
    bsf edx, edx
}

بـ:

__asm {
    push edx
 
    mov edx, number
    bsf edx, edx
    mov j, edx
 
    pop edx
}

النتائج عندي كانت قريبة.

وأما بالنسبة للتطابق في النتائج فقد أضفت هذه الشفرة:

for (i = 0; i < (iterations >> 8); ++i) {
    number = rand();
 
   // Method 1
   for (j = 0; number; number >>= 1, ++j) ;
   // Method 2	
   __asm {
       push edx
 
       mov edx, number
       bsf edx, edx
       mov k, edx
 
       pop edx
   }
 
   if (j != k) {
       i = -1;
       break;
   }
}
 
if (i < 0)
   printf("Results of both methods mismatch!\n");
else
   printf("Results of both methods of detecting leading bit match "
      "(over %u iterations of random numbers).\n", iterations >> 8);

والنتيجة تؤكد أن النتائج متطابقة. يعني المقارنة تتم بين شفرتين صحيحتين تعطيان النتائج نفسها.

Results of both methods of detecting leading bit match (over 3906250 iterations of random numbers).

طيب ممكن تجرب طريقة unrolled loop وتعطينا نتيجتها مقارنة مع الطريقتين السابقتين
وكمان اذا فيك تجرب غير compiler أو اذا كان فيك تفعل الـ optimization
لأنو بظن الاختلاف بالنتائج هو بسب الـ compiler أو بسبب الـ optimization
مابظن استخدام gettimeofday أو GetTickCount رح يغير شي, على كل حال رح جرب الكود الي كتبته متل ماهو.

المصرف الذي أستخدمه (XCode في بيئة ماكنتوش) مبني على الإصدار الأحدث من مصرف GCC وهو المصرف الذي تستند عليه البرمجيات المفتوحة، وفي خيار درجات الاختزال Optimisation Level توجد بضعة خيارات منها Fastest ومنها Fastest, Smallest وقد جربت الاثنتين من دون فرق يذكر.

جربت أيضًا فك الحلقة بالطريقة نفسها التي استخدمتها أنت ولم أجد فرقًا:

Using the bit scan instruction it is possible to execute 83.2 million iterations per second.
Using a loop it is possible to execute 8.6 million iterations per second.

جربت الكود متل ماهو (بس استخدمت gettimeofday من هون)
وما اختلفت النسبة (على معالج AMD Turion X2)ـ:

<br />
Using the bit scan instruction it is possible to execute 20.7 million iterations per second.<br />
Using a loop it is possible to execute 15.9 million iterations per second.<br />

هذه الملفات التنفيذية لا تعمل:

This application has failed to start because the application configuration is incorrect

لم يخطر ببالي حتى الآن أنني كان يجدر بي أن أجري المقارنة بين ملفات الإطلاقة النهائية (Release edition) لا بين ملفات الإصدارة الأولية (Debug edition) وقد فعلت ذلك للتو وحصلت على نتائج مختلفة قليلاً في حالة الحلقة العادية ومختلفة كثيرًا في حالة الحلقة المفرودة.

فأما بالنسبة للحلقة العادية فقد حصلت على هذه الأرقام:

Using the bit scan instruction it is possible to execute 83.7 million iterations per second.
Using a loop it is possible to execute 30.4 million iterations per second.

وأما بالنسبة للحلقة المفرودة الغريبة التي كتبها فؤاد فقد كانت النتيجة مدهشة (وغرابة تلك الحلقة المفرودة هي في أنها لا تستخدم القفزات لتجاوز العمليات غير الضرورية):

Using the bit scan instruction it is possible to execute 84.6 million iterations per second.
Using a loop it is possible to execute 85.8 million iterations per second.

وبقدر ما أنا مدرك أن فرد الحلقات بهذه الطريقة غير عملي في البرامج الحقيقية (مما لا يقل في قلة عمليته عن استخدام شفرة أسمبلي) فقد وجدت النتائج مثيرة للدهشة وتجعلني راغبًا بشدة في الفهم الإضافي، مما ربما أمحصه لوحدي فربما نكون قد غصنا أكثر من اللازم للتو وأخذنا هذا الموضوع بعيدًا عن قصده الأصلي.

إضافة:

جربت حلقة ثابتة الطول تشبه الحلقة المفرودة لكن من دون فرد:

for (k = 0; k < 32; ++k) {
    number >>= 1; 
    j = j + (number > 0);
}

والنتيجة كانت عادية (لم تعطِ نتائج مثيرة مثل الحلقة المفرودة):

Using the bit scan instruction it is possible to execute 86.9 million iterations per second.
Using a loop it is possible to execute 33.3 million iterations per second.

بعد مزيد من التمحيص اكتشفت بأنني ارتكبت الكثير من الأخطاء وهو ما يجعل الكثير من النتائج التي بعثتها غير موثوقة. لذا ولأنني لا أحب أن أقدم معلومات غير موثوقة فسألخص الحال التي انتهينا إليها بالتالي:

١. لاكتشاف ما إذا كان الرقم قوة من قوى الاثنين فالحل الأمثل هو: "الرقم" وو ("الرقم" - ١)
٢، لاكتشاف مكان البت المعلم في الكلمة الثنائية فيوجد بضعة طرق منها استخدام تعليمات المسح البتي في معالجات إنتل ومنها استخدام حلقة، وليس واضحًا تمامًا أية طريقة هي المفضلة والتي تحقق توازنًا مقبولاً بين قابلية الكتابة في شفرة عالية المستوى والأداء.

(عدم موثوقية النتائج المبعوثة في حالتي معزو إلى موثوقية الأدوات التي أستخدمها وحقيقة أن دالة rand لم تكن تعمل بشكل صحيح (ترجع الرقم نفسه دائمًا) بالإضافة إلى قلة دقة في تمثيل تعليمة المسح البتي باستخدام حلقة عادية، والخلل التصميمي في توفير كلمات ثنائية فيها بضع بتات معلمة للمقارنة في حين كان من الواجب توفير كلمات عشوائية فيها بت واحد معلم. باختصار، يبدو أن الأمر لا يمكن تمحيصه بذهن مشوش ومشغول وبأشياء أخرى وهو ما يبدو أنه أدى إلى فوضى عارمة ورؤية مشوشة).

يمكن لأنو بهالحالة (loop unwinding) رح تقلص عمليات ال jump وال conditional branch لأقل حد ممكن وهالشي أكيد الو علاقة بالcompiler.

المهم انو بالنسبة لتعليمة BSF (يلي كل هالاختبارات مشانها) قدرنا نستبدلها بمجموعة تعليمات (32 عملية إزاحة وجمع و مقارنة) وحصلنا على أداء أفضل!

بالنسبة لفرد الحلقة بهالحالة هي بالذات بظن فرق الأداء ناتج عن التخلص من تعليمات القفز المشروطة

شكرا عروة وفؤاد

يعني (حسب ما فهمت) بامكانك تنفذ n تعليمة خلال:

بفرض هالتعليمات مستقلين ومافي بينهم ارتباط (وهون المشكلة الرئيسية)

<br />
--------<br />
    --------<br />
        --------<br />
            --------<br />

مساء الخير

اسعدني قراءة المداخلات العديدة و الشيفرات المختلفة التي كتبها الاخوة

---- قياس الأداء ----------
بالنسبة الى قياس الاداء اقوم باستخدام طريقة مختلفة وهي تكرار العملية عدد من المرات وقياس الوقت و قسمته على عدد المرات

</p>
<p>time_reselution= 1000000;</p>
<p>start_time_point1 = now(); </p>
<p>for(i=1; i<=time_reselution; i++)  ;</p>
<p>end_time_point1= = now(); </p>
<p>lost_time = msbetween(start_time_point1,end_time_point1);</p>
<p>start_time_point2 = now(); </p>
<p>for(i=1; i<=time_reselution; i++) x=1+1 ;</p>
<p>end_time_point2= = now(); </p>
<p>done_time = msbetween(start_time_point2,end_time_point2);</p>
<p>real_time = (done_time - lost_time)/time_reselution;</p>
<p>

هذا مثال للطريقة التي اقوم باستخدامها و المثال يقوم بحساب الوقت اللازم لجمع 1+1

و لكن المشكلة الحقيقية في قياس الاداء ان انظمة تعدد المهام قد تعطي نتائج مختلفة في كل مرة يتم فيها قياس الاداء بسبب تشغيلها لاكثر من مهمة ولانه لا يمكن التنبؤ بالوقت الذي قد تاخذه المهام الاخرى من تضيع وقت يؤثر على قياس الاداء

و ايضا وجود مشكلة قدرة المعالج على تشغيل اكثر من تعليمة اذا لم تكن تلك التعليمات مرتبطة ببعضها البعض

------- الحصول على لوغريثم 2 لرقم log2

اعتقد انه يجب في البداية عمل تبديل بين البايت الاول و الاخير
ضمن الكلمة التي هي عبارة عن 4 بايت

s: و من ثم اعتقد ان تدوير الرقم باستخدام تعليمة ror مرة واحدة
و الحصول على البت الاعلى عن طريق and او or
end s

و تكرار s عدد 31 مرة

بالنسبة لملف الاختبار BSF_Test_Unrolled
يبدو أن الـ compiler قرر إزالة التعليمات التي ليس لها أهمية
فمثلا ضمن (unrolled loop)
يوجد فقط تعليمة واحدة و هي SUB EBX,1

كما أن تعليمة BSF يتم تنفيذها ضمن نبضة ساعة واحدة حسب المعالج
CPUID=06_17 أو CPUID=06_1D
ينبغي فحص الملف الذي يقوم بتوليده الـ compiler قبل اعتماده.
ما رأيكم؟

اهلا اخي

لا استغرب ان يقوم المترجم بعمل اخطاء

اعتقد لا بد من وجود طريقة لمنع التحسين optimization

على جزء من الكود

و تحية

الاختبارات السابقة لتقدير سرعة تعليمة BSF مقارنة بما يكافئها دفعتني لتعلم المزيد عن دقة قياس الزمن, فتعليمة GetTickCount تعطي الزمن بوحدة جزء بالألف من الثانية (milliseconds) أما تعليمة QueryPerformanceCounter فمن أجل دقة أعلى (أو لقياس أزمنة أقل من جزء بالألف من الثانية)
و تعتمد وحدة القياس على نتيجة تعليمة QueryPerformanceFrequency وتختلف حسب الجهاز. ولكني أفضل معرفة عدد نبضات الساعة. ولحسن حظي فإن معظم المعالجات الحديثة (على الأقل معالجات Intel) تقدم تعليمات لقياس الأداء تتضمن عدد نبضات الساعة!! فمن أجل لغزنا السابق أفضّل تعليمة RDTSC أو Read Time-Stamp Counter وهي, برأيي الأكثر دقة. ولكن ينبغي منع أثر التداخل مع التطبيقات الأخرى وتعدد المهام والمقاطعات وهنا تكمن الصعوبة, فمنع المقاطعات (التي يمكن منعها) مثلا يحتاج لتعليمة CLI أو Clear Interrupt Flag وهي تعليمة لا يمكن استخدامها ضمن التطبيقات العادية والتي تعمل ضمن ما يسمى Ring3 ولتخطي هذه العقبة يمكن انشاء Driver ($!@X?!) يعمل ضمن Ring0 وبالمستوى الأدنى DIRQL!! أو يمكن العمل خارج نظام التشغيل ضمن ما يسمى Real Mode أو, ببساطة, انشاء اختبار يعمل ضمن شريحة الزمن المتاحة للتطبيق ضمن نظام التشغيل ورفع أولوية التطبيق من خلال SetPriorityClass إلى HIGH_PRIORITY_CLASS أو REALTIME_PRIORITY_CLASS
بسبب شعوري بالكسل قمت بتعديل برنامج اختبار وجدته ضمن MASM32
البرنامج الأصلي يوجد ضمن masm32\examples\exampl10\timer_demos\xchg

إليكم برنامج الاختبارلأنظمة Windows.
ويبدو أن معالجات AMD تدعم تعليمة RDTSC.

بظن الشركة المصنعة للمعالج بتعرف بالظبط عدد الدورات اللازمة لتنفيذ كل تعليمة (وقد تتيح هالمعلومات للعموم)
بس الأهم من قياس زمن تنفيذ تعليمة وحدة هو قياس أداء خوارزمية ما مقارنة مع خوارزمية تانية (على عينة بيانات كبيرة وعشوائية)
هاد الشي الي كنا عم نحاول نعمله بس ارتكبنا كتير أخطاء وهفوات

اذا بدكون ممكن نعمل مثلاً عدة برامج (باستخدام عدة طرق bsf, shr, sub) لتنفيذ مهمة ما (مثلاً ايجاد مجموع عدد الأصفار الموجودة في بداية كل رقم بين 1 و 2^32. ممكن نعتبر هاد لغز جديد ) ومنقارن النتائج (زمن تنفيذ البرنامج كاملاً) لحتى نشوف قديش ممكن نحصل على تحسن بالأداء باستخدام bsf مع مقطع asm ضمن الكود.

حلي في التعليق السابق اللاحق!!

حسنا

ابليت بلاءا حسنا في مناقشة مشروع تخرجي

سوف اضع حل هو ليس حلي و لكنه موجود في احد كتب السلسلة المعنونة "فن برمجة الكمبيوتر" للعالم دونالد نوث

Donald Knuth
The Art of Computer Programming Vol IV
p 11

الحل مثالي لتشغيله على التوازي ايضا لانه يمكن ان يتم بشكل متوازي تشغيل قطع من الشيفرة

الحل مسجل باسم
Wilkes, Wheeler and Gill

هو مثال وضع في كتاب لهؤلاء الثلاثة

وقرأت عن وجود تعليمة لمعالجات انتل
POPCNT
تقوم بعدد البتات التي قيمتها 1

على كل هذا هو الكود

اخي عروة و فؤاد

اتمنى تجربة قياس اداء البرنامج في الاسفل ومقارنته بالحلول الاخرى

</p>
<p>int countons(unsigned int n)<br />
{</p>
<p>   n = (n & 0x55555555) + ((n >> 1) & 0x55555555) ;<br />
   n = (n & 0x33333333) + ((n >> 2) & 0x33333333) ;<br />
   n = (n & 0xF0F0F0F) + ((n >> 4) &  0xF0F0F0F) ;<br />
   return n % 0xFF ;</p>
<p>}</p>
<p>int countzeros(unsigned int n)<br />
{<br />
    return 32-countons(n);<br />
}</p>
<p>

وجدت طريقة اخرى من مختبرات جامعة MIT

ملخص الطريقة اذا كان لديك رقم مكون من 3 بت

مثلا الرقم x

وكان y = x shr 1
و z = y shr 1

عدد بتتات x

x-(y+z

وطبعا ممكن تطبيق ذلك على 32 بت دفعة واحدة

</p>
<p>int bitcount(unsigned int n) {<br />
   /* works for 32-bit numbers only    */<br />
   /* fix last line for 64-bit numbers */</p>
<p>   register unsigned int tmp;</p>
<p>   tmp = n - ((n >> 1) & 033333333333)<br />
           - ((n >> 2) & 011111111111);<br />
   return ((tmp + (tmp >> 3)) & 030707070707) % 63;<br />
}</p>
<p>

اعجبتني هذه الطريقة

استخدام BSF

<br />
    mov ecx, 0<br />
    mov edx, 1</p>
<p>    nextDigit:<br />
    bsf eax, edx<br />
    add ecx, eax<br />
    inc edx<br />
    jnz nextDigit<br />

<br />
    mov ecx, 0<br />
    mov edx, 1</p>
<p>    countZeros:<br />
    mov eax, edx<br />
    dec ecx</p>
<p>    nextBit_sub:<br />
    inc ecx<br />
    shr eax, 1<br />
    jnc nextBit_sub</p>
<p>    nextDigit:<br />
    inc edx<br />
    jnz countZeros<br />

<br />
using bsf... 4294967263 zeros<br />
20714 ms<br />
using shr... 4294967263 zeros<br />
23959 ms, shr<br />

@rani_walhan
هذه الخوارزميات تقوم بعد الواحدات (أو الأصفار) في كامل الرقم.
اللغز الحالي هو عدد الأصفار في بداية الرقم (ثم حساب المجموع):

<br />
001 => 0<br />
010 => 1<br />
011 => 0<br />
100 => 2<br />
101 => 0<br />
110 => 1<br />
111 => 0<br />
SUM(1 -> 7) => 4<br />

عفوا لم انتبه الى اللغز الاخير

بالنسبة لي سوف آخذ اسوء الاحتمالات واضعها بعين الاعتبار بمعنى ان يكون الاداء نفسه تقريبا بجميع الحالات

consider worst case

اسوء الاحتمالات بالنسبة ارقم 32 بت ان تكون قيمته 0 و بالتالي سوف يتم فحص جميع البتات قبل اعطاء النتيجة لاقلل تاثير هذه الظاهرة سوف افحص كل بايت من الاربعة بدءا بالاعلى حتى اعرف اين اول بت
الحل سوف يجعل قيم الالافضل و الاسوء متقاربة بما يسمى الثبات

على كل سوف اضع الحل بشكل خوارزمية

<br />
if eax[4] <> 0 then<br />
idx = 4<br />
else if eax[3] <> 0<br />
idx = 3<br />
else if ah <> 0<br />
ecx = 2<br />
else if al <> 0<br />
idx = 1<br />
 else jmp z<br />
find_first_one(eax[idx])<br />
jmp end<br />
z: ebx =0<br />
end:<br />

اعود بمشاركة بعد ان انعشت اكواد اخي sh_que_L ذاكرتي
وقمت بتحويل شرحي للحل الى لغة الاسمبلي

وهذا هو حلي لمسالة البحث عن اول بت قيمته 1 و ايضا لارجاع عدد الاصفار التي قبله وقمت بكتابة ملاحظات على الاجراء في الاسفل

وتحية

- ملاحظة - متاكد من وجود اخطاء حيث لم اقم بتجربة الاجراء -

اتمنى في حال قياس الكفاءة للطرق العديدة التي هي حلول للمسالة
ان يتم القياس على 32 رقم و هي جميع الارقام التي هي 2 مرفوع الى رقم 1 2 4 8 16 ..

حتي يتسنى قياس المعدل الوسط بين اسوء الاحتمالات وافضلها

وتحية

</p>
<p>// i choose to devide the 32 bit to 4 bytes<br />
// and work on the first non zero byte by msb </p>
<p>// input : eax the 32 bit number<br />
// oitput : dl is the pos of 1st one msb<br />
//          dh is the count of zeros before dl pos<br />
// sgment : cl where eax[cl] is a byte inside eax</p>
<p>mov eax , 0xFFFFF // value of 32 bit number</p>
<p>xor dl,dl<br />
mov cl,4<br />
bswap eax</p>
<p>seg3:<br />
dec cl<br />
or al,0<br />
jz seg2<br />
bsf al,dl<br />
jmp compute</p>
<p>seg2:<br />
dec cl<br />
or ah,0<br />
jz seg1<br />
bsf ah,dl<br />
jmp compute</p>
<p>seg1:<br />
bswap eax<br />
dec cl<br />
or ah,0<br />
jz seg0<br />
bsf ah,dl<br />
jmp compute</p>
<p>seg0:<br />
dec cl<br />
or al,0<br />
jz donz<br />
bsf al,dl</p>
<p>compute:<br />
shl cl,3<br />
add cl,dl<br />
jmp dono</p>
<p>donz:<br />
sub dl,1<br />
// dl = ff if there is not ones even in the low lsb byte<br />
// could be changed<br />
dono:<br />
mov dh,32<br />
sub dh,dl</p>
<p>

<br />
    mov ecx, 0<br />
    mov edx, 1</p>
<p>    nextDigit:<br />
    bsf eax, edx<br />
    add ecx, eax<br />
    inc edx<br />
    jnz nextDigit<br />

<br />
    mov ecx, 0<br />
    mov edx, 1</p>
<p>    countZeros:<br />
    mov eax, edx<br />
    dec ecx</p>
<p>    nextBit_sub:<br />
    inc ecx<br />
    shr eax, 1<br />
    jnc nextBit_sub</p>
<p>    nextDigit:<br />
    inc edx<br />
    jnz countZeros<br />

حسب رأيي الشخصي معالج انتل ينقصه القدرة على قياس الاداء

اعتقد ان على انتل ان تضع هذا الشيئ بعين الاعتبار لانه معالجات انتل تعاني من رحيل الادمغة عنها و تفقد فرصة ان يعمل الباحثون و المحترفون على معالجاتها مما سوف يؤثر سلبا على منتجات انتل نستقبلا

على كل في لاسطر قمت بوضع عدد التعليمات من نوع معين ويمكن حساب الاداء من معرفة عدد الدورات او وقت التنفيذ الحقيقي

<br />
---BSF--<br />
02 mov<br />
32 bsf<br />
32 add<br />
32 inc<br />
32 jnz</p>
<p>-- shift --<br />
03 mov<br />
01 dec<br />
64 inc<br />
32 shr<br />
32 jnc<br />
32 jnz</p>
<p>

أخي فؤاد نتيجة الاختبار على جهاز قديم

وسأحاول تجربة حل أخي rani_walhan ووضع النتيجة هنا

أخي العزيز

لا اعرف كيف تقوم بعمل تجربة الاداء لكن اتمنى منك ان تقوم بعمل تجربة اداء كالتالي

اجراء 33 تجربة

بحيث التجربة الاولى تكون قيمة الرقم 0

التجربة الثانية 2 مرفوع الى قوة 0
.
.
.
.
التجربة 33 تكون 2 مرفوع الى قوة 31

و تكرار كل تجربة عدد كافي من المرات لقياس اداء

</p>
<p>tested_num = 0;</p>
<p>for (i=-1;i<3; i++)<br />
{</p>
<p>init_time();<br />
do_the_test(tested_num);<br />
save_time();</p>
<p>print_time();</p>
<p>tested_number = tested_number shl 1;</p>
<p>if (tested_num == 0) tested_number=1;</p>
<p>}</p>
<p>

اريد قياس شيئ يسمى الثبات في الاداء

سوف تشاهد ان الكود سوف يختلف اداؤه في ال 32 حالة المختلفة

واسوء اداء سوف يكون عندما يكون الرقم = 0

@sh_que_L
يعني فرق الأداء عم يكون بسيط نسبياً! (مع انو عم نستبدل تعليمة وحدة BSF بحلقة)

بس ياترى شو هي الطريقة المثالية لحل اللغز السابق! (حساب مجموع عدد الأصفار الموجودة في بداية كل رقم بين 1 و n)

مساء الخير

للاسف العمل و الدراسة و اشياء اخرى

تاخذ معظم الوقت و ليس متاح كما كان في السابق اجراء تجارب واسعة

بالنسبة الى كود اخي sh_que_L اعتقد ان الاكثر من حل لديه لديها نفس اسوء و افضل حالة اداء مع اختلاف الاداء بالنسبة للقيم المختلفة في كل طريقة فتكون احيانا shl افضل و اخرى bsf أفضل على حسب الرقم

واسوء حالة اداء عندما تكون قيمة الرقم المراد فحصه 0 حيث سوف يستهلك اقصى دورات متاحة لامر bsf و في حالة shl سوف يستمر التكرار الى اخر بت

و افضل حالة هي 2 مرفوعة الى القوة 31 سوف يستهلك فيها bsf عدد من الدورات هي 6 بينما shl سوف يستهلك دورة واحدة

على كل اعتقد من الافضل تحديد اسوء حالات اداء لكل كود و افضل حالات اداء وقياسها عن طريق محاكيات simulators

سمعت بمحاكي ممتاز لكن لم اقم باستخدامه او معرفة ان كان فيه قدرة على قياس دورات المعالج لبرنامج معين موجود في الرابط

[http://www.ptlsim.org/index.php]

اتمنى الاطلاع عليه من طرف الاخوة هنا و تقدير ان كان مناسب لقياس الحلول

بالنسبة الى الكود الذي قمت باقتراحه فاسوء حالة اداء اعتقد عندما تكون قيمة الرقم المراد فحصه 1
و افضل حالة اداء عندما يكون الرقم 2 مرفوعة الى الاس 31

على كل قمت بالرجوع الى دليل فيه دورات تعليمات المعالج 486 و واستبعدت ان المعالج قادر على تنفيذ اكثر من تعليمة واحدة في نفس الدورة حتى احصل على حساب تقريبي

فكانت النتائج بالنسبة لبرنامجي في احسن الحالات 22 دورة
وفي اسوء الحالات 26

وسوف يكون معدل الاداء 24 دورة

لا اعرف سبب استخدام عملية jnz في حالة الــ bsf في برنامج اخي
sh_que_L
حيث يقوم هذا الامر بايجاد اول خانة فيها الرقم 1 ولا حاجة لتكراره
الا اذا كان مطلوب فحص اكثر من قيمة مدخلة واحدة

اريد ان انبه ان اسوء حالات bsf عند استخدام 32 بت هي 43 دورة وافضلها 6 دورات

واذا تم حساب ذلك مع باقي التعليمات التي سوف يتم استخدامها
سوف يكون الرقم غير مناسب و سوف تكون تعليمة shl افضل

على كل اعتقد ان استخدام برنامجي مع تعديله ليستخدم shl بدلا من bsf هو حل ممتاز ولكن انتظر ان تثبت النتائج بعد التعديل
ان كان مجموع 33 اداء مقسومة على 33 تمثل افضل بالنسبة للحلول الاخرى
علما ان 33 هي جميع الاحتمالات في المسألة التي اشرت اليها سابقا

حيث سوف يحتاج امر shl في الطريقة التي قدمتها 1 دوة في افضل الحالات
بدلا من 6 دورات لمعالج 486 بالنسبة الى امر bsf في افضل حالاته

لكن بالنهاية لا بد ان يتم احساب الاسوء ايضا

للحصول على معدل الاداء

وتحية

أخي foaad اقتنعت بصحة كلامك، لا يوجد فرق مهم في الأداء
أما عن الحل الأمثل للأرقام من ١ حتى n فاتوقع وجود طريقة حسابية مختصرة، ساحاول استنتاجها أو إيجدها إن أمكن.

أخي rani_walhan بالنسبة لقياس الأداء بعدد دورات الساعة لتعليمة BSF reg,reg للمعالجات القديمة

وهي تختلف باختلاف الرقم، بينما للمعالجات الحديثة, وفقا لـ

وهي قيم الحالة الأسواء. ومجرد معرفة عدد دورات الساعة لمجموعة من التعليمات لم تعد تكفي لقياس الأداء ضمن المعالجات الحديثة. فمن أجل مقارنة خوارزميتين يمكن قياس عدد دورات الساعة الفعلية من خلال تعليمة RDTSC ويتم حفظ النتيجة في EDX:EAX أي 64 Bits وقيمة العداد تتزايد مع كل نبضة ساعة, وهي مساحة تكفي للقياس ضمن فترة زمنية طويلة. وهي الطريقة التي استخدمتها عند المقارنة الأولى بين shl و bsf واعتمدت على Macros جاهزة ضمن MASM32 المذكور سابقا حيث يتم اجراء القياس ١٠٠٠ مرة واعطاء الوسطي، كما يتم حذف عدد الدورات الناتجة عن تعليمات الاختبار نفسه.

بالنسبة لاستخدام jnz ضمن حل لغز حساب عدد الأصفار, يتم القفز مرة لكل رقم جديد
وفي هذا الحل تم استخدام تعليمتي Windows لحساب الزمن QueryPerformanceCounter و QueryPerformanceFrequency وأيضا من MASM32 ولكن لمرة واحدة بسبب أن الاختبار نفسه تم على كل الأعداد من 1 حتى 0xFFFFFFFF

و اعتبرت الحساب من جهة اليمين كما في مثال أخي foaad ولاحظت أنك تقوم بالحساب من اليسار عند استخدام shl ومن الجهة اليمنى عند استخدام bsf

كنت أتمنى أن يشاركنا أخي عروة، خاصة أنني وجدت عدة معالجات Intel حديثة ولكنها ضمن أجهزة Mac

أخي foaad عدلت عن رأيي!! لست مقتنعا بصحة كلامك!!
إن لغزك الأخير يولد
٥٠٪ من الأرقام الخانة الأولى بقيمة ١
٢٥٪ من الآرقام الخانة الأرلى ٠ و الثانية ١
١٢.٥٪ من الأرقام الخانة الأولى ٠ و كذلك الثانية و الثالثة ١
أتمنى أن لا تكون قد اخترت هذا المثال عمدا

اخترت هالمثال لحتى يكون في نتيجة وحدة بحاجة لزمن طويل لحسابها
وبالتالي ممكن نشوف اذا كان استخدام BSF ممكن يختصر هالزمن بشكل ملحوظ أم لا وبالتالي هل في مبرر لاستخدام مقطع asm ضمن الكود أم لا.

طيب ممكن تعكس المثال وتحسب مجموع عدد الأصفار بنهاية كل رقم بين 1 و 2³²-1 (مع انو حساب هالشي ما بيحتاج للمرور على كل الأرقام)

تعلمت الكثير من هذا اللغز, شكرا rani_walhan و foaad و عروة

المثال الذي تم اختياره للمقارنة, مجرد مثال. فتمثيل الأعداد بالنظام الثنائي binary لا يعطي توزيعا عادلا لاستخدام الخانات bits, وأظن هذا سبب طلب أخي rani_walhan بتجريب 33 احتمالا. والمقصود فيها احتمالات ذات توزيع عادل.
ربما استخدام bsf و bsr غير مرتبط بالأعداد اطلاقا, وقد يكون لها تطبيق عملي أكثر عند التعامل مع البوابات مثلا, حيث التوزيع العادل للخانات مفروض.
تجربة أكثر عدلا مع استثناء الاحتمال الأسوأ, عندما يكون الرقم صفرا. تحوي أربعة اختبارات هي
اختبار تعليمة bsf

  mov ecx, [n]
  bsf eax,ecx

وما يقابلها باستخدام الازاحة shr

  mov ecx, [n]
  mov eax,ecx
  mov edx,-1
  nextBit1:
  inc edx
  shr eax,1
  jnc nextBit1

و اختبار تعليمة bsr

  mov ecx, [n]
  bsr eax,ecx

وما يقابلها باستخدام الازاحة shl

  mov ecx, [n]
  mov eax,ecx
  mov edx,-1
  nextBit2:
  inc edx
  shl eax,1
  jnc nextBit2

يتم حفظ قيمة العداد قبل كل تجربة ضمن المكدس كما يلي

  xor eax,eax
  cpuid
  rdtsc
  push edx
  push eax

ثم بعد الانتهاء من كل تجربة يتم ايجاد عدد الدورات بطرح القيمة التي تم حفظها من القيمة المقروءة

  xor eax,eax
  cpuid
  rdtsc
  pop ecx
  sub eax,ecx
  pop ecx
  sbb edx,ecx

كمحاولة لضمان استقرار قيم دورات الساعة في كل اختبار, يتم التأكد من انتهاء المعالج من تنفيذ التعليمات السابقة باضافة تعليمة cpuid مع تمرير قيمة صفر ضمن eax وذلك قبل طلب rdtsc. لم ألحظ فرقا مهما عند إلغائها, ربما تظهرأهميتها عند اختبار معالجات أخرى ولكنها بالطبع تزيد عدد دورات الساعة.

توقعت مشاهدة قيم غير مستقرة عند اختبار خانة bit واحدة أو أكثر, وأن تكون تلك الخانة (أو الخانات) عشوائية و معظمها ضمن حلقات الازاحة shl و shr, الطويلة منها خاصة. وهي تعطينا فكرة عن عدد التعليمات (عدد دورات الساعة) التي يقوم المعالج بتفيذها بعيدا عن البرنامج.

قلّ عدد تلك القيم الشاذة عند استخدام HIGH_PRIORITY_CLASS ولكن بنسبة منخفضة تكاد تكون غير مهمة, وعند تجربتي REALTIME_PRIORITY_CLASS زادت تلك القيم العشوائية بدلا من أن تنقص!! لا أعلم السبب. تم رفع سوية البرنامج قبل الاختبارات و اعادتها إلى ما كانت عليه بعد الاختبارات.

باستخدام حاسب قديم بمعالج AMD Duron 750 MHz
معظم النتائج مستقر.
استخدام تعليمتي bsf و bsr أسرع في كل الحالات باستثناء أول ثلاث خانات من أجل bsf و آخر خانتين من أجل bsr
اختبار bsf استقر عند 70 دورة بغض النظر عن الخانة التي يتم اختبارها
اختبار shr المكافئ يبدأ بـ 65 دورة ثم 67 ثم 69 و ينتهي بـ 125

قضيت وقتا طويلا مع الـ List Box, إذ يبدو أنه لا يمكن استبدال أحد أسطرها مباشرة. ففعليا يتم حذف السطر ثم إضافة سطر آخر في نفس الموقع!! ويبدو الأمر ممتعا عندما يكون إظهار شريط الإزاحة Scroll Bar متوقفا على سطر واحد, عندها سيومض ذلك الشريط 32 مرة عند كل تجربة (بسبب تعديل 32 سطرا). كما أنه عند اجراء الاختبارات عدة مرات في الثانية من خلال مؤقت Timer تبدو آلية مسح الشاشة Scanning واضحة بحسب تزامنها مع مسح الخلفية Erasing أو Filling. اخفاء تلك التشوهات يمكن بتفعيل الـ Double buffering

  LSBListBox.DoubleBuffered := True;
  MSBListBox.DoubleBuffered := True;

تركت نص التنسيق الممرر لتعليمة format متاحا للتغيير لبساطة الأمر
يمكن حفظ أي من القائمتين بملف من خلال الزر الأيمن

ممتاز

نعم كان اللغز ممتع واستمتعت بتنفيذ برنامجك المعمول على دلفي

على كل كنت اريد اجراء 33 اختبار و ضرب كل اختبار بمعامل وجوده في ال 32 بت ثم اجمع المضروبات جميعا لكل اختبار

الرقم الذي سوف ينتج بالنسبة الى shl هو نتائج الاختبار
و الرقم الذي سوف ينتج بالنسبة لـ bsf هو نتائج الاختبار

وكنت اريد ابداء وجهة نظر معينة ان الاداء الافضل سوف يكون للتعليمة التي مجموع مضروبات اداءها افضل وسوف تكون هي التي اداءها افضل عندما يكون عدد الاصفار اقل
فكلما كانت عدد الاصفار اقل زادت نسبة وجود الرقم ضمن ال 4 بلايين رقم محتمل

عدد البتات المعامل
31 50.000000000%
30 25.000000000%
29 12.500000000%
28 6.250000000%
27 3.125000000%
26 1.562500000%
25 0.781250000%
24 0.390625000%
23 0.195312500%
22 0.097656250%
21 0.048828125%
20 0.024414063%
19 0.012207031%
18 0.006103516%
17 0.003051758%
16 0.001525879%
15 0.000762939%
14 0.000381470%
13 0.000190735%
12 0.000095367%
11 0.000047684%
10 0.000023842%
9 0.000011921%
8 0.000005960%
7 0.000002980%
6 0.000001490%
5 0.000000745%
4 0.000000373%
3 0.000000186%
2 0.000000093%
1 0.000000047%
0 0.000000023%

أرجو أن لا يثنيكم عندي وتمسكي برأيي عن طرح المزيد من الأفكار والألغاز

أخي foaad لايجاد اجمالي الأصفار الواقعة على يمين الأعداد من 1 حتى N (عند تمثيلها وفق النظام الثنائي)
لاحظت أن نصف الأعداد تكون الخانة الأولى فيها صفرا و بالتالي
تساهم الخانة الأولى في مجموع الأصفار بقيمة N0=N/2 (عملية القسمة على مجموعة الأعداد الصحيحة طبعا)
ومن ضمن هذا النصف أي من ضمن الـ N0, نصفه يساهم بأصفار في الخانة الثانية وبالتالي
تساهم الخانة الثانية في مجموع الأصفار بقيمة N1=N0/2
وهكذا, نستمر إلى أن تكون نتيجة القسمة صفرا أو نغطي كل الخانات
فيكون مجموع الأصفار في الجهة اليمنى

Total=N0+N1+..+N31
Total=N/2+N/4+...N/(2^31)

حساب مجموع الأصفار Total على يمين الأعداد من 1 حتى N بلغة الباسكال:

  Total:=0;
  Ni:=N shr 1;
  while Ni>0 do
  begin
    Total:=Total+Ni;
    Ni:=Ni shr 1;
  end;

حساب مجموع الأصفار Total على يمين الأعداد من 1 حتى N بلغة الآلة ضمن Delphi:

  asm
    mov eax, [N]
    xor ecx, ecx
    Looop:
    shr eax, 1
    jz  Done
    add ecx, eax
    jmp Looop
    Done:
    mov Total,ecx
  end;

لا أظن أنها الطريقة الأمثل.

أخي rani_wahlan بالنسبة للموقع الذي أشرت إليه [http://www.ptlsim.org/index.php], يبدو أنه مميز ولكن في قسم الانزال يوجد النسخة المصدرية فقط, فلن استطيع تجربته قريبا مع الأسف. أما عن التعديل الأخير للمقارنة بين bsf و حلقة shr فقد وضعته هنا
و لأتأكد من فهمي، ماذا تقصد عندما كتبت "فكلما كانت عدد الاصفار اقل زادت نسبة وجود الرقم ضمن ال 4 بلايين رقم محتمل"؟

اهلا اخي

بالنسبة الى ptsim للاسف لم اعرف من قبل بعدم وجود نسخة مترجمة الى لغة الآلة من البرنامج

بالنسبة الى البرنامج المصنوع على الدلفي جميل جدا و الخيارات الغنية فيه تنوع القدرة على قياس الاداء

انا اعتقد ان 33 تجربة كافية لمعرفة الاداء
و وسوف تسد مكان التجارب ال 4 بلايين لكن يجب ضرب تجربة 2 ^ 31 بمعاملها 0.5 و التجارب الاخرى كل بمعامله
ومن ثم جمع كل هذه المضروبات

لدي لغز جديد وضعته لنفسي ولم اقم بحله حتى الآن وربما سوف يكون صعب حله

اللغز هو توليد مجموعة من الارقام بشكل متسلسل علما ان الارقام ليست عشوائية ولكن يجب توليد الارقام باقل عدد من الحلقات التكرارية

<br />
16, 8, 4, 2, 1, 3, 6, 5, 7, 12,10,9,11, 14, 13, 15, 24, 20, 18, 17, 19, 22, 21, 23, 28, 26, 25, 27, 30,29, 31<br />

Total=N0+N1+..+N31
Total=N/2+N/4+...N/(2^31)

<br />
16, 8, 4, 2, 1, 3, 6, 5, 7, 12,10,9,11, 14, 13, 15, 24, 20, 18, 17, 19, 22, 21, 23, 28, 26, 25, 27, 30,29, 31<br />

<br />
int arr[] = {16, 8, 4, 2, 1, 3, 6, 5, 7, 12,10,9,11, 14, 13, 15, 24, 20, 18, 17, 19, 22, 21, 23, 28, 26, 25, 27, 30,29, 31}<br />

أظن أنه من الممكن توليد هذه الأرقام من خلال LFSR

ما جعلني أفترض امكانية توليد الأرقام من خلال سجل ازاحة بتغذية خلفية خطية Linear-Feedback Shift Register أو LFSR هو أول خمسة أرقام, ثم أن الخانة ذات القيمة الأصغرLSB تستنتج من أول خانتين من العدد السابق وبمجرد xor بينهما.

محاولة استنتاج باقي العلاقات يدويا لم تكن بنفس السهولة, ولكنها كانت فرصة جيدة لتذكر مخططات كارنو Karnaugh maps, و في النهاية قمت بتجريب أحد البرامج المجانية (Logic Friday) لاستنتاج وتبسيط تلك العلاقات المنطقية
و هي:

B4 = b4 b3  + b4 b2  + b4 b1  + b4 b0 + b3 b2 b1 b0;
B3 = b3' b2 b1 b0 + b3' b2' b1' b0' + b3 b2' b1  + b4' b3 b0 + b3 b1' b0 + b3 b2 b0';
B2 = b2' b1 b0 + b2 b1' b0 + b2 b1 b0' + b3 b2' b1' b0' + b3' b1 b0;
B1 = b2 b1'  + b2' b0;
B0 = b1' b0 + b1 b0';

حلي بلغة الباسكال

var
  i:integer;
  b0,b1,b2,b3,b4:byte;      //Previous value
  bb0,bb1,bb2,bb3,bb4:byte; //Calculated value
  nextNum:Byte;

  procedure extractBits(num:byte);
  begin
    b0:=((num shr 0) and 1)*255;
    b1:=((num shr 1) and 1)*255;
    b2:=((num shr 2) and 1)*255;
    b3:=((num shr 3) and 1)*255;
    b4:=((num shr 4) and 1)*255;
  end;
begin
  extractBits(31);//Start with the last value

  for i := 0 to Length(Nums)-1 do
  begin
    bb4 := (b4 and b3) or (b4 and b2) or (b4 and b1) or (b4 and b0) or (b3 and b2 and b1 and b0);
    bb3 := (not b3 and b2 and b1 and b0) or (not b3 and not b2 and not b1 and not b0) or (b3 and not b2 and b1) or (not b4 and b3 and b0) or (b3 and not b1 and b0) or (b3 and b2 and not b0);
    bb2 := (not b2 and b1 and b0) or (b2 and not b1 and b0) or (b2 and b1 and not b0) or (b3 and not b2 and not b1 and not b0) or (not b3 and b1 and b0);
    bb1 := (b2 and not b1) or (not b2 and b0);
    bb0 := (not b1 and b0) or (b1 and not b0);
    nextNum:=(bb0 and 1) or (bb1 and 2) or (bb2 and 4) or (bb3 and 8) or (bb4 and 16);
    b0:=bb0; b1:=bb1; b2:=bb2; b3:=bb3; b4:=bb4;
    Log:=Format('%d',[nextNum]);
  end;
end;

كتب foaad:

كتب sh_que_L:

فيكون مجموع الأصفار في الجهة اليمنى

Total=N0+N1+..+N31
Total=N/2+N/4+...N/(2^31)

بظن هي أفضل طريقة.

كتب rani_walhan:

اللغز هو توليد مجموعة من الارقام بشكل متسلسل علما ان الارقام ليست عشوائية ولكن يجب توليد الارقام باقل عدد من الحلقات التكرارية

<br />
16, 8, 4, 2, 1, 3, 6, 5, 7, 12,10,9,11, 14, 13, 15, 24, 20, 18, 17, 19, 22, 21, 23, 28, 26, 25, 27, 30,29, 31<br />

مجموعة منتهية؟!

<br />
int arr[] = {16, 8, 4, 2, 1, 3, 6, 5, 7, 12,10,9,11, 14, 13, 15, 24, 20, 18, 17, 19, 22, 21, 23, 28, 26, 25, 27, 30,29, 31}<br />

غير مقبول حلك

اهلا اخي

نعم يمكنك حلها بخرائط كارنو

فعليا انا قمت ببعثرة محتويات شجرة ثنائية بنظام معين

لو افترضنا انها شجرة ثنائية

و ال 16 هي الرأس

و اليسار هي 16 قسمة 2

و اليمين هي (الراس + اليسار ) قسمة 2

وطلعا يوجد لكل ابن لل 16 ابناء

لكن هذا ليس نفسه الترتيب الذي قمت بوضعه

لكن اعتقد ان الترتيب الحالي ممكن تحقيقه باستدعاء ذاتي

فعليا انا لم ابحث في كيفية حل المسالة حتى الآن

وربما لا يوجد حل لها

و تحية

B4 = b4 b3  + b4 b2  + b4 b1  + b4 b0 + b3 b2 b1 b0;
B3 = b3' b2 b1 b0 + b3' b2' b1' b0' + b3 b2' b1  + b4' b3 b0 + b3 b1' b0 + b3 b2 b0';
B2 = b2' b1 b0 + b2 b1' b0 + b2 b1 b0' + b3 b2' b1' b0' + b3' b1 b0;
B1 = b2 b1'  + b2' b0;
B0 = b1' b0 + b1 b0';

var
  i:integer;
  b0,b1,b2,b3,b4:byte;      //Previous value
  bb0,bb1,bb2,bb3,bb4:byte; //Calculated value
  nextNum:Byte;

  procedure extractBits(num:byte);
  begin
    b0:=((num shr 0) and 1)*255;
    b1:=((num shr 1) and 1)*255;
    b2:=((num shr 2) and 1)*255;
    b3:=((num shr 3) and 1)*255;
    b4:=((num shr 4) and 1)*255;
  end;
begin
  extractBits(31);//Start with the last value

  for i := 0 to Length(Nums)-1 do
  begin
    bb4 := (b4 and b3) or (b4 and b2) or (b4 and b1) or (b4 and b0) or (b3 and b2 and b1 and b0);
    bb3 := (not b3 and b2 and b1 and b0) or (not b3 and not b2 and not b1 and not b0) or (b3 and not b2 and b1) or (not b4 and b3 and b0) or (b3 and not b1 and b0) or (b3 and b2 and not b0);
    bb2 := (not b2 and b1 and b0) or (b2 and not b1 and b0) or (b2 and b1 and not b0) or (b3 and not b2 and not b1 and not b0) or (not b3 and b1 and b0);
    bb1 := (b2 and not b1) or (not b2 and b0);
    bb0 := (not b1 and b0) or (b1 and not b0);
    nextNum:=(bb0 and 1) or (bb1 and 2) or (bb2 and 4) or (bb3 and 8) or (bb4 and 16);
    b0:=bb0; b1:=bb1; b2:=bb2; b3:=bb3; b4:=bb4;
    Log:=Format('%d',[nextNum]);
  end;
end;

هل يمكن استبدال AND و OR بـ XOR فقط؟

اذا كان يحل المسألة نعم يمكن

لكن اعتقد ان المسألة تحل بشكل افضل عن طريق الاستدعاء الذاتي

انظر معي

لو افترضنا وجود استدعاء ذاتي

بحيث

</p>
<p>f(16)<br />
{</p>
<p>gives f(8)// 16/2</p>
<p>gives f(12) // 12 = 16/2 + 8 /2<br />
}</p>
<p>اذن</p>
<p>f(x)<br />
{<br />
y = x /2 ;<br />
print y<br />
f(y)</p>
<p>z = (y+x) /2</p>
<p>print z<br />
f(z)<br />

مساء الخير

ما زلت اعتقد بامكانية توليد السلسلة بالاستدعاء الذاتي

قمت بكتابة كود لتوليد السلسلة لكن ما زال يوجد اخطاء

السلسلة التي ولدها الكود

</p>
<p>32 16 8 4 2 1 3 6 8 6 5 7 12 16 12 10 9 11 14 16 14 13 15 24 32 24 20 18 17 19 22 24 22 21 23 28 32 28 26 25 27 30 32 30 29 31<br />

الكود قمت بكتابته بالسي++

[code]

#include
#include

using namespace std;

void rec(int x, int y)
{
int w;
int z;
cout <