Set Bits कैसे Count करें

Set bits count करना यह count करने जैसा है कि एक row में कितनी light switches on हैं।

In this page:

Set Bit Meaning
Loop Method
Brian Kernighan Method
Language Helpers
Practice

Syntax

markup

count = 0
while n:
    n &= n - 1    # clear the lowest set bit
    count += 1

Set Bit Meaning

एक 'set bit' बस एक bit को represent करती है जिसकी value 0 के बजाय 1 है — set bits count करने का मतलब है count करना कि किसी number के binary representation में कितने 1s दिखते हैं, कभी-कभी इसका 'population count' कहलाता है।

उदाहरण: Set Bit Meaning

#include <iostream>
using namespace std;
int main() {
	int n = 11;
	cout << n << " (binary 1011) has 3 set bits -- its population count is 3";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 11;
		System.out.println(n + " (binary 1011) has 3 set bits -- its population count is 3");
	}
}

n = 11
print(f"{n} (binary 1011) has 3 set bits -- its population count is 3")

#include <stdio.h>
int main() {
	int n = 11;
	printf("%d (binary 1011) has 3 set bits -- its population count is 3", n);
	return 0;
}

Loop Method

सबसे direct method हर bit position एक समय में एक जांचता है (shifting और masking, या बार-बार divide करके remainders लेते हुए), एक 1 bit मिलने पर हर बार एक counter increment करते हुए, जो value में bits की संख्या के अनुपात में time लेता है।

उदाहरण: Loop Method

#include <iostream>
using namespace std;
int main() {
	int n = 11, count = 0;
	while (n) { count += n & 1; n >>= 1; }
	cout << "Set bits counted by checking each position: " << count;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 11, count = 0;
		while (n != 0) { count += n & 1; n >>= 1; }
		System.out.println("Set bits counted by checking each position: " + count);
	}
}

n = 11
count = 0
while n:
    count += n & 1
    n >>= 1
print("Set bits counted by checking each position:", count)

#include <stdio.h>
int main() {
	int n = 11, count = 0;
	while (n) { count += n & 1; n >>= 1; }
	printf("Set bits counted by checking each position: %d", count);
	return 0;
}

Brian Kernighan Method

Brian Kernighan की trick n & (n - 1) compute करती है, जो हमेशा n का बिल्कुल lowest set bit clear करता है; इसे दोहराना और यह count करना कि zero पहुंचने में कितनी बार लगे set bits को सीधे count करता है, सिर्फ 1 bits की संख्या के अनुपात में काम करते हुए total bit width के बजाय।

उदाहरण: Brian Kernighan Method

#include <iostream>
using namespace std;
int main() {
	int n = 11, count = 0;
	while (n) { n &= (n-1); count++; }
	cout << "n & (n-1) clears lowest set bit each time, iterations = " << count;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 11, count = 0;
		while (n != 0) { n &= (n-1); count++; }
		System.out.println("n & (n-1) clears lowest set bit each time, iterations = " + count);
	}
}

n = 11
count = 0
while n:
    n &= (n-1)
    count += 1
print("n & (n-1) clears lowest set bit each time, iterations =", count)

#include <stdio.h>
int main() {
	int n = 11, count = 0;
	while (n) { n &= (n-1); count++; }
	printf("n & (n-1) clears lowest set bit each time, iterations = %d", count);
	return 0;
}

Language Helpers

कई languages इस exact operation के लिए एक built-in, hardware-accelerated function प्रदान करती हैं (जैसे C++ में __builtin_popcount या Java में Integer.bitCount), जो आमतौर पर किसी भी hand-written loop से तेज़ है।

उदाहरण: Language Helpers

#include <iostream>
using namespace std;
int main() {
	int n = 11;
	cout << "__builtin_popcount(" << n << ") = " << __builtin_popcount(n);
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 11;
		System.out.println("Integer.bitCount(" + n + ") = " + Integer.bitCount(n));
	}
}

n = 11
print(f"bin(n).count('1') = {bin(n).count('1')}")

#include <stdio.h>
int main() {
	int n = 11;
	printf("__builtin_popcount(%d) = %d", n, __builtin_popcount(n));
	return 0;
}

Practice

Set bits count करना subsets वाली problems में दिखता है (क्योंकि एक bitmask का set-bit count आपको subset का size बताता है), checksums, और विभिन्न bit-manipulation puzzles में जो एक binary number के weight के बारे में पूछते हैं।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "A bitmask's set-bit count tells you the represented subset's size";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("A bitmask's set-bit count tells you the represented subset's size");
	}
}

print("A bitmask's set-bit count tells you the represented subset's size")

#include <stdio.h>
int main() {
	printf("A bitmask's set-bit count tells you the represented subset's size");
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Common Bit Tricks Next Lesson → Power of Two