Algorithms/total set bits

هناك عدة طرق لحساب مجموع عدد البتات المعينة في التمثيل الثنائي لجميع الأعداد بدءًا من 1 وانتهاءً بالعدد المعطى n.

مثال:

Input: n = 3
Output:  4

Input: n = 6
Output: 9

Input: n = 7
Output: 12

Input: n = 8
Output: 13

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

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

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

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

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

• بايثون:

# تعيد الدالة تعداد البتات المعينة في جميع الأعداد بدءًا من 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))

• جافا:

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

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

Total set bit count is 5

التعقيد الزمني

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

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

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

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

n = 5;
0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000

يلاحظ مثلًا أن البت الموجود في أقصى اليمين (i = 0) ينقلب بعد (‎2^0 = 1‎) عدد، وأنّ البت الثالث من جهة اليمين (‎i = 2) ينقلب بعد (‎2^2 = 4) أعداد.

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

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

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

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

• بايثون:

# تحسب الدالة البتات المعينة من 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))

• جافا:

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

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

35

التعقيد الزمني

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

مصادر

• صفحة Count total set bits in all numbers from 1 to n في توثيق الخوارزميات في موقع GeeksforGeeks.