تدوير البتات

تدوير البتات Bit Rotation (أو الإزاحة الدائرية circular shift) هي عملية مشابهة لإزاحة البتات باستثناء أنّ البتات التي تخرج من أحد الأطراف تعود مرة أخرى من الطرف الآخر.

وهناك نوعان من عمليات التدوير هما:

1. التدوير اليساري: تعود البتات التي تقع من الجانب الأيسر إلى الجانب الأيمن من العدد الثنائي.
2. التدوير اليميني: تعود البتات التي تقع من الجانب الأيمن إلى الجانب الأيسر من العدد الثنائي.

مثال:

ليكن n عددًا مؤلّفًا من 8 بتات n = 11100101. تؤدي الإزاحة اليسارية بمقدار 3 مواقع إلى الحصول على قيمة جديدة هي n = 00101111 (أزيحت البتات إلى اليسار بمقدار 3 مواقع وأرجعت البتات في نهاية العدد الثنائي إلى بدايته). إن كان n عددًا مؤلّفًا من 16 بت أو 32 بت فإنّ الإزاحة اليسارية ستؤدي إلى تحويل العدد (‎000...11100101‎) إلى (‎00..0011100101000‎).

ليكن n عددًا مؤلّفًا من 8 بتات n = 11100101. تؤدي الإزاحة اليمينية بمقدار 3 مواقع إلى الحصول على قيمة جديدة هي n = 10111100 (أزيحت البتات إلى اليمين بمقدار 3 مواقع وأرجعت البتات في نهاية العدد الثنائي إلى بدايته). إن كان n عددًا مؤلّفًا من 16 بت أو 32 بت فإنّ الإزاحة اليمينية ستؤدي إلى تحويل العدد (‎000...11100101‎) إلى (‎101000.0011100‎).

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include<iostream> 

using namespace std; 
#define INT_BITS 32 
class gfg 
{ 
	
/* دالة التدوير اليساري */
public: 
int leftRotate(int n, unsigned int d) 
{ 
	/* بعد إزاحة المقدار المعطى من البتات
	تصبح البتات الأخيرة أصفارًا. ولإرجاع البتات الأولى
	إلى نهاية العدد الثنائي يستخدم عامل "أو الثنائي" */
	return (n << d)|(n >> (INT_BITS - d)); 
} 

/* دالة التدوير اليميني */
int rightRotate(int n, unsigned int d) 
{ 
	/* بعد إزاحة المقدار المعطى من البتات
	تصبح البتات الأخيرة أصفارًا. ولإرجاع البتات الأولى
	إلى نهاية العدد الثنائي يستخدم عامل "أو الثنائي" */
	return (n >> d)|(n << (INT_BITS - d)); 
} 
}; 

/* اختبار الدالتين السابقتين */
int main() 
{ 
	gfg g; 
	int n = 16; 
	int d = 2; 
	cout << "Left Rotation of " << n << 
			" by " << d << " is "; 
	cout << g.leftRotate(n, d); 
	cout << "\nRight Rotation of " << n << 
			" by " << d << " is "; 
	cout << g.rightRotate(n, d); 
	getchar(); 
}

• بايثون:

INT_BITS = 32

# دالة التدوير اليساري 
def leftRotate(n, d): 

	# بعد إزاحة المقدار المعطى من البتات
	# تصبح البتات الأخيرة أصفارًا. ولإرجاع البتات الأولى
	# إلى نهاية العدد الثنائي يستخدم عامل "أو الثنائي"
	return (n << d)|(n >> (INT_BITS - d)) 

# دالة التدوير اليميني 
def rightRotate(n, d): 

	# بعد إزاحة المقدار المعطى من البتات
	# تصبح البتات الأخيرة أصفارًا. ولإرجاع البتات الأولى
	# إلى نهاية العدد الثنائي يستخدم عامل "أو الثنائي"
	return (n >> d)|(n << (INT_BITS - d)) & 0xFFFFFFFF

# اختبار الدالتين السابقتين
n = 16
d = 2

print("Left Rotation of",n,"by"
	,d,"is",end=" ") 
print(leftRotate(n, d)) 

print("Right Rotation of",n,"by"
	,d,"is",end=" ") 
print(rightRotate(n, d))

• جافا:

class GFG 
{ 
static final int INT_BITS = 32; 

/*دالة التدوير اليساري*/
static int leftRotate(int n, int d) { 
	
	/* بعد إزاحة المقدار المعطى من البتات
	تصبح البتات الأخيرة أصفارًا. ولإرجاع البتات الأولى
	إلى نهاية العدد الثنائي يستخدم عامل "أو الثنائي" */
	return (n << d) | (n >> (INT_BITS - d)); 
} 

/*دالة التدوير اليميني*/
static int rightRotate(int n, int d) { 
	
	/* بعد إزاحة المقدار المعطى من البتات
	تصبح البتات الأخيرة أصفارًا. ولإرجاع البتات الأولى
	إلى نهاية العدد الثنائي يستخدم عامل "أو الثنائي" */
	return (n >> d) | (n << (INT_BITS - d)); 
} 

// اختبار التابعين السابقين
public static void main(String arg[]) 
{ 
	int n = 16; 
	int d = 2; 
	System.out.print("Left Rotation of " + n + 
						" by " + d + " is "); 
	System.out.print(leftRotate(n, d)); 
	
	System.out.print("\nRight Rotation of " + n + 
							" by " + d + " is "); 
	System.out.print(rightRotate(n, d)); 
} 
}

مصادر

• صفحة Rotate bits of a number في توثيق الخوارزميات في موقع GeeksforGeeks.