عرض مصدر Algorithms/max min 2 numbers

<noinclude>{{DISPLAYTITLE:حساب العدد الأكبر أو الأصغر بين عددين صحيحين دون استخدام التفريع}}</noinclude>
تكون عملية التفريع branching مكلفة في بعض الحالات النادرة على بعض الأجهزة؛ لذا فإنّ عملية إيجاد العدد الأكبر أو الأصغر بين عددين باستخدام التفريع ستكون عملية بطيئة.

يمكن إيجاد العدد الأكبر أو الأصغر دون اللجوء إلى التفريع باتباع إحدى الطرق التالية:

== الطريقة الأولى: استخدام عامل <code>XOR</code> وعامل المقارنة ==

يمكن إيجاد العدد الأصغر بين عددين صحيحين (<code>x, y</code>) باستخدام التعبير:

<source lang="text">y ^ ((x ^ y) & -(x < y))</source>
إن كان العدد <code>x</code> أصغر من العدد <code>y</code> فإنّ نتيجة التعبير <code>‎-(x = y, then -(x < y)‎</code> ستكون أصفارًا، لذا فإن <code>‎r = y ^ ((x ^ y) & 0) = y‎</code>. ولكن في بعض الأجهزة تتطلب عملية تخمين قيمة التعبير <code>(x < y)</code> لتكون <code>0</code> أو <code>1</code> تعليمة تفرّع branch instruction؛ لذا قد لا تقدّم هذه الطريقة التحسين المطلوب.

يمكن إيجاد العدد الأصغر بين عددين صحيحين (<code>x, y</code>) باستخدام التعبير:

<source lang="text">x ^ ((x ^ y) & -(x < y));</source>
=== تنفيذ الطريقة ===

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

* C++‎:

<source lang="c++">#include<iostream> 
using namespace std; 

class gfg 
{ 
	
	/* تحسب الدالة العدد الأصغر بين العددين المعطيين */
	public: 
	int min(int x, int y) 
	{ 
		return y ^ ((x ^ y) & -(x < y)); 
	} 

	/* تحسب الدالة العدد الأكبر بين العددين المعطيين */
	int max(int x, int y) 
	{ 
		return x ^ ((x ^ y) & -(x < y)); 
	} 
	}; 
	
	/* اختبار الدالتين السابقتين */
	int main() 
	{ 
		gfg g; 
		int x = 15; 
		int y = 6; 
		cout << "Minimum of " << x << 
			" and " << y << " is "; 
		cout << g. min(x, y); 
		cout << "\nMaximum of " << x << 
				" and " << y << " is "; 
		cout << g.max(x, y); 
		getchar(); 
	} </source>
* بايثون:

<source lang="python">
# تحسب الدالة العدد الأصغر بين العددين المعطيين

def min(x, y): 

	return y ^ ((x ^ y) & -(x < y)) 


# تحسب الدالة العدد الأكبر بين العددين المعطيين
def max(x, y): 

	return x ^ ((x ^ y) & -(x < y)) 


# اختبار الدالتين السابقتين

x = 15
y = 6
print("Minimum of", x, "and", y, "is", end=" ") 
print(min(x, y)) 
print("Maximum of", x, "and", y, "is", end=" ") 
print(max(x, y)) </source>
* جافا:

<source lang="java">public class AWS { 

/* تحسب الدالة العدد الأصغر بين العددين المعطيين */
	static int min(int x, int y) 
	{ 
	return y ^ ((x ^ y) & -(x << y)); 
	} 
	
/* تحسب الدالة العدد الأكبر بين العددين المعطيين */
	static int max(int x, int y) 
	{ 
	return x ^ ((x ^ y) & -(x << y)); 
	} 
	
	// اختبار التابعين السابقين
	public static void main(String[] args) { 
		
		int x = 15; 
		int y = 6; 
		System.out.print("Minimum of "+x+" and "+y+" is "); 
		System.out.println(min(x, y)); 
		System.out.print("Maximum of "+x+" and "+y+" is "); 
		System.out.println( max(x, y)); 
	} 

} 
</source>
تعطي الشيفرات السابقة المعطيات التالية:

<source lang="text">Minimum of 15 and 6 is 6
Maximum of 15 and 6 is 15</source>
== الطريقة الثانية: الطرح والإزاحة ==

إذا علمنا أنّ: 

<source lang="text">INT_MIN <= (x - y) <= INT_MAX</source>
فيمكن استخدام التعابير التالية والتي ستكون أسرع لأنّ التعبير <code>(x - y)</code> سيخمَّن مرة واحدة فقط.

يمكن إيجاد العدد الأصغر بين عددين صحيحين (<code>x, y</code>) باستخدام التعبير:

<code>y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))</code>

تزيح هذه الطريقة ناتج طرح <code>y</code> من <code>x</code> بمقدار <code>31</code> (إن كان حجم العدد الصحيح <code>32</code>). فإن كان ناتج الطرح <code>(x-y)</code> أصغر من <code>0</code>، فإنّ ‎<code>(x -y)>>31</code>‎ سيكون <code>1</code>. وإن كان ناتج الطرح أكبر من <code>0</code> أو مساويًا له، فإنّ ‎<code>(x -y)>>31</code>‎ سيكون <code>0</code>.

لذا إن كان العدد <code>x</code> أكبر من <code>y</code> أو مساويًا له فإنّ العدد الأصغر بينهما سيكون <code>y + (x-y)&0</code> وهو العدد <code>y</code>.<br />
وإن كان العدد <code>x</code> أصغر من العدد <code>y</code> فإنّ العدد الأصغر بينهما هو <code>y + (x-y)&1</code> وهو العدد <code>x</code>.

يمكن إيجاد العدد الأكبر بين العددين <code>(x, y)</code> بنفس الطريقة:

<source lang="text">x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))</source>
=== تنفيذ الطريقة ===

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

* C++‎:

<source lang="c++">#include <bits/stdc++.h> 
using namespace std; 
#define CHARBIT 8 

/* تحسب الدالة العدد الأصغر بين العددين المعطيين */
int min(int x, int y) 
{ 
	return y + ((x - y) & ((x - y) >> 
			(sizeof(int) * CHARBIT - 1))); 
} 

/* تحسب الدالة العدد الأكبر بين العددين المعطيين */
int max(int x, int y) 
{ 
	return x - ((x - y) & ((x - y) >> 
			(sizeof(int) * CHARBIT - 1))); 
} 

/* اختبار الدالتين السابقتين */
int main() 
{ 
	int x = 15; 
	int y = 6; 
	cout<<"Minimum of "<<x<<" and "<<y<<" is "; 
	cout<<min(x, y); 
	cout<<"\nMaximum of"<<x<<" and "<<y<<" is "; 
	cout<<max(x, y); 
} </source>
* بايثون:

<source lang="python">import sys; 
	
CHAR_BIT = 8; 
INT_BIT = sys.getsizeof(int()); 

# تحسب الدالة العدد الأصغر بين العددين المعطيين
def Min(x, y): 
	return y + ((x - y) & ((x - y) >> 
				(INT_BIT * CHAR_BIT - 1))); 

# تحسب الدالة العدد الأكبر بين العددين المعطيين
def Max(x, y): 
	return x - ((x - y) & ((x - y) >> 
				(INT_BIT * CHAR_BIT - 1))); 

# اختبار الدالتين السابقتين
x = 15; 
y = 6; 
print("Minimum of", x, "and", 
					y, "is", Min(x, y)); 
print("Maximum of", x, "and", 
					y, "is", Max(x, y)); </source>
* جافا:

<source lang="java">class GFG 
{ 
	
static int CHAR_BIT = 4; 
static int INT_BIT = 8; 
/* يحسب التابع العدد الأصغر بين العددين المعطيين */
static int min(int x, int y) 
{ 
	return y + ((x - y) & ((x - y) >> 
				(INT_BIT * CHAR_BIT - 1))); 
} 

/* يحسب التابع العدد الأكبر بين العددين المعطيين */
static int max(int x, int y) 
{ 
	return x - ((x - y) & ((x - y) >> 
			(INT_BIT * CHAR_BIT - 1))); 
} 

/* اختبار التابعين السابقين */
public static void main(String[] args) 
{ 
	int x = 15; 
	int y = 6; 
	System.out.println("Minimum of "+x+" and "+y+" is "+min(x, y)); 
	System.out.println("Maximum of "+x+" and "+y+" is "+max(x, y)); 
} 
} </source>
== مصادر ==

* صفحة [https://www.geeksforgeeks.org/compute-the-minimum-or-maximum-max-of-two-integers-without-branching/ Compute the minimum or maximum of two integers without branching] في توثيق الخوارزميات في موقع GeeksforGeeks.

[[تصنيف: الخوارزميات]]
[[تصنيف: خوارزميات الأعداد الثنائية]]