الفرق بين المراجعتين لصفحة: «Algorithms/total set bits»

من موسوعة حسوب
مرئينص الويكي
أنشأ الصفحة ب'<noinclude>{{DISPLAYTITLE:تعداد البتات المعينة الكلية في الأعداد من 1 إلى العدد المعطى}}</noinclude> هناك عدة ط...'
 
لا ملخص تعديل
 
سطر 307: سطر 307:
يبلغ التعقيد الزمني لهذه الطريقة المقدار <code>O(k*n)‎</code>K. تمثّل <code>k</code> عدد البتات التي تمثّل العدد <code>n</code>، وقيمتها <code>k <= 64</code>.
يبلغ التعقيد الزمني لهذه الطريقة المقدار <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.
إذا كانت هيئة الرقم المدخل هي <code>‎2^b -1</code> مثل: ‎1, 3, 7, 15 ... الخ فإنّ عدد البتات المعيّنة هو <code>b * (2^(b-1)‎)‎، وذلك لأنّ حساب المتمّم لقائمة الأعداد الثنائية ثم قلب تلك القائمة (لجميع الأعداد من 0 إلى</code>‎(2^b)-1‎)‎` سيؤدي إلى الحصول على القائمة نفسها (نصف البتات مفعّلة والنصف الآخر غير مفعّل).
[[تصنيف:الخوارزميات]]
 
[[تصنيف:خوارزميات الأعداد الثنائية]]
إن لم تكن جميع البتات مفعّلة في رقم معين، فإنّ الموقع <code>m</code> سيكون موقع البت المعيّن في أقصى اليسار، ويكون عدد البتات المعيّنة في ذلك الموقع مساويًا للمقدار <code>‎n - (1 >> m) + 1</code>، وتكون بقية البتات المعيّنة على نوعين:
 
# البتات في المواقع <code>(m-1)</code> نزولًا إلى النقطة التي يصبح فيها البت في أقصى اليسار مساويًا للصفر<br />
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<br />
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<br />
0|0 1<br />
0|1 0<br />
0|1 1<br />
-|--<br />
1|0 0<br />
1|0 1<br />
1|1 0<br />
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++‎:
 
<source lang="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
</source>
* بايثون:
 
<source lang="python"># 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
</source>
* جافا:
 
<source lang="java">// 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..
</source>

المراجعة الحالية بتاريخ 20:53، 1 ديسمبر 2019

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

مصادر

مجلوبة من «https://wiki.hsoub.com/index.php?title=Algorithms/total_set_bits&oldid=29379»