Algorithms/add one

تضيف هذه الخوارزمية العدد 1 على العدد المعطى دون استخدام أيٍّ من العوامل الرياضية مثل ‎‘+’, ‘-‘, ‘*’, ‘/’, ‘++’, ‘–‘‎.

الطريقة الأولى

لإضافة العدد 1 إلى أي عدد (ليكن 0011000111) يمكن قلب جميع البتات بعد البت 0 في أقصى اليمين (سنحصل على 0011000000) ثم قلب البت 0 في أقصى اليمين كذلك (سنحصل على 0011001000) للحصول على الناتج النهائي.

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

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

• C++‎:

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

int addOne(int x) 
{ 
	int m = 1; 
	
	// قلب جميع البتات المعينة إلى حين العثور على 0
	while( x & m ) 
	{ 
		x = x ^ m; 
		m <<= 1; 
	} 
	
	// قلب البت 0 في أقصى اليمين
	x = x ^ m; 
	return x; 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	cout<<addOne(13); 
	return 0; 
}

• بايثون:

def addOne(x) : 
	
	m = 1; 
	# قلب جميع البتات المعينة إلى حين العثور على 0
	while(x & m): 
		x = x ^ m 
		m <<= 1
	
	# قلب البت 0 في أقصى اليمين
	x = x ^ m 
	return x 

# اختبار الدالة السابقة
n = 13
print addOne(n)

• جافا:

class GFG { 

	static int addOne(int x) 
	{ 
		int m = 1; 
		
		// قلب جميع البتات المعينة إلى حين العثور على 0 
		while( (int)(x & m) >= 1) 
		{ 
			x = x ^ m; 
			m <<= 1; 
		} 
	
		// قلب البت 0 في أقصى اليمين 
		x = x ^ m; 
		return x; 
	} 
	
	/* اختبار التابع السابق */
	public static void main(String[] args) 
	{ 
		System.out.println(addOne(13)); 
	} 
}

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

14

الطريقة الثانية

تستخدم معظم الأنظمة والمعماريات طريقة متممات الاثنين 2s complement لتمثيل الأعداد السالبة، ويمكن اتباع الطريقة التالية لإضافة العدد 1 إلى عدد معين دون استخدام العوامل الحسابية.

لنفترض أنّ x يمثّل قيمة عددية فإنّ:

~x = -(x+1)

يمثّل الرمز ~ متمّم العدد الثنائي، ويأتي التعبير (x+1) نتيجة لإضافة 1 في عملية تحويل متمّمات الاثنين، ولتطبيق عملية الجمع هذه يمكن إجراء عملية نفي أخرى، ليصبح التعبير النهائي: ‎(-(~x))‎

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

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

• C++‎:

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

int addOne(int x) 
{ 
	return (-(~x)); 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	cout<<addOne(13); 
	return 0; 
}

• بايثون:

def addOne(x): 
	return (-(~x)); 


# اختبار الدالة السابقة
print(addOne(13))

• جافا:

class GFG 
{ 
	static int addOne(int x) 
	{ 
		return (-(~x)); 
	} 
	
	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		System.out.printf("%d", addOne(13)); 
	} 
}

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

14

مصادر

• صفحة Add 1 to a given number في توثيق الخوارزميات في موقع GeeksforGeeks.