عرض مصدر Algorithms/total set bits

<noinclude>{{DISPLAYTITLE:تعداد البتات المعينة الكلية في الأعداد من 1 إلى العدد المعطى}}</noinclude>
هناك عدة طرق لحساب مجموع عدد البتات المعينة في التمثيل الثنائي لجميع الأعداد بدءًا من <code>1</code> وانتهاءً بالعدد المعطى <code>n</code>.

'''مثال:'''

<source lang="text">Input: n = 3
Output:  4

Input: n = 6
Output: 9

Input: n = 7
Output: 12

Input: n = 8
Output: 13</source>
== الطريقة الأولى ==

أبسط حلّ لهذه المسألة هو إنشاء حلقة تكرارية تبدأ من <code>1</code> وتنتهي بالعدد <code>n</code> وتجمع عدد البتات المعينة في جميع الأعداد ابتداءً من <code>1</code> وانتهاءً بالعدد <code>n</code>.

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

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

* C++‎:

<source lang="c++">#include <stdio.h> 

// دالة مساعدة لحساب البتات المعيّنة في العدد المعطى
unsigned int countSetBitsUtil(unsigned int x); 

// تعيد الدالة تعداد البتات المعينة في جميع الأعداد بدءًا من 1 وانتهاءً بالعدد المعطى
unsigned int countSetBits(unsigned int n) 
{ 
	int bitCount = 0; // تهيئة النتيجة

	for (int i = 1; i <= n; i++) 
		bitCount += countSetBitsUtil(i); 

	return bitCount; 
} 

// دالة مساعدة لحساب عدد البتات المعينة في العدد المعطى
unsigned int countSetBitsUtil(unsigned int x) 
{ 
	if (x <= 0) 
		return 0; 
	return (x % 2 == 0 ? 0 : 1) + countSetBitsUtil(x / 2); 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int n = 4; 
	printf("Total set bit count is %d", countSetBits(n)); 
	return 0; 
} 
</source>
* بايثون:

<source lang="python"># تعيد الدالة تعداد البتات المعينة في جميع الأعداد بدءًا من 1 وانتهاءً بالعدد المعطى 
def countSetBits(n): 
	
	# تهيئة النتيجة 
	bitCount = 0

	for i in range(1, n + 1): 
		bitCount += countSetBitsUtil(i) 

	return bitCount 


# دالة مساعدة لحساب عدد البتات المعينة في العدد المعطى 
def countSetBitsUtil(x): 

	if (x <= 0): 
		return 0
	return (0 if int(x % 2) == 0 else 1) + countSetBitsUtil(int(x / 2)) 


# اختبار الدالة السابقة
if __name__=='__main__': 
	n = 4
	print("Total set bit count is", countSetBits(n)) </source>
* جافا:

<source lang="java">class GFG{ 

	// تعيد الدالة تعداد البتات المعينة في جميع الأعداد بدءًا من 1 وانتهاءً بالعدد المعطى
	static int countSetBits( int n) 
	{ 
		// تهيئة النتيجة
		int bitCount = 0; 
	
		for (int i = 1; i <= n; i++) 
			bitCount += countSetBitsUtil(i); 
	
		return bitCount; 
	} 
	
	// تابع مساعد لحساب عدد البتات المعينة في العدد المعطى
	static int countSetBitsUtil( int x) 
	{ 
		if (x <= 0) 
			return 0; 
		return (x % 2 == 0 ? 0 : 1) + 
			countSetBitsUtil(x / 2); 
	} 
	
	// اختبار التوابع السابقة
	public static void main(String[] args) 
	{ 
		int n = 4; 
		System.out.print("Total set bit count is "); 
		System.out.print(countSetBits(n)); 
	} 
} </source>
تعطي الشيفرات السابقة المخرجات التالية:

<source lang="text">Total set bit count is 5</source>
=== التعقيد الزمني ===

يبلغ التعقيد الزمني لهذه الطريةق المقدار <code>O(nLogn)‎</code>.

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

إذا رُتّبت الأعداد الثنائية ترتيبًا عموديًا فيمكن ملاحظة أنّ البتات في أقصى اليمين تنقلب بعد <code>‎2^i‎</code> موقع في التسلسل العمودي.

فعلى سبيل المثال: 

<source lang="text">n = 5;
0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000</source>
يلاحظ مثلًا أن البت الموجود في أقصى اليمين (<code>i = 0</code>) ينقلب بعد (‎<code>2^0 = 1</code>‎) عدد، وأنّ البت الثالث من جهة اليمين (<code>‎i = 2</code>) ينقلب بعد (<code>‎2^2 = 4</code>) أعداد.

يمكن حساب البتات بطريقة عمودية بحيث أنّ الموقع <code>i</code> من جهة اليمين سينقلب بعد <code>‎2^i</code> من الدورات.

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

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

* C++‎:

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

// تحسب الدالة البتات المعينة من 0 إلى العدد المعطى
int countSetBits(int n) 
{ 
	int i = 0; 

	// يحفظ هذا المتغير مجموع البتات المعيّنة من 0 إلى العدد المعطى
	int ans = 0; 

	// تنفّذ الحلقة التكرارية ما دام العدد المعطى أكبر من ‎2^i‎ أو مساويًا له
	while ((1 << i) <= n) { 

		// ستنقلب قيمة هذا المتغير بعد ‎2^i من الدورات
		bool k = 0; 

		// هذا المتغير هو مكرِّر من ‎2^i إلى 1
		int change = 1 << i; 

		// ستنفّذ هذه الحلقة من 0 إلى العدد المعطى لكل موقع خاص بالبتات
		for (int j = 0; j <= n; j++) { 

			ans += k; 

			if (change == 1) { 
				k = !k; // قلب البت عند تحقق الشرط 
				change = 1 << i; // إعادة تعيين قيمة المتغير
			} 
			else { 
				change--; 
			} 
		} 

		// زيادة الموقع
		i++; 
	} 

	return ans; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int n = 17; 
	cout << countSetBits(n) << endl; 
	return 0; 
} 
</source>
* بايثون:

<source lang="python"># تحسب الدالة البتات المعينة من 0 إلى العدد المعطى 
def countSetBits(n) : 
	i = 0

	# يحفظ هذا المتغير مجموع البتات المعيّنة من 0 إلى العدد المعطى
	ans = 0

	# تنفّذ الحلقة التكرارية ما دام العدد المعطى أكبر من ‎2^i‎ أو مساويًا له
	while ((1 << i) <= n) : 

		# ستنقلب قيمة هذا المتغير بعد ‎2^i من الدورات
		k = 0

		# هذا المتغير هو مكرِّر من ‎2^i إلى 1 
		change = 1 << i 

		# ستنفّذ هذه الحلقة من 0 إلى العدد المعطى لكل موقع خاص بالبتات 
		for j in range(0, n+1) : 
			ans += k 

			if change == 1 : 
				
				# قلب البت عند تحقق الشر 
				k = not k 

				# إعادة تعيين قيمة المتغير 
				change = 1 << i 

			else : 
				change -= 1

		# زيادة الموقع 
		i += 1

	return ans 



# اختبار الدالة السابقة 
if __name__ == "__main__" : 

	n = 17
	print(countSetBits(n)) </source>
* جافا:

<source lang="java">public class GFG { 
	
	// تحسب الدالة البتات المعينة من 0 إلى العدد المعطى 
	static int countSetBits(int n) 
	{ 
		int i = 0; 

		// يحفظ هذا المتغير مجموع البتات المعيّنة من 0 إلى العدد المعطى 
		int ans = 0; 

		// تنفّذ الحلقة التكرارية ما دام العدد المعطى أكبر من ‎2^i‎ أو مساويًا له 
		while ((1 << i) <= n) { 

			//  ستنقلب قيمة هذا المتغير بعد ‎2^i من الدورات
			boolean k = false; 

			// هذا المتغير هو مكرِّر من ‎2^i إلى 1 
			int change = 1 << i; 

			// ستنفّذ هذه الحلقة من 0 إلى العدد المعطى لكل موقع خاص بالبتات
			for (int j = 0; j <= n; j++) { 

				if (k == true) 
					ans += 1; 
				else
					ans += 0; 

				if (change == 1) { 
					
					//  قلب البت عند تحقق الشرط 
					k = !k; 
					
					// إعادة تعيين قيمة المتغير 
					change = 1 << i; 
				} 
				else { 
					change--; 
				} 
			} 

			//  زيادة الموقع 
			i++; 
		} 

		return ans; 
	} 

	// اختبار الدوال السابقة
	public static void main(String[] args) 
	{ 
		int n = 17; 
		
		System.out.println(countSetBits(n)); 
	} 
} </source>
تعطي الشيفرات السابقة المخرجات التالية:

<source lang="text">35</source>
=== التعقيد الزمني ===

يبلغ التعقيد الزمني لهذه الطريقة المقدار <code>O(k*n)‎</code>K. تمثّل <code>k</code> عدد البتات التي تمثّل العدد <code>n</code>، وقيمتها <code>k <= 64</code>.

== مصادر ==
* صفحة [https://www.geeksforgeeks.org/count-total-set-bits-in-all-numbers-from-1-to-n/ Count total set bits in all numbers from 1 to n] في توثيق الخوارزميات في موقع GeeksforGeeks.
[[تصنيف:الخوارزميات]]
[[تصنيف:خوارزميات الأعداد الثنائية]]