نوبة عمل دائرية

مصفوفات من 8 عناصر إزاحات دائرية إلى اليسار واليمين

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

${\displaystyle \sigma (i)\equiv (i+1)}$modulo n ، لجميع المدخلات i = 1، ...، n

أو

${\displaystyle \sigma (i)\equiv (i-1)}$modulo n ، لجميع المدخلات i = 1، ...، n .

وتسمى نتيجة تطبيق عمليات الإزاحة الدائرية بشكل متكرر على مجموعة معينة أيضًا بالإزاحات الدائرية للمجموعة.

على سبيل المثال، يؤدي تطبيق الإزاحات الدائرية بشكل متكرر على الرباعية ( أ ، ب ، ج ، د ) تباعًا إلى

• ( د ، أ ، ب ، ج )،
• ( ج ، د ، أ ، ب )،
• ( ب ، ج ، د ، أ )،
• ( أ ، ب ، ج ، د ) (الرباعية الأصلية)،

ثم يتكرر التسلسل؛ لذا، يحتوي هذا الرباعي على أربعة تحولات دائرية مميزة. مع ذلك، لا تحتوي جميع الرباعيات المكونة من n عنصرًا على n تحولًا دائريًا مميزًا. على سبيل المثال، يحتوي الرباعي ( a , b , a , b ) على تحولين دائريين مميزين فقط. عدد التحولات الدائرية المميزة للرباعي المكون من n عنصرًا هو${\displaystyle {\frac {n}{k}}}$، حيث k هو قاسم لـ n ، مما يشير إلى الحد الأقصى لعدد التكرارات على جميع الأنماط الفرعية.

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

تُستخدم عمليات الإزاحة الدائرية بكثرة في علم التشفير لتبديل تسلسلات البتات. لسوء الحظ، تفتقر العديد من لغات البرمجة، بما فيها لغة C ، إلى عوامل أو دوال قياسية للإزاحة الدائرية، على الرغم من أن جميع المعالجات تقريبًا تحتوي على تعليمات عمليات بتية لهذا الغرض (مثل معالجات Intel x86 التي تحتوي على تعليمات ROL (تدوير لليسار) وROR (تدوير لليمين)). مع ذلك، قد توفر بعض المترجمات إمكانية الوصول إلى تعليمات المعالج عبر دوال مضمنة . إضافةً إلى ذلك، قد تُحسِّن بعض البنى في كود ANSI C القياسي بواسطة المترجم إلى تعليمة "rotate" في لغة التجميع على وحدات المعالجة المركزية التي تحتوي على هذه التعليمة. تتعرف معظم مترجمات لغة C على هذا النمط، وتُترجمه إلى تعليمة تدوير واحدة بحجم 32 بت. ^{[ 1 ] [ 2 ]}

/* * عمليات الإزاحة في لغة C مُعرَّفة فقط لقيم الإزاحة التي * ليست سالبة وأصغر من sizeof(value) * CHAR_BIT. * القناع، المستخدم مع عملية AND المنطقية (&)، يمنع السلوك غير المُعرَّف * عندما يكون عدد الإزاحة 0 أو أكبر من أو يساوي عرض العدد الصحيح غير المُوقَّع. */#include <stdint.h>  // لـ uint32_t، للحصول على عمليات تدوير بعرض 32 بت، بغض النظر عن حجم int. #include <limits.h>  // لـ CHAR_BITuint32_t rotl32 ( uint32_t value , unsigned int count ) { const unsigned int mask = CHAR_BIT * sizeof ( value ) - 1 ; count &= mask ; return ( value << count ) | ( value >> ( - count & mask )); }uint32_t rotr32 ( uint32_t value , unsigned int count ) { const unsigned int mask = CHAR_BIT * sizeof ( value ) - 1 ; count &= mask ; return ( value >> count ) | ( value << ( - count & mask )); }

تم تطوير هذا التطبيق الآمن والمتوافق مع المترجم بواسطة جون ريغير ، ^{[ 3 ]} وتم تحسينه بشكل أكبر بواسطة بيتر كوردس. ^{[ 4 ] [ 5 ]}

غالباً ما تُرى نسخة أبسط عندما countيقتصر النطاق على 1 إلى 31 بت:

uint32_t rotl32 ( uint32_t value , unsigned int count ) { return ( value << count ) | ( value >> ( 32 - count )); }

هذه النسخة خطيرة لأنها إذا countكانت قيمة المتغير 0 أو 32، فإنها تطلب إزاحة 32 بت، وهو سلوك غير مُعرَّف في معيار لغة C. مع ذلك، فإنها تعمل في الغالب، لأن معظم المعالجات الدقيقة تُنفِّذ الإزاحة value >> 32إما بإزاحة 32 بت (مُنتجةً 0) أو بإزاحة 0 بت (مُنتجةً القيمة الأصلية value)، وكلا الإزاحتين تُنتج النتيجة الصحيحة في هذا التطبيق.

إذا تعرض تسلسل البتات 0001 0111 لإزاحة دائرية بمقدار موضع بت واحد... (انظر الصور أدناه)

إلى اليسار سينتج عنه: 0010 1110

إلى اليمين سينتج عنه: 1000 1011 .

إذا تم إخضاع تسلسل البتات 1001 0110 للعمليات التالية:

تُعدّ الشفرات الدورية نوعًا من شفرات الكتل، وتتميز بخاصية أن الإزاحة الدائرية لكلمة شفرة تُنتج دائمًا كلمة شفرة أخرى. وهذا ما يُبرر التعريف العام التالي: بالنسبة لسلسلة s على الأبجدية Σ ، لنرمز بـ shift ( s ) إلى مجموعة الإزاحات الدائرية لـ s ، وبالنسبة لمجموعة L من السلاسل، لنرمز بـ shift ( L ) إلى مجموعة جميع الإزاحات الدائرية للسلاسل في L. إذا كانت L شفرة دورية، فإن shift ( L ) ⊆ L ؛ وهذا شرط ضروري لكون L لغة دورية . وقد دُرست عملية shift ( L ) في نظرية اللغات الرسمية . على سبيل المثال، إذا كانت L لغة خالية من السياق ، فإن shift ( L ) تكون خالية من السياق أيضًا. ^{[ 6 ] [ 7 ]} كذلك، إذا وُصفت L بتعبير منتظم طوله n ، فإنه يوجد تعبير منتظم طوله O ( n³ ) يصف shift ( ^L ) . ^{[ 8 ]}

• ناقل الحركة البرميلي
• الدورة الدموية
• كلمة ليندون
• قلادة - شيء يشبه المجموعة المرتبة ولكن تعتبر الإزاحات الدائرية مكافئة له.