Algorithms/add subtract no operator

يمكن إجراء عمليتي الجمع والطرح على الأعداد الصحيحة دون استخدام العوامل وذلك بالتعامل مع التمثيلات الثنائية لهذه الأعداد.

جمع رقمين دون استخدام العوامل

المطلوب في هذه المسألة هو كتابة دالة تعيد حاصل جمع العددين المعطيين بشرط عدم استخدام العوامل الحسابية المعروفة (‎+, ++, -, --, ...‎).

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

يمكن الحصول على حاصل جمع بتين بتطبيق العامل XOR (^) على البتين. ويمكن الحصول على بت الترحيل Carry bit بتطبيق العامل AND (&) على البتين.

تسمى هذه الطريقة بطريقة الجامع النصفي Half Adder، ويمكن توسيعها لتشمل الأعدا دالصحيحة، فإذا كان هناك عددان صحيحان x و y ولم يكن لهذين الرقمين بتات معينة في نفس المواقع، فإنّ تطبيق العامل XOR (^) سيعطي ناتج جمع العددين x و y. ويستخدم العامل AND (&) لإضافة البتات المعينة المشتركة كذلك. يؤدي تطبيق العامل AND الخاص بالأعداد الثنائي على العددين x و y إلى الحصول على جميع البتات المرحلة، فيمكن حينئذٍ حساب قيمة (x & y) وإزاحة الناتج بمقدار واحد وإضافته إلى x ^ y للحصول على الناتج المطلوب.

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

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

• C++‎:

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

int Add(int x, int y) 
{ 
	// تعمل الحلقة التكرارية إلى أن تنتهي من جميع البتات المرحلة
	while (y != 0) 
	{ 
		// تحتوي البتات المرحلة الآن على
		// البتات المعينة المشتركة بين العددين المعطيين
		int carry = x & y; 

		// مجموع بتات العددين المعطيين
		// بشرط أن يكون أحد البتات على الأقل غير معين
		x = x ^ y; 

		// يزاح البت المرحّل بمقدار واحد
		// بحيث يؤدي إضافته إلى العدد الأول
		// إلى الحصول على المجموع المطلوب
		y = carry << 1; 
	} 
	return x; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	cout << Add(15, 32); 
	return 0; 
}

• بايثون:

def Add(x, y): 

	# تعمل الحلقة التكرارية إلى أن تنتهي من جميع البتات المرحلة
	while (y != 0): 
	
		# تحتوي البتات المرحلة الآن على
		# البتات المعينة المشتركة بين العددين المعطيين
		carry = x & y 

		# مجموع بتات العددين المعطيين
		# بشرط أن يكون أحد البتات على الأقل غير معين
		x = x ^ y 

		# يزاح البت المرحّل بمقدار واحد
		# بحيث يؤدي إضافته إلى العدد الأول
		# إلى الحصول على المجموع المطلوب
		y = carry << 1
	
	return x 

print(Add(15, 32))

• جافا:

import java.io.*; 

class GFG 
{ 
	static int Add(int x, int y) 
	{ 
		// تعمل الحلقة التكرارية إلى أن تنتهي من جميع البتات المرحلة
		while (y != 0) 
		{ 
			// تحتوي البتات المرحلة الآن على
			// البتات المعينة المشتركة بين العددين المعطيين
			int carry = x & y; 

			// مجموع بتات العددين المعطيين
			// بشرط أن يكون أحد البتات على الأقل غير معين
			x = x ^ y; 

			// يزاح البت المرحّل بمقدار واحد
			// بحيث يؤدي إضافته إلى العدد الأول
			// إلى الحصول على المجموع المطلوب
			y = carry << 1; 
		} 
		return x; 
	} 
	
	// اختبار التابع السابق
	public static void main(String arg[]) 
	{ 
		System.out.println(Add(15, 32)); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

47

الطريقة التعاودية

يمكن استخدام التعاود Recursion عوضًا عن الحلقة التكرارية لتحقيق النتيجة عينها:

• C++‎:

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

int Add(int x, int y) 
{ 
    if (y == 0) 
        return x; 
    else
        return Add( x ^ y, (x & y) << 1); 
} 

// اختبار الدالة السابقة
int main()
{
    cout << Add(15, 32);
    return 0;
}

• بايثون:

def Add(x , y):
	if (y == ):
		return x
	else:
		return Add( x ^ y, (x & y) << 1)
		
print(Add(15, 32))

• جافا:

import java.io.*; 

class GFG 
{ 
	static int Add(int x, int y)
	{
		if (y == 0)
			return x;
		else
			return Add( x ^ y, (x & y) << 1);
	} 
	
	// اختبار الدالة السابقة
	public static void main(String arg[]) 
	{ 
		System.out.println(Add(15, 32)); 
	} 
}

طرح رقمين دون استخدام العوامل

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

أدناه جدول الحقيقة Truth table للطارح النصفي:

X     Y    الاستعارة         الفرق
0     0     0            0
0     1     1            1
1     0     1            0
1     1     0            0

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

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

• C‎:

#include<stdio.h> 

int subtract(int x, int y) 
{ 
	// تعمل الحلقة التكرارية إلى أن تنتهي من جميع البتات المرحلة 
	while (y != 0) 
	{ 
		// تحتوي الاستعارة الآن على البتات
		// المعيّنة المشتركة في العدد الثاني
		// والبتات غير المعيّنة في العدد الأول
		int borrow = (~x) & y; 

		// طرح بتات العددين بشرط أن يكون
		// هناك بت واحد على الأقل غير معين
		x = x ^ y; 

		// تزاح البتات المستعارة بمقدار واحد
		// بحيث يؤدي طرحها من العدد الأول إلى
		// الحصول على الناتج المطلوب
		y = borrow << 1; 
	} 
	return x; 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int x = 29, y = 13; 
	printf("x - y is %d", subtract(x, y)); 
	return 0; 
}

• بايثون:

def subtract(x, y): 

	# تعمل الحلقة التكرارية
	# إلى أن تنتهي من جميع البتات المرحلة
	while (y != 0): 
	
		# تحتوي الاستعارة الآن على البتات
		# المعيّنة المشتركة في العدد الثاني
		# والبتات غير المعيّنة في العدد الأول
		borrow = (~x) & y 
		
		# طرح بتات العددين بشرط أن يكون 
		# هناك بت واحد على الأقل غير معين 
		x = x ^ y 

		# تزاح البتات المستعارة بمقدار واحد
		# بحيث يؤدي طرحها من العدد الأول إلى
		# الحصول على الناتج المطلوب
		y = borrow << 1
	
	return x 


# اختبار الدالة السابقة
x = 29
y = 13
print("x - y is",subtract(x, y))

• جافا:

import java.io.*; 

class GFG 
{ 
	static int subtract(int x, int y) 
	{ 
		
	// تعمل الحلقة التكرارية إلى أن تنتهي من جميع البتات المرحلة 
	while (y != 0) 
	{ 
		// تحتوي الاستعارة الآن على البتات
		// المعيّنة المشتركة في العدد الثاني
		// والبتات غير المعيّنة في العدد الأول
		int borrow = (~x) & y; 

		// طرح بتات العددين بشرط أن يكون
		// هناك بت واحد على الأقل غير معين
		x = x ^ y; 

		// تزاح البتات المستعارة بمقدار واحد
		// بحيث يؤدي طرحها من العدد الأول إلى
		// الحصول على الناتج المطلوب
		y = borrow << 1; 
	} 
	
	return x; 
} 
	
	// اختبار التابع السابق
	public static void main (String[] args) 
	{ 
		int x = 29, y = 13; 
		
		System.out.println("x - y is " + 
						subtract(x, y)); 
	} 
}

الطريقة التعاودية

يمكن استخدام التعاود عوضًا عن الحلقة التكرارية لتحقيق النتيجة عينها:

• C‎:

#include<stdio.h> 

int subtract(int x, int y) 
{ 
	if (y == 0) 
		return x; 
	return subtract(x ^ y, (~x & y) << 1); 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int x = 29, y = 13; 
	printf("x - y is %d", subtract(x, y)); 
	return 0; 
}

• بايثون:

def subtract(x, y): 

	if (y == 0): 
		return x 
	return subtract(x ^ y, (~x & y) << 1) 

# اختبار الدالة السابقة 
x = 29
y = 13
print("x - y is", subtract(x, y))

• جافا:

class GFG { 

	static int subtract(int x, int y) 
	{ 

		if (y == 0) 
			return x; 

		return subtract(x ^ y, (~x & y) << 1); 
	} 

	// اختبار التابع السابقة
	public static void main(String[] args) 
	{ 
		int x = 29, y = 13; 
		System.out.printf("x - y is %d", 
							subtract(x, y)); 
	} 
}

مصادر

• صفحة Add two numbers without using arithmetic operators في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Subtract two numbers without using arithmetic operators في توثيق الخوارزميات في موقع GeeksforGeeks.