Learn Power of Two — Free DSA Tutorial

Power of Two Idea

A positive power of two (1, 2, 4, 8, 16, ...) has exactly one bit set in its binary representation — for example 8 is 1000 in binary — which is the property every power-of-two check relies on.

Example: 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

For a positive n, the expression n & (n - 1) clears the lowest set bit; if n only had one set bit to begin with, that expression becomes exactly zero, giving a one-line test for whether n is a power of two.

Example: 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

This bit trick assumes n is a positive integer — zero has no set bits at all so it isn't considered a power of two, and negative numbers use a different binary representation (two's complement) where the trick doesn't mean the same thing.

Example: 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

Starting from 1 and repeatedly shifting left by one position generates the sequence of powers of two directly (1, 2, 4, 8, ...), which is often how code builds a lookup table or iterates through candidate powers.

Example: 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 matter for things like validating array or buffer sizes optimized for binary alignment, choosing bitmask capacities, and any binary-search-style algorithm that assumes a power-of-two-sized range.

Example: 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;
}

Power of Two

Power of Two Idea

Bit Trick

Zero and Negative Values

Finding Powers

Practice

Chapter Quiz — Complete all 5 topics to unlock

Login to run this code