ابحث عن المجموعة الأولى

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
الموسوعة الحرة

في برمجيات وأجهزة الحاسوب، تُعرف عملية البحث عن أول بت مُفعّل ( ffs ) أو البحث عن أول بت واحد (find first one) بأنها عملية بتية تُعيد فهرس أو موضع أقل بت أهمية مُفعّل في الكلمة، بدءًا من موضع أقل بت أهمية. وتُعتبر عملية عدّ الأصفار اللاحقة ( ctz ) أو عدد الأصفار اللاحقة ( ntz ) عملية مُكافئة تقريبًا، حيث تحسب عدد البتات الصفرية التي تلي أقل بت أهمية (1). أما العملية المُكملة التي تُحدد فهرس أو موضع أكثر بت أهمية مُفعّل فهي اللوغاريتم الثنائي ( log₂) ، الذي يُحسب اللوغاريتم الثنائي ⌊log₂ (x)⌋ . [ 1 ] وترتبط هذه العملية ارتباطًا وثيقًا بعملية عدّ الأصفار البادئة ( clz ) أو عدد الأصفار البادئة ( nlz )، التي تحسب عدد البتات الصفرية التي تسبق أكثر بت أهمية (1). [ nb 1 ] هناك نوعان شائعان من find first set، تعريف POSIX الذي يبدأ فهرسة البتات من 1، [ 2 ] المسمى هنا ffs، والنوع الذي يبدأ فهرسة البتات من الصفر، وهو ما يعادل ctz وبالتالي سيتم تسميته بهذا الاسم.

توفر معظم بنى مجموعة تعليمات وحدة المعالجة المركزية الحديثة واحدة أو أكثر من هذه كعوامل تشغيل للأجهزة؛ وعادة ما يتم توفير محاكاة البرامج لأي منها غير متوفر، إما كوظائف مضمنة في المترجم أو في مكتبات النظام .

أمثلة

بافتراض وجود الكلمة التالية المكونة من 32 بت:

0000 0000 0000 0000 1000 0000 0000 1000

ستُعيد عملية حساب الأصفار اللاحقة القيمة 3، بينما ستُعيد عملية حساب الأصفار البادئة القيمة 16. وتعتمد عملية حساب الأصفار البادئة على حجم الكلمة: فإذا تم اقتطاع هذه الكلمة ذات 32 بت إلى كلمة ذات 16 بت، فإن عملية حساب الأصفار البادئة ستُعيد القيمة صفر. أما عملية البحث عن أول مجموعة فستُعيد القيمة 4، مما يُشير إلى الموضع الرابع من اليمين. واللوغاريتم المقتطع للأساس 2 هو 15.

وبالمثل، بالنظر إلى الكلمة التالية المكونة من 32 بت، فإن النفي الثنائي للكلمة المذكورة أعلاه هو:

1111 1111 1111 1111 0111 1111 1111 0111

ستُرجع عملية عد الآحاد اللاحقة 3، وستُرجع عملية عد الآحاد الأولى 16، وستُرجع عملية البحث عن أول صفر ffz 4.

إذا كانت الكلمة صفرًا (أي لا توجد بتات مُفعّلة)، فإنّ كلاً من دالتيّ "عدّ الأصفار البادئة" و"عدّ الأصفار اللاحقة" تُعيدان عدد البتات في الكلمة، بينما تُعيد دالة "ffs" القيمة صفرًا. وبشكل عام، تُعيد كلتا دالتيّ "find first set" (التي تعتمد على اللوغاريتم ذي الأساس 2 وتلك التي تعتمد على الصفر) نتيجة غير مُعرّفة للكلمة الصفرية.

دعم الأجهزة

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

منصةذاكرياسمعرض المعاملاتوصفعند تقديم الطلب إلى 0
معالجات ARM ( بنية ARMv5T وما بعدها ) باستثناء Cortex-M0/M0+/M1/M23clz [ 3 ]عد الأصفار البادئة32clz32
ARM ( معمارية ARMv8-A )clzعد الأصفار البادئة32، 64clzعرض المعامل
AVR32clz [ 4 ]عد الأصفار البادئة32clz32
دي إي سي ألفاctlz [ 5 ]عد الأصفار البادئة64clz64
cttz [ 5 ]عد الأصفار اللاحقة64ctz64
معالج Intel 80386 والإصدارات الأحدثbsf [ 6 ]مسح البت للأمام16، 32، 64ctzغير مُعرَّف؛ يُعيِّن علامة الصفر
bsr [ 6 ]المسح العكسي للبت16، 32، 64اللوغاريتم ذو الأساس 2غير مُعرَّف؛ يُعيِّن علامة الصفر
يدعم معالج x86 مؤشر كتلة الجسم 1 أو مؤشر كتلة الجسمlzcnt [ 7 ]عد الأصفار البادئة16، 32، 64clzعرض المعامل؛ يحدد علامة الحمل
يدعم معالج x86 مؤشر كتلة الجسم 1tzcnt [ 8 ]عد الأصفار اللاحقة16، 32، 64ctzعرض المعامل؛ يحدد علامة الحمل
إيتانيومclz [ 9 ]عد الأصفار البادئة64clz64
MIPS32/MIPS64clz [ 10 ] [ 11 ]عد الأصفار البادئة في الكلمة32، 64clzعرض المعامل
clo [ 10 ] [ 11 ]عدّ الآحاد الأولى في الكلمة32، 64كلوعرض المعامل
موتورولا 68020 وما بعدهاbfffo [ 12 ]ابحث عن أول عنصر في حقل البتاتاِعتِباطِيّاللوغاريتم ذو الأساس 2إزاحة الحقل + عرض الحقل
PDP-10jffoاقفز إذا وجدت أول واحد36clz0؛ لا توجد عملية (أي، القفز على قيمة غير صفرية)
باور / باور بي سي / باور آي إس إيهcntlz/cntlzw/cntlzd [ 13 ]عد الأصفار البادئة32، 64clzعرض المعامل
Power ISA 3.0 والإصدارات الأحدثcnttzw/cnttzd [ 14 ]عد الأصفار اللاحقة32، 64ctzعرض المعامل
RISC-V ("امتداد B")clz [ 15 ]عد الأصفار البادئة32، 64clzعرض المعامل
ctz [ 15 ]عد الأصفار اللاحقة32، 64ctzعرض المعامل
SPARC Oracle Architecture 2011 والإصدارات الأحدثlzcnt (مرادف: lzd) [ 16 ]عدد الأصفار البادئة64clz64
فاكسffs [ 17 ]ابحث عن المجموعة الأولى0–32ctzعرض المعامل؛ يضبط علامة الصفر
بنية IBM zflogr [ 18 ]ابحث عن العنصر الموجود في أقصى اليسار64clz64
vclz [ 18 ]عدد المتجهات - الأصفار البادئة8، 16، 32، 64clzعرض المعامل
vctz [ 18 ]عدد المتجهات والأصفار اللاحقة8، 16، 32، 64ctzعرض المعامل

في بعض منصات ألفا، تتم محاكاة CTLZ و CTTZ في البرامج.

دعم الأدوات والمكتبات

يقوم عدد من موردي المترجمات والمكتبات بتوفير وظائف المترجمات أو وظائف المكتبة لتنفيذ عمليات البحث عن المجموعة الأولى و/أو العمليات ذات الصلة، والتي يتم تنفيذها بشكل متكرر من حيث تعليمات الأجهزة المذكورة أعلاه:

الأدوات/المكتبةاسميكتبنوع (أنواع) الإدخالملحوظاتعند تقديم الطلب إلى 0
مكتبة C23 القياسية [ 19 ] [ 20 ]stdc_first_trailing_one[_uc,_us,_ui,_ul,_ull]stdc_trailing_zeros[_uc,_us,_ui,_ul,_ull]stdc_first_leading_one[_uc,_us,_ui,_ul,_ull]stdc_leading_zeros[_uc,_us,_ui,_ul,_ull]وظيفة المكتبةunsigned char, unsigned short, unsigned int, unsigned long, unsigned long longكما يتم توفير وظائف لـ zeroو .ones0 (مؤشر البت) عرض المعامل (العدد)
مكتبة C++20 القياسية [ 21 ] [ 22 ]bit_ceil bit_floorbit_widthcountl_zero countl_onecountr_zero countr_oneوظيفة المكتبةunsigned char, unsigned short, unsigned int, unsigned long, unsigned long long
مكتبة libc المتوافقة مع POSIX .1، مكتبة libc لنظام التشغيل 4.3BSD ، مكتبة libc لنظام التشغيل OS X 10.3 [ 2 ] [ 23 ]ffsوظيفة المكتبةعدد صحيحيتضمن مكتبة glibc . لا يوفر نظام POSIX نظام اللوغاريتم التكميلي ذو الأساس 2 / clz.0
FreeBSD 5.3 libc OS X 10.4 libc [ 23 ]ffslflsflslوظيفة المكتبةعدد صحيح، عدد طويلتقوم الدالة fls("find last set") بحساب (log base 2) + 1.0
FreeBSD 7.1 libc [ 24 ]ffsllflsllوظيفة المكتبةطويلاً جداً0
GCC 3.4.0 [ 25 ] [ 26 ] Clang 5.x [ 27 ] [ 28 ]__builtin_ffs[l,ll,imax]__builtin_clz[l,ll,imax]__builtin_ctz[l,ll,imax]الوظائف المدمجةعدد صحيح غير مُوقّع، عدد صحيح طويل غير مُوقّع، عدد صحيح طويل غير مُوقّع، uintmax_tتعتبر وثائق GCC النتيجة غير محددة clz و ctz على 0.0 (ffs)
فيجوال ستوديو 2005_BitScanForward[ 29 ] _BitScanReverse[ 30 ]وظائف المترجم الداخليةعدد صحيح طويل غير مُوقّع، عدد صحيح غير مُوقّع __int64قيمة إرجاع منفصلة للإشارة إلى عدم وجود مدخلاتغير محدد
فيجوال ستوديو 2008__lzcnt[ 31 ]المترجم الداخليunsigned short, unsigned int, unsigned __int64يعتمد على دعم الأجهزة لتعليمات lzcnt التي تم تقديمها في BMI1 أو ABM .عرض المعامل
فيجوال ستوديو 2012_arm_clz[ 32 ]المترجم الداخليعدد صحيح غير موقعيعتمد على دعم الأجهزة لتعليمات clz التي تم تقديمها في بنية ARMv5T وما بعدها .؟
مُترجم لغة C++ من إنتل_bit_scan_forward_bit_scan_reverse[ 33 ] [ 34 ]وظائف المترجم الداخليةعدد صحيحغير محدد
Nvidia CUDA [ 35 ]__clzالوظائف32 بت، 64 بتيؤدي التجميع إلى عدد أقل من التعليمات على سلسلة GeForce 40032
__ffs0
LLVMllvm.ctlz.*llvm.cttz.*[ 36 ]جوهري8، 16، 32، 64، 256لغة التجميع LLVMعرض المعامل، إذا كانت الوسيطة الثانية تساوي 0؛ غير مُعرَّف خلاف ذلك
GHC 7.10 (الأساس 4.8)، فيData.BitscountLeadingZeroscountTrailingZerosوظيفة المكتبةFiniteBits b => bلغة البرمجة هاسكلعرض المعامل
مكتبة Rust القياسية [ 37 ] [ 38 ] [ 39 ]highest_oneleading_zeroslowest_onetrailing_zerosطريقة المكتبةجميع أنواع الأعداد الصحيحة الأولية وأنواع الأعداد الصحيحة الأخرى مثلNonZero<T>highest_oneوهي lowest_oneليست مستقرة بعد.
زيج [ 40 ] [ 41 ]@clz@ctzوظيفة مدمجةعدد صحيح أو متجه

الخصائص والعلاقات

إذا رُقِّمت البتات بدءًا من 1 (وهو الاصطلاح المُستخدم في هذه المقالة)، فإن عمليتي عدّ الأصفار اللاحقة وإيجاد أول مجموعة ترتبطان بالعلاقة ctz( x ) = ffs( x ) - 1 (باستثناء حالة كون المُدخل صفرًا). أما إذا رُقِّمت البتات بدءًا من 0 ، فإن عمليتي عدّ الأصفار اللاحقة وإيجاد أول مجموعة متكافئتان تمامًا. وبمعرفة w بت لكل كلمة، يُمكن حساب اللوغاريتم 2 بسهولة من clz والعكس صحيح باستخدام العلاقة log 2 ( x ) = w - 1 - clz( x ) .

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

في المنصات التي تتميز بعملية لوغاريتمية فعالة من الدرجة الثانية مثل M68000، يمكن حساب ctz عن طريق:

ctz( x ) = log 2 ( x & −x )

حيث يرمز & إلى عملية AND الثنائية، و− x إلى المتمم الثنائي لـ x . يؤدي التعبير x & −x إلى مسح جميع البتات باستثناء البت الأقل أهمية (1) ، بحيث يكون البت الأكثر أهمية والبت الأقل أهمية (1) متطابقين.

في المنصات التي تتميز بعملية عد الأصفار البادئة الفعالة مثل ARM و PowerPC، يمكن حساب ffs عن طريق:

ffs( x ) = w − clz( x & −x ) .

وعلى العكس من ذلك، في الأجهزة التي لا تحتوي على عوامل تشغيل log 2 أو clz ، يمكن حساب clz باستخدام ctz ، وإن كان ذلك بشكل غير فعال:

clz = w − ctz(2 ⌈log 2 ( x )⌉ ) (والذي يعتمد على أن ctz تُرجع w للمدخل الصفري)

على المنصات التي تحتوي على عملية وزن هامينغ فعالة ( عدد السكان) مثل SPARC POPC[ 42 ] [ 43 ] أو BlackfinONES [ 44 ] يوجد ما يلي :

ctz( x ) = popcount(( x & −x ) − 1) , [ 45 ] [ 46 ] or ctz( x ) = popcount(~( x | −x )) ,
ffs( x ) = popcount( x ^ ~− x ) [ 42 ]
clz = 32 − popcount(2 ⌈log 2 ( x )⌉ − 1)

حيث يشير الرمز ^ إلى عملية XOR الثنائية، ويشير الرمز | إلى عملية OR الثنائية، ويشير الرمز ~ إلى عملية النفي الثنائية.

يمكن حساب المشكلة العكسية (بإعطاء i ، قم بإنتاج x بحيث يكون ctz( x ) = i ) باستخدام إزاحة لليسار ( 1 << i ).

يمكن توسيع نطاق خوارزمية البحث عن المجموعة الأولى والعمليات ذات الصلة لتشمل مصفوفات بتات كبيرة الحجم بطريقة مباشرة، وذلك بالبدء من أحد طرفي المصفوفة والمتابعة حتى الوصول إلى كلمة ليست جميع قيمها أصفارًا (مثل ffs و ctz و clz ) أو ليست جميع قيمها آحادًا (مثل ffz و clo و cto ). ويمكن تسريع هذه العملية باستخدام بنية بيانات شجرية تستخدم خرائط بتات بشكل متكرر لتتبع الكلمات غير الصفرية.

محاكاة البرمجيات

معظم وحدات المعالجة المركزية التي يعود تاريخها إلى أواخر ثمانينيات القرن الماضي وما بعدها تحتوي على مُعاملات بتية لعمليات ffs أو ما يُعادلها، لكن بعض الوحدات الحديثة، مثل بعض وحدات سلسلة ARM-Mx، لا تحتوي عليها. وبدلاً من مُعاملات الأجهزة لعمليات ffs وclz وctz، يُمكن للبرمجيات مُحاكاتها باستخدام عمليات الإزاحة، والحسابات الصحيحة، والمُعاملات البتية. توجد عدة طرق تعتمد على بنية وحدة المعالجة المركزية، وإلى حدٍ أقل، على دلالات لغة البرمجة وجودة توليد كود المُترجم. يُمكن وصف هذه الطرق بشكلٍ عام بأنها البحث الخطي ، والبحث الثنائي ، والبحث مع البحث في الجداول ، وضرب دي بروين ، وتحويل الفاصلة العائمة/استخراج الأس ، وطرق المُعاملات البتية (بدون تفرع) . توجد مُفاضلات بين وقت التنفيذ ومساحة التخزين، وكذلك بين قابلية النقل والكفاءة.

عادةً ما تكون عمليات المحاكاة البرمجية حتمية. فهي تُرجع نتيجة محددة لجميع قيم الإدخال؛ وعلى وجه الخصوص، تكون النتيجة لإدخال جميع البتات أصفارًا عادةً 0 بالنسبة لعملية ffs، وطول بتات المعامل بالنسبة للعمليات الأخرى.

إذا كان لدى المرء جهاز clz أو ما يعادله، فيمكن حساب ctz بكفاءة باستخدام عمليات البت، ولكن العكس ليس صحيحًا: فحساب clz ليس فعالًا في حالة عدم وجود عامل تشغيل للأجهزة.

2 ن

الدالة 2 ⌈log 2 (x)⌉ (تقريب إلى أقرب قوة للعدد اثنين) باستخدام عمليات الإزاحة وعمليات OR الثنائية [ 47 ] ليست فعالة في الحساب كما هو الحال في هذا المثال ذي 32 بت، بل إنها أقل كفاءة إذا كان لدينا معامل 64 بت أو 128 بت:

دالة pow2(x): إذا كانت x = 0، فأرجع قيمة غير صالحة // القيمة غير الصالحة محددة من قبل التنفيذ (ليست في [0,63]) x ← x - 1 لكل قيمة y في المجموعة {1، 2، 4، 8، 16}: x ← x | (x >> y) أرجع x + 1

يا إلهي

بما أن ffs = ctz + 1 (POSIX) أو ffs = ctz (التنفيذات الأخرى)، يمكن استخدام الخوارزميات المطبقة لـ ctz، مع خطوة نهائية محتملة تتمثل في إضافة 1 إلى النتيجة، وإرجاع 0 بدلاً من طول المعامل لإدخال جميع البتات الصفرية.

CTZ

الخوارزمية الأساسية هي حلقة تحسب الأصفار بدءًا من البت الأقل أهمية (LSB) حتى يتم مصادفة بت واحد (1):

دالة ctz1 (x) إذا كانت x = 0 تُرجع w t ← 1 r ← 0 بينما (س و ت) = 0 t ← t << 1 r ← r + 1 إرجاع r

تُنفذ هذه الخوارزمية O ( w ) من الوقت والعمليات، وهي غير عملية من الناحية العملية بسبب العدد الكبير من الفروع الشرطية.

يُستثنى من ذلك حالة توزيع المدخلات توزيعًا منتظمًا. في هذه الحالة، يمكننا الاعتماد على حقيقة أن نصف القيم المُعادة ستكون صفرًا، وربعها سيكون واحدًا، وهكذا. يبلغ متوسط ​​عدد تكرارات الحلقة لكل استدعاء دالة واحدًا، ويتم تنفيذ الخوارزمية في زمن O (1) في الحالة المتوسطة.

يمكن لجدول البحث أن يستبعد معظم الفروع:

table[1..2 n -1] = ctz(i) for i in 1..2 n -1 function ctz2 (x) if x = 0 return w r ← 0 بينما (x & (2 n −1)) ≠ 0 x ← x >> n r ← r + n أعد r + table[x & (2 n −1)]

المعامل n ثابت (عادةً 8) ويمثل مفاضلة بين الوقت والمساحة . يمكن أيضًا فك الحلقة بالكامل . ولكن كعملية بحث خطية، يظل هذا الأسلوب من رتبة O(n) بالنسبة لعدد البتات في المعامل.

إذا تم اختيار n = 4، فيمكن ترميز جدول 16 مدخلًا من 2 بت في ثابت واحد من 32 بت باستخدام تقنيات SIMD داخل السجل :

// ثنائي 00 01 00 10 00 01 00 11 00 01 00 10 00 01 00 xx الجدول ← 0x12131210 دالة ctz2a (x) إذا كانت x = 0 تُرجع w r ← 0 بينما (س & 15) = 0 x ← x >> 4 r ← r + 4 أعد r + ((table >> 2*(x & 15)) & 3);

تعتبر هذه التقنية عملية للغاية في تطبيقات مثل خوارزمية GCD الثنائية ، حيث يتم توزيع قيم x بشكل منتظم، لذلك لا تكون الحلقة التكرارية مطلوبة في 15/16 من الوقت، وتعاني من الحد الأدنى من عقوبة سوء التنبؤ بالتفرع .

يتطلب تنفيذ البحث الثنائي عددًا لوغاريتميًا من العمليات والفروع، كما هو الحال في هذا الإصدار 32 بت: [ 48 ] [ 49 ]

دالة ctz3 (x) إذا كانت x = 0 ، تُرجع 32 ن ← ٠ إذا كان (x & 0x0000FFFF) = 0: n ← n + 16، x ← x >> 16. إذا كان (x & 0x000000FF) = 0: n ← n + 8، x ← x >> 8. إذا كان (x & 0x0000000F) = 0: n ← n + 4، x ← x >> 4. إذا كان (x & 0x00000003) = 0: n ← n + 2، x ← x >> 2. إذا كان (x & 0x00000001) = 0: n ← n + 1 // أو ما يعادله، n ← n + 1 - (x & 1). أرجع n.

يمكن مساعدة هذه الخوارزمية بجدول أيضًا، وذلك باستبدال آخر 2 أو 3 عبارات if بجدول بحث مكون من 16 أو 256 مدخلًا باستخدام أقل البتات أهمية xكمؤشر.

كما هو مذكور في قسم  الخصائص والعلاقات ، إذا كان الجهاز يحتوي على عامل clz، فإن الطريقة الأكثر كفاءة لحساب ctz هي كالتالي:

دالة ctz4 (x) إذا كانت x = 0 تُرجع w // تعزل البت الأقل أهمية x ← x & −x أعد w − 1 − clz(x)

يمكن استخدام أسلوب مماثل للاستفادة من تعليمات عد السكان :

دالة ctz4a (x) إذا كانت x = 0 تُرجع w // تُنشئ قناعًا من البتات الأقل أهمية x ← x ^ (x − 1) أعد عدد السكان (س) - 1

تستخدم خوارزمية لـ ctz ذات 32 بت متتالية دي بروين لإنشاء دالة تجزئة مثالية دنيا تُزيل جميع التفرعات. [ 50 ] [ 51 ] تفترض هذه الخوارزمية أن نتيجة الضرب تُقتطع إلى 32 بت.

for i from 0 to 31: table[ 0x077CB531 << i >> 27 & 31 ] ← i // تم تهيئة table [0..31] function ctz5 (x) if x = 0 return 32 return table[((x & −x) * 0x077CB531) >> 27 & 31]

يُعزل التعبير (x & −x)مرة أخرى البت الأقل أهمية (1). وبالتالي، لا يتبقى سوى 32 كلمة ممكنة، والتي تُجرى عليها عملية الضرب غير المُوقّع وإزاحة التجزئة إلى الموضع الصحيح في الجدول. تكون هذه الخوارزمية خالية من التفرعات إذا لم تكن بحاجة إلى التعامل مع المدخلات الصفرية.

يمكن توسيع نطاق هذه التقنية لتشمل الكلمات ذات 64 بت. [ 52 ]

يستخدم أحد المتغيرات الثانوية التعبير (x & (x−1))لحساب قناع من n من الآحاد اللاحقة، كما هو الحال في طريقة popcount ، ومضاعف تجزئة مثالي أدنى مختلف. [ 52 ] وهذا يسمح بمشاركة جدول البحث مع تطبيق عد الأصفار البادئة .

يسمح هذا أيضًا بتنفيذ مطوي باستخدام عملية ضرب بنصف العرض. [ 53 ] بعد حساب القناع، يكفي إجراء عملية XOR ثنائية بين النصفين العلوي والسفلي لتحديد القناع الأصلي بشكل فريد. ينتج عن مُضاعِف مناسب دالة تجزئة مثالية دنيا يمكن فك تشفيرها باستخدام جدول بحث.

for i from 0 to 31: table[ ((0xffff0000 >> i) * 0x70a7) >> 11 & 31 ] ← 31 - i // تم تهيئة الجدول [0..31] function ctz5 (x) if x = 0 return 32 x ← x ^ (x - 1) x ← x ^ (x >> 16) return table[(x * 0x70a7) >> 11 & 31] // 0x70d3 يعمل أيضًا

يُعدّ هذا مفيدًا إذا وفّرت عملية الضرب الأضيق وقتًا أكبر من الوقت الذي تستغرقه عملية الطي. ويمكن أيضًا توسيع هذه التقنية لتشمل الكلمات ذات 64 بت، باستخدام مضاعفات 32 بت 0x783a9b23، 0x78291d9bأو 0x782c8d4f، أو 0x78291acf. [ 53 ]

CLZ

تفحص الخوارزمية التقليدية بتًا واحدًا في كل مرة بدءًا من البت الأكثر أهمية (MSB) حتى يتم العثور على بت غير صفري، كما هو موضح في هذا المثال. يتم تنفيذها في زمن O(n) حيث n هو طول البتات للمعامل، وهي ليست خوارزمية عملية للاستخدام العام.

دالة clz1 (x) إذا كانت x = 0 تُرجع w t ← 1 << (w - 1) r ← 0 بينما (س و ت) = 0 t ← t >> 1 r ← r + 1 إرجاع r

يُحسّن هذا الأسلوب التكراري المُطوّر الأسلوب السابق بفحص ثمانية بتات في كل مرة، ثم يستخدم جدول بحث مكون من 256 مدخلاً (2^ 8 ) للعثور على أول بايت غير صفري. مع ذلك، لا يزال هذا الأسلوب يتطلب زمن تنفيذ O(n).

دالة clz2 (x) إذا كانت x = 0 تُرجع w t ← 0xff << (w - 8) r ← 0 بينما (س و ت) = 0 t ← t >> 8 r ← r + 8 أعد r + table[x >> (w - 8 - r)]

يمكن للبحث الثنائي أن يقلل وقت التنفيذ إلى O(log 2 n):

دالة clz3 (x) إذا كانت x = 0 ، تُرجع 32 ن ← ٠ إذا كان (x & 0xFFFF0000) = 0: n ← n + 16، x ← x << 16. إذا كان (x & 0xFF000000) = 0: n ← n + 8، x ← x << 8. إذا كان (x & 0xF0000000) = 0: n ← n + 4، x ← x << 4. إذا كان (x & 0xC0000000) = 0: n ← n + 2، x ← x << 2. إذا كان (x & 0x80000000) = 0: n ← n + 1. أرجع n.

أسرع الطرق المحمولة لمحاكاة clz هي مزيج من البحث الثنائي والبحث في الجداول: يمكن للبحث في جدول 8 بت (2 ^8 = 256 مدخلًا بحجم بايت واحد) أن يحل محل الفروع الثلاثة الأخيرة في البحث الثنائي. تتطلب المعاملات ذات 64 بت فرعًا إضافيًا. يمكن استخدام بحث بعرض أكبر، لكن الحد الأقصى العملي لحجم الجدول محدود بحجم ذاكرة التخزين المؤقت للبيانات من المستوى الأول (L1) في المعالجات الحديثة. إن توفير فرع واحد يفوق بكثير زمن استجابة خطأ ذاكرة التخزين المؤقت L1 .

تعمل خوارزمية مشابهة لضرب دي بروين لـ CTZ مع CLZ، ولكن بدلاً من عزل البت الأكثر أهمية، فإنها تقرب إلى أقرب عدد صحيح من الشكل 2 n − 1 باستخدام عمليات الإزاحة وعمليات OR الثنائية: [ 54 ]

table[0..31] = {0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8، 12، 20، 28، 15، 17، 24، 7، 19، 27، 23، 6، 26، 5، 4، 31} دالة clz4 (x) لكل y في {1، 2، 4، 8، 16}: x ← x | (x >> y) إرجاع الجدول[((x * 0x07C4ACDD) >> 27) % 32]

بالنسبة للمعالجات ذات خطوط الأنابيب العميقة، مثل معالجات بريسكوت والمعالجات اللاحقة من إنتل، قد يكون من الأسرع استبدال الفروع بمعاملات AND و OR الثنائية (على الرغم من الحاجة إلى عدد أكبر من التعليمات) لتجنب عمليات مسح خط الأنابيب للفروع المتوقعة بشكل خاطئ (وهذه الأنواع من الفروع غير قابلة للتنبؤ بطبيعتها):

دالة clz5 (x) r = (x > 0xFFFF) << 4; x >>= r; q = (x > 0xFF ) << 3; x >>= q; r |= q; q = (x > 0xF ) << 2; x >>= q; r |= q; q = (x > 0x3 ) << 1; x >>= q; r |= q; r |= (x >> 1); أعد r؛

في المنصات التي توفر تحويلًا ماديًا للأعداد الصحيحة إلى أعداد عشرية، يمكن استخراج حقل الأس وطرحه من ثابت لحساب عدد الأصفار البادئة. يلزم إجراء تصحيحات لمراعاة أخطاء التقريب. [ 48 ] [ 55 ] قد يستغرق تحويل الأعداد العشرية وقتًا طويلاً. هذه الطريقة غير قابلة للنقل بشكل كبير، ولا يُنصح بها عادةً.

int x ; int r ; union { unsigned int u [ 2 ]; double d ; } t ;t.u [ LE ] = 0x43300000 ; // LE تساوي 1 لنظام الترتيب الصغير t.u [ ! LE ] = x ; t.d - = 4503599627370496.0 ; r = ( t.u [ LE ] >> 20 ) - 0x3FF ; // log2 r ++ ; // CLZ

التطبيقات

يمكن استخدام عملية عدّ الأصفار البادئة (clz) لتنفيذ عملية التطبيع بكفاءة ، حيث تُشفّر عددًا صحيحًا على الصورة m ×  2e  ، حيث يكون البت الأكثر أهمية في m في موضع معروف (مثل أعلى موضع). ويمكن استخدام هذه العملية بدورها لتنفيذ قسمة نيوتن-رافسون ، وتحويل الأعداد الصحيحة إلى أعداد عشرية في البرامج، وغيرها من التطبيقات. [ 48 ] [ 56 ]

يمكن استخدام عدّ الأصفار البادئة (clz) لحساب المسند 32 بت "x = y" (صفر إذا كان صحيحًا، وواحد إذا كان خاطئًا) عبر المتطابقة clz(x − y) >> 5 ، حيث ">>" هي إزاحة يمين غير مُوقّعة. [ 57 ] ويمكن استخدامه لإجراء عمليات بت أكثر تعقيدًا، مثل إيجاد أول سلسلة من n بتًا من 1. [ 58 ] يُعد التعبير 1 << (16 − clz(x − 1)/2) تخمينًا أوليًا فعالًا لحساب الجذر التربيعي لعدد صحيح 32 بت باستخدام طريقة نيوتن . [ 59 ] يمكن لـ CLZ تنفيذ كبت الأصفار بكفاءة ، وهي تقنية ضغط بيانات سريعة تُشفّر العدد الصحيح بعدد بايتات الأصفار البادئة مع البايتات غير الصفرية. [ 60 ] كما يمكنه توليد أعداد صحيحة موزعة أُسّيًا بكفاءة عن طريق أخذ clz لأعداد صحيحة عشوائية منتظمة . [ 48 ]    

يمكن استخدام اللوغاريتم ذي الأساس 2 للتنبؤ بما إذا كانت عملية الضرب ستحدث تجاوزًا، حيث أن ⌈log 2 (xy)⌉ ≤ ⌈log 2 (x)⌉ + ⌈log 2 (y)⌉ . [ 61 ]

يمكن استخدام عدّ الأصفار البادئة وعدّ الأصفار اللاحقة معًا لتنفيذ خوارزمية جوسبر للكشف عن الحلقات ، [ 62 ] والتي يمكنها إيجاد دورة دالة ذات مدى محدود باستخدام موارد محدودة. [ 49 ]

تستهلك خوارزمية القاسم المشترك الأكبر الثنائية دورات عديدة لإزالة الأصفار الزائدة؛ ويمكن استبدال ذلك بحساب عدد الأصفار الزائدة (ctz) متبوعًا بعملية إزاحة. وتظهر حلقة مماثلة في حسابات متتالية حبة البرد .

يمكن استخدام مصفوفة بتات لتنفيذ قائمة انتظار ذات أولوية . في هذا السياق، تُعدّ خوارزمية البحث عن المجموعة الأولى (ffs) مفيدة في تنفيذ عملية "السحب" أو "إخراج العنصر ذي الأولوية الأعلى" بكفاءة. يستخدم مُجدوِل الوقت الحقيقي في نواة لينكسsched_find_first_bit() هذه الخوارزمية داخليًا لهذا الغرض. [ 63 ]

تُقدّم عملية عدّ الأصفار اللاحقة حلاً أمثل بسيطاً لمسألة برج هانوي : تُرقّم الأقراص بدءاً من الصفر، وفي الخطوة k ، يُحرّك القرص رقم ctz( k ) إلى أقصر مسافة ممكنة إلى اليمين (مع الدوران يساراً عند الحاجة). كما يُمكنها توليد رمز غراي بأخذ كلمة عشوائية وقلب البت ctz( k ) في الخطوة k . [ 49 ]

انظر أيضاً

ملحوظات

  1. ↑ هذه العمليات الأربع لها أيضًا نسخ منفية (أقل شيوعًا بكثير):
    • إيجاد أول صفر ( ffz )، والذي يحدد فهرس بت الصفر الأقل أهمية؛
    • حساب عدد الآحاد اللاحقة ، والذي يحسب عدد البتات الآحاد التي تلي أقل بت صفر أهمية.
    • عد الآحاد الرائدة ، والذي يحسب عدد البتات الآحاد التي تسبق البت الصفر الأكثر أهمية؛
    • أوجد فهرس البت الصفري الأكثر أهمية، وهو نسخة معكوسة من اللوغاريتم الثنائي .
  2. قد يؤدي استخدام عمليات البت على كلمات آلة غير غير الموقعة إلى نتائج غير محددة.
خطأ في الاستشهاد: لم يتم استخدام مرجع معرف في قائمة باسم "NB1" في المحتوى (انظر صفحة المساعدة ).

مراجع

  1. ↑ أندرسون . أوجد اللوغاريتم الأساسي 2 لعدد صحيح مع تعيين البت الأكثر أهمية N في O(N) عملية (الطريقة الواضحة) .
  2. 1 2 "FFS(3)" . دليل مبرمج لينكس . أرشيفات نواة لينكس . تم الاسترجاع في 2012-01-02 .
  3. ↑ "مرجع تعليمات ARM > تعليمات معالجة البيانات العامة لـ ARM > CLZ" . دليل مُجمِّع ARM Developer Suite . ARM . تم الاسترجاع في 3 يناير 2012 .
  4. ↑ "وثيقة بنية AVR32" (ملف PDF) (إصدار CORP072610 ). شركة Atmel . 2011. 32000D–04/201. مؤرشفة من الأصل (ملف PDF) بتاريخ 25-10-2017 . تم الاطلاع عليها بتاريخ 22-10-2016 . 
  5. 1 2 دليل مرجعي لهندسة ألفا (PDF) . كومباك . 2002. الصفحات 4 - 32، 4 - 34. 
  6. 1 2 دليل مطوري البرامج لبنيتي Intel 64 و IA-32 . المجلد 2 أ . Intel . الصفحات 3-92–3-97 .  رقم الطلب 325383.
  7. ↑ دليل مبرمج معمارية AMD64، المجلد 3: تعليمات الأغراض العامة وتعليمات النظام (ملف PDF) . المجلد 3. شركة Advanced Micro Devices (AMD). 2011. الصفحات 204-205 . رقم المنشور 24594.  
  8. ↑ "دليل مبرمج معمارية AMD64، المجلد 3: تعليمات الأغراض العامة وتعليمات النظام" (ملف PDF) . تقنية AMD64 (الإصدار 3.28 ). شركة Advanced Micro Devices (AMD). سبتمبر 2019 [2013]. رقم المنشور 24594. مؤرشف (ملف PDF) من الأصل بتاريخ 30 سبتمبر 2019. تاريخ الاسترجاع: 2 يناير 2014 . 
  9. ↑ دليل مطوري برامج معمارية إنتل إيتانيوم. المجلد 3: مجموعة تعليمات إنتل إيتانيوم . المجلد 3. إنتل . 2010. الصفحات 3:38. مؤرشف من الأصل بتاريخ 26-06-2019.  
  10. ١ ٢ بنية MIPS للمبرمجين. المجلد الثاني-أ: مجموعة تعليمات MIPS32 (الإصدار 3.02 ). تقنيات MIPS . ٢٠١١. الصفحات ١٠١-١٠٢ . مؤرشف من الأصل بتاريخ ٧ نوفمبر ٢٠١٧. تم الاطلاع عليه بتاريخ ٤ يناير ٢٠١٢ .  
  11. ١ ٢ بنية MIPS للمبرمجين. المجلد الثاني-أ: مجموعة تعليمات MIPS64 (الإصدار 3.02 ). تقنيات MIPS . ٢٠١١. الصفحات ١٠٥، ١٠٧، ١٢٢، ١٢٣. مؤرشف من الأصل بتاريخ ٧ نوفمبر ٢٠١٧. تم الاطلاع عليه بتاريخ ٤ يناير ٢٠١٢ .  
  12. ↑ دليل مرجعي لمبرمج عائلة M68000 (يتضمن تعليمات CPU32) ( ملف PDF) (الطبعة الأولى ). موتورولا . 1992. الصفحات 4-43–4-45 . M68000PRM/AD. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 2019-12-08.  
  13. ↑ فراي، براد. "الفصل 3.3.11 تعليمات المنطق ذات النقطة الثابتة". كتاب هندسة باور بي سي (الإصدار 2.02 ). آي بي إم . ص 70.  
  14. ↑ "الفصل 3.3.13 تعليمات منطقية ذات نقطة ثابتة - الفصل 3.3.13.1 تعليمات منطقية ذات نقطة ثابتة 64 بت". Power ISA الإصدار 3.0B . IBM . الصفحات 95، 98. 
  15. 1 2 وولف، كليفورد (22-03-2019). "امتداد معالجة البتات "B" لـ RISC-V" (ملف PDF) . جيت هاب (مسودة) ( الإصدار 0.37) . تم الاطلاع عليه بتاريخ 09-01-2020 . 
  16. ↑ بنية أوراكل سبارك 2011. أوراكل . 2011.
  17. ↑ دليل مرجعي لهندسة VAX (ملف PDF) . شركة ديجيتال إكويبمنت (DEC). 1987. الصفحات 70-71 . مؤرشف (ملف PDF) من الأصل بتاريخ 29-09-2019 . تم الاطلاع عليه بتاريخ 09-01-2020 . 
  18. ١ ٢ ٣ " الفصل ٢٢. تعليمات الأعداد الصحيحة المتجهة". مبادئ تشغيل بنية IBM z (ملف PDF) ( الطبعة الحادية عشرة). IBM . مارس ٢٠١٥. الصفحات ٧-٢١٩–٢٢-١٠ . SA22-7832-10. مؤرشف من الأصل (ملف PDF) بتاريخ ٩ يناير ٢٠٢٠. تم الاطلاع عليه بتاريخ ١٠ يناير ٢٠٢٠ .  
  19. ^ مينيد، جان هايد؛ فيديك ، فريك (2024/02/22). تكنولوجيا المعلومات – لغات البرمجة – مسودة عمل C, N3220 (PDF) . آيزو/إيك. ص 305 – 308 . تم الاسترجاع بتاريخ 2025-08-07 . 
  20. ↑ "ملف رأس المكتبة القياسية <stdbit.h> (C23)" . cppreference.com . تم الاطلاع عليه بتاريخ 2025-08-07 .
  21. ↑ سميث، ريتشارد (2020-04-01). مسودة عمل N4861، معيار لغة البرمجة C++ (ملف PDF) . المنظمة الدولية للتوحيد القياسي /اللجنة الكهروتقنية الدولية. الصفحات 1150-1153 . تاريخ الاسترجاع: 2020-05-25 . 
  22. ↑ "رأس المكتبة القياسية <بت>" . cppreference.com . تم الاسترجاع في 25-05-2020 .
  23. 1 2 "FFS(3)" . مكتبة مطوري نظام التشغيل Mac OS X. شركة Apple، 19 أبريل 1994. تم الاطلاع عليه بتاريخ 4 يناير 2012 .
  24. ↑ "FFS(3)" . دليل وظائف مكتبة FreeBSD . مشروع FreeBSD . تم الاطلاع عليه بتاريخ 4 يناير 2012 .
  25. ↑ "وظائف أخرى مدمجة يوفرها GCC" . استخدام مجموعة مترجمات GNU (GCC) . مؤسسة البرمجيات الحرة. تم الاطلاع عليه بتاريخ 14 نوفمبر 2015 .
  26. ↑ "سجل تغييرات GCC 3.4.0" . GCC 3.4.0 . مؤسسة البرمجيات الحرة. تم الاطلاع عليه بتاريخ 14 نوفمبر 2015 .
  27. ↑ "امتدادات لغة Clang - الفصل: الدوال المدمجة" . فريق Clang . تم الاطلاع عليه بتاريخ 9 أبريل 2017. يدعم Clang عددًا من دوال المكتبة المدمجة بنفس صيغة GCC.
  28. ↑ "شفرة المصدر لـ Clang" . فريق LLVM، جامعة إلينوي في أوربانا-شامبين . تم الاطلاع عليه بتاريخ 9 أبريل 2017 .
  29. ↑ "_BitScanForward, _BitScanForward64" . Visual Studio 2008: Visual C++: Compiler Intrinsics . Microsoft . 2012-11-16 . تم الاطلاع عليه بتاريخ 2018-05-21 .
  30. ↑ "_BitScanReverse, _BitScanReverse64" . Visual Studio 2008: Visual C++: Compiler Intrinsics . Microsoft . 2012-11-16 . تم الاطلاع عليه بتاريخ 2018-05-21 .
  31. ↑ "__lzcnt16, __lzcnt, __lzcnt64" . Visual Studio 2008: Visual C++: Compiler Intrinsics . Microsoft . تم الاسترجاع في 3 يناير 2012 .
  32. ↑ "وظائف ARM الداخلية" . Visual Studio 2012: Visual C++: وظائف المترجم الداخلية . مايكروسوفت . 2012-08-20 . تم الاطلاع عليه بتاريخ 2022-05-09 .
  33. ↑ "دليل Intel Intrinsics" . Intel . تم الاطلاع عليه بتاريخ 2020-04-03 .
  34. ↑ مرجع وظائف Intel C++ Compiler لنظام Linux . Intel . 2006. ص 21. 
  35. ↑ دليل برمجة NVIDIA CUDA (ملف PDF) (الإصدار 3.0 ). NVIDIA . 2010. ص 92.  
  36. ↑ ""llvm.ctlz.*' Intrinsic, 'llvm.cttz.*' Intrinsic" . دليل مرجع لغة LLVM . بنية مُصرّف LLVM . تم الاطلاع عليه بتاريخ 23 فبراير 2016 .
  37. ↑ "i32 - Rust" . doc.rust-lang.org . تم الاطلاع عليه بتاريخ 18-11-2025 .
  38. ↑ "u32 - Rust" . doc.rust-lang.org . تم الاطلاع عليه بتاريخ 18-11-2025 .
  39. ↑ "NonZero in std::num - Rust" . doc.rust-lang.org . تم الاطلاع عليه بتاريخ 18-11-2025 .
  40. ↑ "الوثائق - لغة برمجة Zig" . ziglang.org . تم الاطلاع عليه بتاريخ 18-11-2025 .
  41. ↑ "الوثائق - لغة برمجة Zig" . ziglang.org . تم الاطلاع عليه بتاريخ 18-11-2025 .
  42. ١ ٢ شركة SPARC الدولية (١٩٩٢). "A.41: تعداد السكان. ملاحظة برمجية". دليل بنية SPARC: الإصدار ٩ (PDF) (الإصدار ٩ ). إنجلوود كليفس، نيو جيرسي، الولايات المتحدة الأمريكية: برنتيس هول . ٢٠٥ صفحة . ISBN   978-0-13-825001-0.
  43. ↑ وارن الابن، هنري س. (2013) [2002]. متعة المخترق ( الطبعة الثانية). أديسون ويسلي - بيرسون للتعليم، المحدودة. ISBN  978-0-321-84268-8. 0-321-84268-5.
  44. ↑ مرجع مجموعة تعليمات بلاكفين ( طبعة أولية). شركة أنالوج ديفايسز . 2001. الصفحات 8-24 . رقم القطعة 82-000410-14.  
  45. ↑ ديتز، هنري جوردون . "خوارزميات السحر التجميعي" . جامعة كنتاكي . مؤرشف من الأصل في 31-10-2019.
  46. ↑ إيزنبرغ، جيرد (2019-11-03) [2012]. "BitScan: فهرس LS1B حسب عدد النقاط" . ويكي برمجة الشطرنج (CPW) . مؤرشف من الأصل في 2020-01-09 . تم الاسترجاع في 2020-01-09 .
  47. ↑ أندرسون . قرّب الناتج إلى أقرب قوة أعلى للعدد 2 .
  48. 1 2 3 4 وارن . الفصل 5-3: عدّ الأصفار البادئة.
  49. 1 2 3 وارن . الفصل 5-4: عد الأصفار في نهاية العدد.
  50. ↑ ليسرسون، تشارلز إي .؛ بروكوب، هارالد ؛ راندال، كيث إتش. (7 يوليو 1998). "استخدام متواليات دي بروين لفهرسة الرقم 1 في كلمة حاسوبية" (ملف PDF) . مختبر علوم الحاسوب بمعهد ماساتشوستس للتكنولوجيا، كامبريدج، ماساتشوستس، الولايات المتحدة الأمريكية. مؤرشف (ملف PDF) من الأصل بتاريخ 9 يناير 2020. تم الاطلاع عليه بتاريخ 9 يناير 2020 .
  51. ↑ بوش، فيليب (1 مارس 2009) [21 فبراير 2009]. "كيفية حساب الأصفار اللاحقة" (ملف PDF) . مؤرشف (PDF) من الأصل بتاريخ 1 أغسطس 2016. تم الاطلاع عليه بتاريخ 9 يناير 2020 .
  52. 1 2 إيزنبرغ، جيرد (2019-11-03) [2012]. "BitScan: De Bruijn Multiplication" . ويكي برمجة الشطرنج (CPW) . مؤرشف من الأصل في 2020-01-09 . تم الاسترجاع في 2020-01-09 .
  53. 1 2 إيزنبرغ، جيرد (2019-11-03) [2012]. "BitScan: خدعة مات تايلور في الطي" . ويكي برمجة الشطرنج (CPW) . مؤرشف من الأصل في 2020-01-09 . تم الاسترجاع في 2026-04-17 .
  54. ↑ أندرسون . أوجد اللوغاريتم ذو الأساس 2 لعدد صحيح مكون من N بت في O(lg(N)) عملية مع الضرب والبحث .
  55. ↑ أندرسون . أوجد اللوغاريتم الصحيح للأساس 2 لعدد صحيح ذي عدد عشري IEEE مكون من 64 بت .
  56. ↑ سلوس، أندرو ن.؛ سايمز، دومينيك؛ رايت، كريس (2004). دليل مطوري أنظمة ARM لتصميم برمجيات النظام وتحسينها ( الطبعة الأولى). سان فرانسيسكو، كاليفورنيا، الولايات المتحدة الأمريكية: مورغان كوفمان . الصفحات 212-213 . ISBN   978-1-55860-874-0.
  57. ↑ وارن . الفصل 2-11: مسندات المقارنة.
  58. ↑ وارن . الفصل 6-2: إيجاد أول سلسلة من البتات المكونة من 1 بت بطول معين.
  59. ↑ وارن . الفصل 11-1: الجذر التربيعي للأعداد الصحيحة.
  60. ↑ شليغل، بنيامين؛ جيمولا، راينر؛ لينر، فولفغانغ [بالألمانية] (يونيو 2010). "ضغط الأعداد الصحيحة السريع باستخدام تعليمات SIMD". وقائع ورشة العمل الدولية السادسة حول إدارة البيانات على الأجهزة الجديدة . الصفحات 34-40 . CiteSeerX 10.1.1.230.6379 . doi : 10.1145/1869389.1869394 . ISBN   978-1-45030189-3. S2CID 7545142 . 
  61. ↑ وارن . الفصل 2-12: اكتشاف الفائض.
  62. ↑ جوسبر، بيل (أبريل 1995) [29 فبراير 1972]. بيكر، هنري جيفنز الابن (محرر). "كاشف الحلقات" . هاكميم (طبعة مُعاد كتابتها وتحويلها ). كامبريدج، ماساتشوستس، الولايات المتحدة الأمريكية: مختبر الذكاء الاصطناعي ، معهد ماساتشوستس للتكنولوجيا (MIT). مذكرة الذكاء الاصطناعي 239، البند 132. مؤرشف من الأصل في 8 أكتوبر 2019. تم الاسترجاع في 9 يناير 2020 . 
  63. ↑ آس، جوش (17 فبراير 2005). فهم مُجدول وحدة المعالجة المركزية في لينكس 2.6.8.1 (ملف PDF) . شركة سيليكون جرافيكس (SGI). صفحة 19. مؤرشف (ملف PDF) من الأصل بتاريخ 19 مايو 2017. تم الاطلاع عليه بتاريخ 9 يناير 2020 . 

للمزيد من القراءة