حساب العدد الأكبر أو الأصغر بين عددين صحيحين دون استخدام التفريع

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

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

الطريقة الأولى: استخدام عامل XOR وعامل المقارنة

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

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

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

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

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

تنفيذ الطريقة

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

• 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(); 
	}

• بايثون:

# تحسب الدالة العدد الأصغر بين العددين المعطيين

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))

• جافا:

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)); 
	} 

}

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

Minimum of 15 and 6 is 6
Maximum of 15 and 6 is 15

الطريقة الثانية: الطرح والإزاحة

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

INT_MIN <= (x - y) <= INT_MAX

فيمكن استخدام التعابير التالية والتي ستكون أسرع لأنّ التعبير (x - y) سيخمَّن مرة واحدة فقط.

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

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

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

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

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

x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))

تنفيذ الطريقة

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

• 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); 
}

• بايثون:

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));

• جافا:

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)); 
} 
}

مصادر

• صفحة Compute the minimum or maximum of two integers without branching في توثيق الخوارزميات في موقع GeeksforGeeks.