تعداد البتات المعينة الكلية في الأعداد من 1 إلى العدد المعطى

هناك عدة طرق لحساب مجموع عدد البتات المعينة في التمثيل الثنائي لجميع الأعداد بدءًا من 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.

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

إذا كانت هيئة الرقم المدخل هي ‎2^b -1 مثل: ‎1, 3, 7, 15 ... الخ فإنّ عدد البتات المعيّنة هو b * (2^(b-1)‎)‎، وذلك لأنّ حساب المتمّم لقائمة الأعداد الثنائية ثم قلب تلك القائمة (لجميع الأعداد من 0 إلى‎(2^b)-1‎)‎` سيؤدي إلى الحصول على القائمة نفسها (نصف البتات مفعّلة والنصف الآخر غير مفعّل).

إن لم تكن جميع البتات مفعّلة في رقم معين، فإنّ الموقع m سيكون موقع البت المعيّن في أقصى اليسار، ويكون عدد البتات المعيّنة في ذلك الموقع مساويًا للمقدار ‎n - (1 >> m) + 1، وتكون بقية البتات المعيّنة على نوعين:

1. البتات في المواقع (m-1) نزولًا إلى النقطة التي يصبح فيها البت في أقصى اليسار مساويًا للصفر
   

2.

If the number does not have all set bits, then some position m is the position of leftmost set bit. The number of set bits in that position is n – (1 << m) + 1. The remaining set bits are in two parts:

1) The bits in the (m-1) positions down to the point where the leftmost bit becomes 0, and
2) The 2^(m-1) numbers below that point, which is the closed form above.

An easy way to look at it is to consider the number 6:

0|0 0
0|0 1
0|1 0
0|1 1
-|--
1|0 0
1|0 1
1|1 0
The leftmost set bit is in position 2 (positions are considered starting from 0). If we mask that off what remains is 2 (the “1 0” in the right part of the last row.) So the number of bits in the 2nd position (the lower left box) is 3 (that is, 2 + 1). The set bits from 0-3 (the upper right box above) is 2*2^(2-1) = 4. The box in the lower right is the remaining bits we haven’t yet counted, and is the number of set bits for all the numbers up to 2 (the value of the last entry in the lower right box) which can be figured recursively.

• C++‎:

#include <bits/stdc++.h> 

// A O(Logn) complexity program to count 
// set bits in all numbers from 1 to n 
using namespace std; 

/* Returns position of leftmost set bit. 
The rightmost position is considered 
as 0 */
unsigned int getLeftmostBit(int n) 
{ 
	int m = 0; 
	while (n > 1) 
	{ 
		n = n >> 1; 
		m++; 
	} 
	return m; 
} 

/* Given the position of previous leftmost 
set bit in n (or an upper bound on 
leftmost position) returns the new 
position of leftmost set bit in n */
unsigned int getNextLeftmostBit(int n, int m) 
{ 
	unsigned int temp = 1 << m; 
	while (n < temp) { 
		temp = temp >> 1; 
		m--; 
	} 
	return m; 
} 

// The main recursive function used by countSetBits() 
unsigned int _countSetBits(unsigned int n, int m); 

// Returns count of set bits present in 
// all numbers from 1 to n 
unsigned int countSetBits(unsigned int n) 
{ 
	// Get the position of leftmost set 
	// bit in n. This will be used as an 
	// upper bound for next set bit function 
	int m = getLeftmostBit(n); 

	// Use the position 
	return _countSetBits(n, m); 
} 

unsigned int _countSetBits(unsigned int n, int m) 
{ 
	// Base Case: if n is 0, then set bit 
	// count is 0 
	if (n == 0) 
		return 0; 

	/* get position of next leftmost set bit */
	m = getNextLeftmostBit(n, m); 

	// If n is of the form 2^x-1, i.e., if n 
	// is like 1, 3, 7, 15, 31, .. etc, 
	// then we are done. 
	// Since positions are considered starting 
	// from 0, 1 is added to m 
	if (n == ((unsigned int)1 << (m + 1)) - 1) 
		return (unsigned int)(m + 1) * (1 << m); 

	// update n for next recursive call 
	n = n - (1 << m); 
	return (n + 1) + countSetBits(n) + m * (1 << (m - 1)); 
} 

// Driver code 
int main() 
{ 
	int n = 17; 
	cout<<"Total set bit count is "<< countSetBits(n); 
	return 0; 
} 

// This code is contributed by rathbhupendra

• بايثون:

# A O(Logn) complexity program to count 
# set bits in all numbers from 1 to n 

""" 
/* Returns position of leftmost set bit. 
The rightmost position is considered 
as 0 */ 
"""
def getLeftmostBit(n): 

	m = 0
	while (n > 1) : 

		n = n >> 1
		m += 1

	return m 

""" 
/* Given the position of previous leftmost 
set bit in n (or an upper bound on 
leftmost position) returns the new 
position of leftmost set bit in n */ 
"""
def getNextLeftmostBit(n, m) : 

	temp = 1 << m 
	while (n < temp) : 
		temp = temp >> 1
		m -= 1

	return m 

# The main recursive function used by countSetBits() 
# def _countSetBits(n, m) 

# Returns count of set bits present in 
# all numbers from 1 to n 
def countSetBits(n) : 

	# Get the position of leftmost set 
	# bit in n. This will be used as an 
	# upper bound for next set bit function 
	m = getLeftmostBit(n) 

	# Use the position 
	return _countSetBits(n, m) 

def _countSetBits(n, m) : 

	# Base Case: if n is 0, then set bit 
	# count is 0 
	if (n == 0) : 
		return 0

	# /* get position of next leftmost set bit */ 
	m = getNextLeftmostBit(n, m) 

	# If n is of the form 2^x-1, i.e., if n 
	# is like 1, 3, 7, 15, 31, .. etc, 
	# then we are done. 
	# Since positions are considered starting 
	# from 0, 1 is added to m 
	if (n == (1 << (m + 1)) - 1) : 
		return ((m + 1) * (1 << m)) 

	# update n for next recursive call 
	n = n - (1 << m) 
	return (n + 1) + countSetBits(n) + m * (1 << (m - 1)) 

# Driver code 
n = 17
print("Total set bit count is", countSetBits(n)) 

# This code is contributed by rathbhupendra

• جافا:

// Java A O(Logn) complexity program to count 
// set bits in all numbers from 1 to n 
import java.io.*; 

class GFG 
{ 
	
/* Returns position of leftmost set bit. 
The rightmost position is considered 
as 0 */
static int getLeftmostBit(int n) 
{ 
	int m = 0; 
	while (n > 1) 
	{ 
		n = n >> 1; 
		m++; 
	} 
	return m; 
} 

/* Given the position of previous leftmost 
set bit in n (or an upper bound on 
leftmost position) returns the new 
position of leftmost set bit in n */
static int getNextLeftmostBit(int n, int m) 
{ 
	int temp = 1 << m; 
	while (n < temp) 
	{ 
		temp = temp >> 1; 
		m--; 
	} 
	return m; 
} 

// The main recursive function used by countSetBits() 
// Returns count of set bits present in 
// all numbers from 1 to n 

static int countSetBits(int n) 
{ 
	// Get the position of leftmost set 
	// bit in n. This will be used as an 
	// upper bound for next set bit function 
	int m = getLeftmostBit(n); 

	// Use the position 
	return countSetBits(n, m); 
} 

static int countSetBits( int n, int m) 
{ 
	// Base Case: if n is 0, then set bit 
	// count is 0 
	if (n == 0) 
		return 0; 

	/* get position of next leftmost set bit */
	m = getNextLeftmostBit(n, m); 

	// If n is of the form 2^x-1, i.e., if n 
	// is like 1, 3, 7, 15, 31, .. etc, 
	// then we are done. 
	// Since positions are considered starting 
	// from 0, 1 is added to m 
	if (n == ((int)1 << (m + 1)) - 1) 
		return (int)(m + 1) * (1 << m); 

	// update n for next recursive call 
	n = n - (1 << m); 
	return (n + 1) + countSetBits(n) + m * (1 << (m - 1)); 
} 

// Driver code 
public static void main (String[] args) 
{ 

	int n = 17; 
	System.out.println ("Total set bit count is " + countSetBits(n)); 
} 
} 

// This code is contributed by ajit..