الإزاحة الحسابية

الموسوعة الحرة
إزاحة حسابية لليمين لرقم ثنائي بمقدار 1. يتم ملء الموضع الفارغ في البت الأكثر أهمية بنسخة من البت الأكثر أهمية الأصلي.
إزاحة حسابية لليسار لرقم ثنائي بمقدار 1. يتم ملء الموضع الفارغ في البت الأقل أهمية بصفر.
عوامل الإزاحة الحسابية في لغات البرمجة والمعالجات المختلفة
اللغة أو المعالجغادريمين
ActionScript 3، Java ، JavaScript ، Python ، PHP ، Ruby ، C ، C++ ، [ 1 ] D ، C# ، Go ، Julia ، Rust (الأنواع الموقعة فقط)، [ 2 ] Swift (الأنواع الموقعة فقط) [ ملاحظة 1 ] << >>
آدا Shift_Left [ 3 ] Shift_Right_Arithmetic
كوتلين shl shr
فورتران SHIFTL SHIFTA [ ملاحظة 2 ]
لغة الآلة القياسية << ~>>
فيريلوج <<< >>> [ ملاحظة 3 ]
لغة الماكرو في نظام التشغيل OpenVMS@ [ ملاحظة 4 ]
مخططarithmetic-shift[ ملاحظة 5 ]
لغة الشفرة الشائعةash
أوكاميلlslasr
هاسكلData.Bits.shift[ ملاحظة 6 ]
لغة VHDLsla[ ملاحظة 7 ]sra
التجميع: Z80SLA[ 5 ]SRA
التجميع: x86SALSAR
التجميع: 68 ألفASLASR
التجميع: RISC-Vsll, slli[ 6 ]sra،srai

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

يفضل بعض المؤلفين استخدام مصطلحي "الإزاحة اليمنى الثابتة" و "الإزاحة اليمنى مع ملء الأصفار" للإزاحات الحسابية والمنطقية على التوالي. [ 7 ]

تُعدّ الإزاحات الحسابية وسيلة فعّالة لإجراء عمليات الضرب أو القسمة للأعداد الصحيحة الموقّعة على قوى العدد اثنين. فإزاحة عدد ثنائي موقّع أو غير موقّع بمقدار n بت إلى اليسار تُؤدي إلى ضربه في 2^ n . أما إزاحة عدد ثنائي موقّع ممثّل بنظام المتمم الثنائي بمقدار n بت إلى اليمين فتُؤدي إلى قسمته على 2^ n ، ولكن مع تقريب الناتج دائمًا إلى الأسفل (نحو سالب ما لا نهاية). وهذا يختلف عن طريقة التقريب المعتادة في قسمة الأعداد الصحيحة الموقّعة (التي تُقرّب نحو الصفر). وقد أدّى هذا التباين إلى ظهور أخطاء في عدد من المترجمات البرمجية. [ 8 ]

على سبيل المثال، في مجموعة تعليمات x86 ، تقوم تعليمة SAR (الإزاحة الحسابية لليمين) بقسمة عدد صحيح على قوة من قوى العدد اثنين ، مع تقريب الناتج إلى سالب ما لا نهاية. [ 9 ] في المقابل، تقوم تعليمة IDIV (القسمة على عدد صحيح) بقسمة عدد صحيح على قوة من قوى العدد اثنين، مع تقريب الناتج إلى الصفر. لذا، لا يمكن استبدال تعليمة SAR بتعليمة IDIV باستخدام قوة من قوى العدد اثنين، ولا العكس.

التعريف الرسمي

التعريف الرسمي للإزاحة الحسابية، وفقًا للمعيار الفيدرالي 1037C، هو أنها:

الإزاحة هي عملية تُطبق على تمثيل عدد في نظام ترقيم ذي أساس ثابت ونظام تمثيل ذي فاصلة ثابتة ، حيث تُنقل فقط الأحرف التي تُمثل الجزء ذي الفاصلة الثابتة من العدد. عادةً ما تُعادل الإزاحة الحسابية ضرب العدد في قوة صحيحة موجبة أو سالبة للأساس، باستثناء تأثير التقريب. قارن الإزاحة المنطقية بالإزاحة الحسابية، خاصةً في حالة تمثيل الأعداد العشرية .

كلمة مهمة في تعريف FS 1073C هي "عادةً".

عدم تكافؤ الإزاحة الحسابية إلى اليمين والقسمة

مع ذلك، تُعدّ عمليات الإزاحة الحسابية إلى اليمين فخًا كبيرًا لمن لا يُحسن التعامل مع الأرقام، لا سيما عند تقريب الأعداد الصحيحة السالبة. على سبيل المثال، في تمثيل المتمم الثنائي المعتاد للأعداد الصحيحة السالبة، يُكتب العدد -1 على هيئة جميع الآحاد. بالنسبة لعدد صحيح مُوقّع ذي 8 بتات، يكون هذا العدد 1111  1111. تُنتج عملية الإزاحة الحسابية إلى اليمين بمقدار 1 (أو 2، 3، ...، 7) العدد 1111  1111 مرة أخرى، وهو ما يزال -1. يُقابل هذا التقريب إلى الأسفل (باتجاه سالب ما لا نهاية)، ولكنه ليس الاصطلاح المعتاد للقسمة.

كثيرًا ما يُقال إن الإزاحة الحسابية لليمين تُعادل القسمة على قوة (موجبة وصحيحة) للأساس (مثل القسمة على قوة 2 للأعداد الثنائية)، وبالتالي يمكن تحسين القسمة على قوة الأساس بتنفيذها كإزاحة حسابية لليمين. (المُزاحة أبسط بكثير من القسمة. في معظم المعالجات، تُنفذ تعليمات الإزاحة أسرع من تعليمات القسمة). يحتوي عدد كبير من كتيبات البرمجة والأدلة والمواصفات الأخرى الصادرة في الستينيات والسبعينيات من القرن الماضي عن شركات ومؤسسات مثل DEC و IBM و Data General و ANSI على مثل هذه التصريحات غير الصحيحة [ 10 ] .

الإزاحة المنطقية لليمين تُعادل القسمة على قوة من قوى الأساس (عادةً 2) فقط للأعداد الموجبة أو غير الموقعة. أما الإزاحة الحسابية لليمين فتُعادل الإزاحة المنطقية لليمين للأعداد الموجبة الموقعة. وتُعادل الإزاحة الحسابية لليمين للأعداد السالبة في نظام المتمم N (عادةً المتمم الثنائي ) القسمة على قوة من قوى الأساس (عادةً 2)، حيث يتم تقريب العدد الفردي إلى الأسفل (وليس نحو الصفر كما هو متوقع عادةً).

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

معالجة المشكلة في لغات البرمجة

يُعرّف معيار ISO (1999) للغة البرمجة C عامل الإزاحة إلى اليمين بدلالة القسمة على قوى العدد 2. [ 11 ] ونظرًا لعدم التكافؤ المذكور أعلاه، يستثني المعيار صراحةً من هذا التعريف عمليات الإزاحة إلى اليمين للأعداد الموقعة ذات القيم السالبة. ولا يُحدد المعيار سلوك عامل الإزاحة إلى اليمين في مثل هذه الحالات، بل يُلزم كل مُصرّف للغة C بتحديد سلوك إزاحة القيم السالبة إلى اليمين. [ ملاحظة 8 ]

كما هو الحال في لغة C، كانت لغة C++ تحتوي على إزاحة يمين محددة التنفيذ للأعداد الصحيحة الموقعة حتى إصدار C++20 . بدءًا من معيار C++20، تُعرَّف إزاحة اليمين لعدد صحيح موقع على أنها إزاحة حسابية. [ 13 ]

التطبيقات

في التطبيقات التي تتطلب تقريبًا ثابتًا للأسفل، تُعدّ عمليات الإزاحة الحسابية لليمين للقيم الموجبة مفيدة. ومن الأمثلة على ذلك تصغير إحداثيات الصور النقطية بمقدار قوة العدد اثنين، مما يحافظ على تباعد متساوٍ. على سبيل المثال، يؤدي الإزاحة إلى اليمين بمقدار 1 إلى تحويل الأرقام 0، 1، 2، 3، 4، 5، ... إلى 0، 0، 1، 1، 2، 2، ...، والأرقام −1، −2، −3، −4، ... إلى −1، −1، −2، −2، ...، مع الحفاظ على تباعد منتظم كما هو الحال −2، −2، −1، −1، 0، 0، 1، 1، 2، 2، ... في المقابل، تؤدي القسمة الصحيحة مع التقريب نحو الصفر إلى تحويل الأرقام −1، 0، و1 جميعها إلى 0 (3 نقاط بدلاً من 2)، مما ينتج عنه −2، −1، −1، 0، 0، 0، 1، 1، 2، 2، ... بدلاً من ذلك، وهو عدد غير منتظم عند الصفر.

انظر أيضاً

ملحوظات

  1. ↑ لا يُعدّ عامل >> الإزاحة في لغتي C و C++ بالضرورة إزاحة حسابية. عادةً ما يكون إزاحة حسابية فقط عند استخدامه مع عدد صحيح مُوَقَّع على جانبه الأيسر. أما عند استخدامه مع عدد صحيح غير مُوَقَّع، فسيكون إزاحة منطقية .
  2. ↑ فورتران 2008.
  3. ↑ لا يُجري عامل الإزاحة الحسابية لليمين في لغة فيريلوج عملية إزاحة حسابية إلا إذا كان المعامل الأول مُوقّعًا. أما إذا كان المعامل الأول غير مُوقّع، فإن العامل يُجري عملية إزاحة منطقية لليمين.
  4. في لغة الماكرو الخاصة بنظام OpenVMS ، يُحدد اتجاه الإزاحة الحسابية (يسارًا أو يمينًا ) بناءً على ما إذا كان المعامل الثاني موجبًا أم سالبًا. وهذا أمر غير معتاد. ففي معظم لغات البرمجة، لكل اتجاه مُعامل خاص به، حيث يُحدد المُعامل الاتجاه، ويكون المعامل الثاني موجبًا ضمنيًا. (تتطلب بعض اللغات، مثل Verilog، تحويل القيم السالبة إلى قيم موجبة غير مُوقّعة. بينما لا تُحدد بعض اللغات الأخرى، مثل C وC++، سلوكًا مُعينًا عند استخدام القيم السالبة.) [ 4 ]
  5. ↑ في لغة Scheme،arithmetic-shiftيمكن أن يكون الإزاحة لليسار واليمين، اعتمادًا على المعامل الثاني، وهو مشابه جدًا للغة الماكرو OpenVMS، على الرغم من أن R6RS Scheme يضيف كلا النوعين-rightوالمتغيرات-left.
  6. ↑ يُعرّف الصنف من وحدة Haskell كلاً منالدالةBitsالتيتقبل وسيطًا مُوقّعًاوالدالةالتي تقبل وسيطًا غير مُوقّع. وهما متماثلان ؛ فلكي يُعرّف المبرمج تعريفًا جديدًا، يكفيه تحديد أحد الشكلين، وسيُعرّف الشكل الآخر تلقائيًا بناءً على الشكل المُقدّم.Data.BitsshiftshiftLshiftR
  7. ↑ يُعدّ عامل الإزاحة الحسابية لليسار في لغة VHDL غير مألوف. فبدلاً من ملء خانة البت الأقل أهمية (LSB) للنتيجة بالأصفار، يقوم بنسخ خانة البت الأقل أهمية الأصلية إلى خانة البت الأقل أهمية الجديدة. ورغم أن هذا يُطابق تمامًا الإزاحة الحسابية لليمين، إلا أنه ليس التعريف التقليدي لهذا العامل، ولا يُعادل الضرب في قوة من قوى العدد 2. في معيار VHDL 2008، تُرك هذا السلوك الغريب دون تغيير (للتوافق مع الإصدارات السابقة) لأنواع الوسائط التي لا تخضع لتفسير عددي إجباري (مثل BIT_VECTOR)، بينما يتصرف عامل الإزاحة المنطقية لليسار (SLA) لأنواع الوسائط غير الموقعة والموقعةبالطريقة المتوقعة (أي، تُملأ الخانات الموجودة في أقصى اليمين بالأصفار). وتُنفّذ دالة الإزاحة المنطقية لليسار (SLL) في لغة VHDL الإزاحة الحسابية "القياسية" المذكورة آنفًا.
  8. ↑ كان الهدف من معيار لغة C هو عدم حصرها في بنية المتمم الأحادي أو المتمم الثنائي. في الحالات التي يختلف فيها سلوك تمثيلات المتمم الأحادي والمتمم الثنائي، كما هو الحال هنا، يُلزم المعيار مُجمِّعات لغة C بتوثيق سلوك بنيتها المستهدفة. على سبيل المثال، تُوثِّق وثائق مجموعة مُجمِّعات GNU (GCC) سلوكها باستخدام تمديد الإشارة. [ 12 ]

مراجع

الإحالة المرجعية

  1. ↑ "التلاعب بالبتات - جولة في لغة Dlang" . tour.dlang.org . تم الاطلاع عليه بتاريخ 23-06-2019 .
  2. ↑ "تعبيرات المعاملات: المعاملات الثنائية الحسابية والمنطقية" . doc.rust-lang.org . تم الاطلاع عليه بتاريخ 13-11-2022 .
  3. ↑ "دليل مرجعي مشروح لـ Ada 2012" .
  4. ↑ HP 2001 .
  5. ↑ "بنية لغة التجميع Z80" .
  6. ↑ "دليل مجموعة تعليمات RISC-V، المجلد الأول: مجموعة تعليمات غير مميزة" (ملف PDF) . GitHub . 13 ديسمبر 2019. الصفحات 18-20 . مؤرشف (PDF) من الأصل بتاريخ 9 أكتوبر 2022. تم الاطلاع عليه بتاريخ 7 أغسطس 2021 . 
  7. ↑ توماس ر. كاين وآلان ت. شيرمان. "كيفية كسر شيفرة جيفورد" . القسم 8.1: "إزاحة البتات اللاصقة مقابل إزاحة البتات غير اللاصقة". كريبتولوجيا. 1997.
  8. ↑ ستيل، جاي الابن. "يُعتبر الإزاحة الحسابية ضارة" (ملف PDF) . مختبر الذكاء الاصطناعي بمعهد ماساتشوستس للتكنولوجيا. مؤرشف (ملف PDF) من الأصل بتاريخ 9 أكتوبر 2022. تم الاطلاع عليه بتاريخ 20 مايو 2013 .
  9. ↑ هايد 1996 ، § 6.6.2.2 SAR.
  10. ↑ ستيل 1977 .
  11. ↑ ISOIEC9899 1999 ، § 6.5.7 عوامل الإزاحة على مستوى البت.
  12. ↑ FSF 2008 ، § 4.5 تنفيذ الأعداد الصحيحة.
  13. ↑ ISOCPP20 2020 ، § 7.6.7 مشغلو الورديات.

المصادر المستخدمة

المجال العام تتضمن هذه المقالة موادًا متاحة للعموم من المعيار الفيدرالي 1037C ، إدارة الخدمات العامة . مؤرشفة من الأصل بتاريخ 22 يناير 2022.