Algorithms/count set bits

المطلوب في هذه المسألة هو عد البتات المعيّنة (التي تحمل القيمة 1) في التمثيل الثنائي للعدد الصحيح المعطى.

مثال:

Input : n = 6
Output : 2
Binary representation of 6 is 110 and has 2 set bits

Input : n = 13
Output : 3
Binary representation of 13 is 1101 and has 3 set bits

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

يمكن المرور على جميع البتات في التمثيل الثنائي للعدد الصحيح المعطى، والتحقّق مما إذا كان البتّ الحالي معيّنًا أو لا، فإن كان كذلك تُزاد قيمة العداد بمقدار واحد.

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

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

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

unsigned int countSetBits(unsigned int n) 
{ 
	unsigned int count = 0; 
	while (n) { 
		count += n & 1; 
		n >>= 1; 
	} 
	return count; 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	int i = 9; 
	cout << countSetBits(i); 
	return 0; 
}

• بايثون:

def countSetBits(n): 
	count = 0
	while (n): 
		count += n & 1
		n >>= 1
	return count 


# اختبار الدالة السابقة 
i = 9
print(countSetBits(i))

• جافا:

import java.io.*; 

class countSetBits { 
	static int countSetBits(int n) 
	{ 
		int count = 0; 
		while (n > 0) { 
			count += n & 1; 
			n >>= 1; 
		} 
		return count; 
	} 

	// اختبار الدالة السابقة
	public static void main(String args[]) 
	{ 
		int i = 9; 
		System.out.println(countSetBits(i)); 
	} 
}

الطريقة التعاودية

يمكن تنفيذ الشيفرة السابقة بطريقة تعاودية وكما توضّحه الأمثلة التالية:

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

// دالة تعاودية لحساب البتات المعيّنة
int countSetBits(int n) 
{ 
	// الحالة الأساس 
	if (n == 0) 
		return 0; 

	else
		// إن كان البت الأخير معيّنًا نضيف 1 وإلا أضفنا 0
		return (n & 1) + countSetBits(n >> 1); 
} 

// اختبار الدالة السابقة
int main() 
{ 
	// العدد المطلوب
	int n = 9; 

	// استدعاء الدالة
	cout << countSetBits(n); 

	return 0; 
}

• بايثون:

def countSetBits( n): 
	
	# الحالة الأساس
	if (n == 0): 
		return 0

	else: 

		# إن كان البت الأخير معيّنًا نضيف 1 وإلا أضفنا 0
		return (n & 1) + countSetBits(n >> 1) 
		
# العدد المطلوب 
n = 9

# استدعاء الدالة
print( countSetBits(n))

• جافا:

import java.io.*; 

class GFG { 

	public static int countSetBits(int n) 
	{ 

		// الحالة الأساس 
		if (n == 0) 
			return 0; 

		else
			// إن كان البت الأخير معيّنًا أضفنا 1 وإلا أضفنا 0
			return (n & 1) + countSetBits(n >> 1); 
	} 

	// اختبار الدالة السابقة
	public static void main(String[] args) 
	{ 

		// العدد المطلوب
		int n = 9; 

		// استدعاء التابع
		System.out.println(countSetBits(n)); 
	}

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

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

خوارزمية Brian Kernighan

يؤدي طرح المقدار 1 من عدد عشري إلى قلب جميع البتات بعد البت المعيّن في أقصى اليمين بالإضافة إلى هذا البت.

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

التمثيل الثنائي للعد 10 هو ‎00001010.

التمثيل الثنائي للعد 9 هو ‎00001001.

التمثيل الثنائي للعد 8 هو ‎00001000.

التمثيل الثنائي للعد 7 هو ‎00000111.

لذا إن طرحنا المقدار 1 من العدد المعطى وطبّقنا العامل & الثنائي مع العدد الأصلي (n & (n-1)‎) فسنلغي تعيين آخر بت معيّن في أقصى اليمين. وإن نفذنا التعبير n & (n-1)‎ في حلقة تكرارية وأحصينا عدد المرات التي ستنفّذ فيها الحلقة التكرراية، فسنحصل على عدد البتات المعيّنة، وهذا يعني أنّ عدد دورات الحلقة التكرارية يعتمد على عدد البتات المعينة في العدد المعطى.

يمكن تلخيص خطوات الخوارزمية بما يلي:

1. تهيئة العداد ليساوي صفرًا.
2. إن لم يكن العدد المعطى n صفرًا:
   1. يطبّق العامل & الثنائي على n و n-1 وإسناد النتيجة إلى n مرة أخرى.
   2. زيادة العداد بمقدار 1.
   3. الذهاب إلى الخطوة 2.
3. وإلا نعيد قيمة العداد.

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

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

• C++‎:

#include <iostream> 
using namespace std; 
unsigned int countSetBits(int n) 
	{ 
		unsigned int count = 0; 
		while (n) { 
			n &= (n - 1); 
			count++; 
		} 
		return count; 
	} 
}; 
/* اختبار الدالة السابقة */
int main() 
{ 
	int i = 9; 
	cout << countSetBits(i); 
	return 0; 
}

• بايثون:

def countSetBits(n): 

	count = 0
	while (n): 
		n &= (n-1) 
		count+= 1
	
	return count 


# اختبار الدالة السابقة
i = 9
print(countSetBits(i))

• جافا:

import java.io.*; 

class countSetBits { 
	static int countSetBits(int n) 
	{ 
		int count = 0; 
		while (n > 0) { 
			n &= (n - 1); 
			count++; 
		} 
		return count; 
	} 

	// اختبار التابع السابق
	public static void main(String args[]) 
	{ 
		int i = 9; 
		System.out.println(countSetBits(i)); 
	} 
}

الطريقة التعاودية

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

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

int countSetBits(int n) 
{ 
	// الحالة الأساس
	if (n == 0) 
		return 0; 
	else
		return 1 + countSetBits(n & (n - 1)); 
} 

// اختبار الدالة السابقة
int main() 
{ 
	int n = 9; 

	cout << countSetBits(n); 

	return 0; 
}

• بايثون:

def countSetBits(n): 

	# الحالة الأساس 
	if (n == 0): 
		return 0
	else: 
		return 1 + countSetBits(n & (n - 1)) 
			
# اختبار الدالة السابقة
if __name__ == '__main__': 
	n = 9
	print(countSetBits(n))

• جافا:

import java.io.*; 

class GFG { 

	public static int countSetBits(int n) 
	{ 

		// الحالة الأساس
		if (n == 0) 
			return 0; 
		else
			return 1 + countSetBits(n & (n - 1)); 
	} 

	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 

		int n = 9; 

		System.out.println(countSetBits(n)); 
	} 
}

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

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

مصادر

• صفحة Count set bits in an integer في توثيق الخوارزميات في موقع GeeksforGeeks.