تبديل البتات في عدد معين

تبدّل هذه الخوارزمية بين موقعين (من الجانب الأيمن) في التمثيل البياني للعدد المعطى بشرط عدم حصول تداخل بين مجموعتي البتات، ثم تعيد النتيجة.

مثال:
المدخلات:

x = 47 (00101111)
p1 = 1 (البدء من البت الثاني من جهة اليمين)
p2 = 5 (البدء من البت السادس من جهة اليمين)
n = 3 (عدد البتات التي سيجري تبديلها)
المخرجات:
227 (11100011)

جرى تبديل ثلاثة بتات بدءًا من البت الثاني (من جهة اليمين) مع ثلاثة بتات بدءًا من البت السادس (من جهة اليمين).

مثال:

المدخلات:
x = 28 (11100)
p1 = 0 (البدء من البت الأول من جهة اليمين)
p2 = 3 (البدء من البت الرابع من جهة اليمين)
n = 2 (عدد البتات التي سيجري تبديلها)
المخرجات:
7 (00111)

خطوات الخوارزمية

المطلوب هو التبديل بين مجموعتين من البتات؛ لذا يمكن استخدام العامل XOR بنفس الطريقة التي يستخدم فيها هذا العامل للتبديل بين رقمين.

تتبع الخوارزمية الخطوات التالية:

1. تحريك جميع البتات في المجموعة الأولى إلى أقصى اليمين

set1 = (x >> p1) &((1U << n) - 1)

يعطي التعبير ‎(1U << n) - 1 عددًا يحتوي على آخر n من البتات المعينة وتكون بقية البتات أصفارًا. يستخدم العامل & في هذا التعبير لتحويل بقية البتات إلى أصفار.

1. تحريك جميع البتات في المجموعة الثانية إلى أقصى اليمين

set2 =  (x >> p2) & ((1U << n) - 1)

1. استخدام العامل XOR مع مجموعتي البتات

xor = (set1 ^ set2)

1. إرجاع البتات الناتجة من الخطوة السابقة إلى مواقعها الأصلية

xor = (xor << p1) | (xor << p2)

1. استخدام العامل XOR مع مجموعة البتات الناتجة من الخطوة 4 والعدد الأصلي ليجري التبديل بين المجموعتين.

result = x ^ xor

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

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

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

int swapBits(unsigned int x, unsigned int p1, 
			unsigned int p2, unsigned int n) 
{ 
	/* تحريك جميع البتات في المجموعة الأولى إلى أقصى اليمين */
	unsigned int set1 = (x >> p1) & ((1U << n) - 1); 

	/* تحريك جميع البتات في المجموعة الثانية إلى أقصى اليمين */
	unsigned int set2 = (x >> p2) & ((1U << n) - 1); 

	/* استخدام العامل XOR مع مجموعتي البتات */
	unsigned int Xor = (set1 ^ set2); 

	/* إرجاع البتات الناتجة من الخطوة السابقة إلى مواقعها الأصلية */
	Xor = (Xor << p1) | (Xor << p2); 

	/* استخدام العامل `XOR` مع مجموعة البتات الناتجة من الخطوة 4 والعدد الأصلي ليجري التبديل بين المجموعتين */
	unsigned int result = x ^ Xor; 

	return result; 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	int res = swapBits(28, 0, 3, 2); 
	cout << "Result = " << res; 
	return 0; 
}

• بايثون:

def swapBits(x,p1,p2,n): 

	# تحريك جميع البتات في المجموعة الأولى إلى أقصى اليمين 
	set1 = (x >> p1) & ((1<< n) - 1) 

	# تحريك جميع البتات في المجموعة الثانية إلى أقصى اليمين 
	set2 = (x >> p2) & ((1 << n) - 1) 

	# استخدام العامل XOR مع مجموعتي البتات
	xor = (set1 ^ set2) 

	# إرجاع البتات الناتجة من الخطوة السابقة إلى مواقعها الأصلية
	xor = (xor << p1) | (xor << p2) 

	# استخدام العامل `XOR` مع مجموعة البتات الناتجة من الخطوة 4 والعدد الأصلي ليجري التبديل بين المجموعتين
	result = x ^ xor 

	return result 
	
# اختبار الدالة السابقة

res =swapBits(28, 0, 3, 2) 
print("Result =",res)

• جافا:

class GFG { 
	
	static int swapBits(int x, int p1, int p2, int n) 
	{ 
		// تحريك جميع البتات في المجموعة الأولى إلى أقصى اليمين
		int set1 = (x >> p1) & ((1 << n) - 1); 
	
		// تحريك جميع البتات في المجموعة الثانية إلى أقصى اليمين
		int set2 = (x >> p2) & ((1 << n) - 1); 
	
		// استخدام العامل XOR مع مجموعتي البتات
		int xor = (set1 ^ set2); 
	
		// إرجاع البتات الناتجة من الخطوة السابقة إلى مواقعها الأصلية
		xor = (xor << p1) | (xor << p2); 
	
		// استخدام العامل `XOR` مع مجموعة البتات الناتجة من الخطوة 4 والعدد الأصلي ليجري التبديل بين المجموعتين 
		int result = x ^ xor; 
	
		return result; 
	} 
	
	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		int res = swapBits(28, 0, 3, 2); 
		System.out.println("Result = " + res); 
	} 
}

مصادر

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