Power of Two कैसे चेक करें

दो की एक power, जैसे 1, 2, 4, 8, में बिल्कुल एक light switch on है, और इसके लिए एक neat quick check है।

In this page:

Power of Two Idea
Bit Trick
Zero and Negative Values
Finding Powers
Practice

Syntax

markup

is_power_of_two = n > 0 and (n & (n - 1)) == 0

Power of Two Idea

दो की एक positive power (1, 2, 4, 8, 16, ...) के binary representation में बिल्कुल एक bit set है — उदाहरण के लिए 8 binary में 1000 है — जो वह property है जिस पर हर power-of-two check निर्भर करता है।

उदाहरण: Power of Two Idea

#include <iostream>
using namespace std;
int main() {
	int n = 8;
	cout << n << " in binary is 1000 -- exactly one bit set, the property every power-of-two check relies on";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 8;
		System.out.println(n + " in binary is 1000 -- exactly one bit set, the property every power-of-two check relies on");
	}
}

n = 8
print(f"{n} in binary is 1000 -- exactly one bit set, the property every power-of-two check relies on")

#include <stdio.h>
int main() {
	int n = 8;
	printf("%d in binary is 1000 -- exactly one bit set, the property every power-of-two check relies on", n);
	return 0;
}

Bit Trick

एक positive n के लिए, expression n & (n - 1) lowest set bit clear करता है; अगर n में शुरू में सिर्फ एक set bit था, वह expression बिल्कुल zero बन जाता है, यह एक one-line test देते हुए कि n दो की power है या नहीं।

उदाहरण: Bit Trick

#include <iostream>
using namespace std;
int main() {
	int n = 8;
	bool isPow2 = n > 0 && (n & (n-1)) == 0;
	cout << n << " & (n-1) == 0 -- is power of two: " << isPow2;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 8;
		boolean isPow2 = n > 0 && (n & (n-1)) == 0;
		System.out.println(n + " & (n-1) == 0 -- is power of two: " + isPow2);
	}
}

n = 8
is_pow2 = n > 0 and (n & (n-1)) == 0
print(f"{n} & (n-1) == 0 -- is power of two: {is_pow2}")

#include <stdio.h>
int main() {
	int n = 8;
	int isPow2 = n > 0 && (n & (n-1)) == 0;
	printf("%d & (n-1) == 0 -- is power of two: %s", n, isPow2 ? "true" : "false");
	return 0;
}

Zero and Negative Values

यह bit trick मानता है कि n एक positive integer है — zero में बिल्कुल कोई set bits नहीं इसलिए इसे दो की power नहीं माना जाता, और negative numbers एक अलग binary representation (two's complement) उपयोग करते हैं जहां trick का वही मतलब नहीं होता।

उदाहरण: Zero and Negative Values

#include <iostream>
using namespace std;
int main() {
	int n = 0;
	bool isPow2 = n > 0 && (n & (n-1)) == 0;
	cout << "n=0 has no set bits, the n>0 guard correctly rejects it: isPow2=" << isPow2;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 0;
		boolean isPow2 = n > 0 && (n & (n-1)) == 0;
		System.out.println("n=0 has no set bits, the n>0 guard correctly rejects it: isPow2=" + isPow2);
	}
}

n = 0
is_pow2 = n > 0 and (n & (n-1)) == 0
print(f"n=0 has no set bits, the n>0 guard correctly rejects it: is_pow2={is_pow2}")

#include <stdio.h>
int main() {
	int n = 0;
	int isPow2 = n > 0 && (n & (n-1)) == 0;
	printf("n=0 has no set bits, the n>0 guard correctly rejects it: isPow2=%s", isPow2 ? "true" : "false");
	return 0;
}

Finding Powers

1 से शुरू करके और बार-बार एक position left shift करना सीधे दो की powers की sequence generate करता है (1, 2, 4, 8, ...), जो अक्सर यह है कि code एक lookup table कैसे बनाता है या candidate powers में कैसे iterate करता है।

उदाहरण: Finding Powers

#include <iostream>
using namespace std;
int main() {
	int p = 1;
	for (int i = 0; i < 5; i++) { cout << p << " "; p <<= 1; }
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int p = 1;
		for (int i = 0; i < 5; i++) { System.out.print(p + " "); p <<= 1; }
	}
}

p = 1
for i in range(5):
    print(p, end=" ")
    p <<= 1

#include <stdio.h>
int main() {
	int p = 1;
	for (int i = 0; i < 5; i++) { printf("%d ", p); p <<= 1; }
	return 0;
}

Practice

Power-of-two checks binary alignment के लिए optimized array या buffer sizes validate करने, bitmask capacities चुनने, और किसी भी binary-search-style algorithm के लिए मायने रखते हैं जो एक power-of-two-sized range मानता है।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Validating buffer sizes for binary alignment, choosing bitmask capacities, binary-search assumptions";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Validating buffer sizes for binary alignment, choosing bitmask capacities, binary-search assumptions");
	}
}

print("Validating buffer sizes for binary alignment, choosing bitmask capacities, binary-search assumptions")

#include <stdio.h>
int main() {
	printf("Validating buffer sizes for binary alignment, choosing bitmask capacities, binary-search assumptions");
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Count Set Bits Next Lesson → XOR Problems