16 Power of 2
- Because
- 2 × 2 × 2 × 2 = 16
Check Power of 2 in C
What you’ll learn
- Which numbers count as powers of two (1, 2, 4, 8, 16…) and why that matters in computing.
- The classic bit test
n & (n - 1), explained without assuming you already love binary. - Two complete C programs: test one value, then list every power of two from 1 to 20.
- A live preview, a divide-by-two loop alternative, and usual edge cases.
Overview
Start with 1. Multiply by 2 each step: 1, 2, 4, 8, 16, 32, … Those are powers of two. The job is to tell whether a given positive integer appears in that list. The fast C trick looks at the number’s binary shape: powers of two are exactly the positive integers whose binary form has one single 1 and the rest 0s.
Bitwise test
One line: positive and (n & (n - 1)) == 0. The page unpacks what that means.
Live preview
Try 16, 12, or 1 before compiling.
Range listing
Second program prints 1 2 4 8 16 for numbers 1–20, matching the classic homework output.
Prerequisites
Tiny C programs, if, and (for the fast version) the idea that & can mean “bitwise AND,” not “address of.”
#include <stdio.h>,int main(void),printf, and integer comparisons.- Optional comfort: counting in binary (1, 10, 100, 1000 for 1, 2, 4, 8).
What is a power of 2?
A power of two is any value 2k where k is a whole number and k ≥ 0. So the list begins 1, 2, 4, 8, 16, 32, …
You can also think: start at 1 and keep doubling. If you ever land on your target, it is a power of two. If you skip over it or never hit it exactly, it is not.
Why the n & (n - 1) trick works
Write n in binary. Subtracting 1 borrows from the lowest 1 bit: that bit becomes 0, and every bit to its right flips to 1. If n had exactly one 1 bit (true for powers of two), then n - 1 has 0 everywhere n had 1. The bitwise AND then lines up zeros with that single one and the result is all zeros.
Mini example:
n = 8- Binary for 8 is
1000(one lonely1). n - 1 = 7is0111in binary.- AND pairs bits:
1000 & 0111 = 0000. So(n & (n - 1)) == 0.
Why also check
n > 0?Zero is not a power of two in this tutorial’s definition, and the n - 1 pattern is awkward for negative numbers. The condition n > 0 keeps the story clean.
Quick examples
12 Not
- Because
- Doubling: 1, 2, 4, 8, 16 — you jump past 12.
1 Power of 2
- Because
- 20 = 1 (start before any doubling).
Live preview
Uses the same rule as the C samples for JavaScript safe integers: positive and (n & (n - 1)) === 0. For small n it also shows a short binary string so the “one 1 bit” idea is visible.
Algorithm
Goal: decide whether a positive integer n equals 2k for some k ≥ 0.
Bitwise method (used in the programs)
Reject non-positive
If n <= 0, return false.
Clear the lowest 1 bit test
Compute n & (n - 1). If the result is 0, n had at most one 1 bit; together with n > 0, that means exactly one 1 bit — a power of two.
Loop method (same idea, no bitwise homework)
If n == 1, true. While n is even and n > 1, replace n with n / 2. If you finish at 1, it was a power of two; if you stop on an odd number greater than 1, it was not.
📜 Pseudocode
Pseudocode
function isPowerOfTwoBitwise(n):
if n <= 0:
return false
return (n & (n - 1)) = 0
function isPowerOfTwoLoop(n):
if n <= 0:
return false
while n > 1 and n mod 2 = 0:
n ← n / 2
return n = 11
Check a single number
Classic interview one-liner: require n > 0, then use n & (n - 1). Change number or read with scanf.
c
#include <stdio.h>
int isPowerOfTwo(int num) {
return (num > 0) && ((num & (num - 1)) == 0);
}
int main(void) {
int number = 16;
if (isPowerOfTwo(number)) {
printf("%d is a power of 2.\n", number);
} else {
printf("%d is not a power of 2.\n", number);
}
return 0;
}Explanation
(num > 0) && ...Guard. Rules out zero and negatives before touching num - 1 in a way that would muddy the pattern.
(num & (num - 1)) == 0Single 1-bit test. For positive num, this is zero exactly when num is 1, 2, 4, 8, …
2
Powers of 2 from 1 to 20
Reuses the same helper. The old reference included <math.h> but never used it — this version stays stdio-only.
c
#include <stdio.h>
int isPowerOfTwo(int num) {
return (num > 0) && ((num & (num - 1)) == 0);
}
int main(void) {
printf("Power of 2 in the range 1 to 20:\n");
for (int i = 1; i <= 20; ++i) {
if (isPowerOfTwo(i)) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}Explanation
The outer loop tries every i. Only 1, 2, 4, 8, 16 pass inside 1–20 because the next power, 32, is larger than 20.
Notes
Equivalent form. Some codebases write num && !(num & (num - 1)). For integers, that is another way to spell “nonzero and a single 1 bit” — the extra ! flips the zero compare.
Logarithms. You can test whether log2(n) is an integer using <math.h>, but floating rounding hurts huge integers. Prefer bits or the divide-by-two loop for exactness.
Interview: say “positive integer with exactly one set bit” out loud, then show n & (n-1).
❓ FAQ
It is a whole number you can write as 2 multiplied by itself some whole number of times. Examples: 1 (because 2^0 = 1), 2, 4, 8, 16, 32… Non-examples: 3, 5, 6, 12.
Yes. By convention 2^0 = 1, so the sequence usually starts 1, 2, 4, 8, 16… The programs on this page treat 1 as a power of 2.
In binary, subtracting 1 flips the lowest 1 bit and every 0 to its right. If n has exactly one 1 bit, that clears the only 1 and the AND with n becomes zero. If n has zero or more than one 1 bit, the test fails.
Zero would make n - 1 negative, and the neat bit pattern story breaks for the interview form. Negative numbers are not counted as powers of two here.
Yes. While n is even and n > 1, divide n by 2. If you end at 1, it was a power of two. Handle n == 1 separately; reject n <= 0.
No. Every power of two after 1 is even, but many even numbers (like 6) are not powers of two.
🔄 Input / output examples
Example 1 prints one line. Use scanf("%d", &number); for interactive runs.
Input number | Typical line (Example 1) |
|---|---|
| 16 | 16 is a power of 2. |
| 12 | 12 is not a power of 2. |
| 1 | 1 is a power of 2. |
| 0 | 0 is not a power of 2. |
Edge cases
Most bugs come from forgetting the n > 0 guard or mixing up bitwise & with logical &&.
n = 0Zero
Not a power of two here. Without num > 0, the bitwise story is misleading.
Negatives
Signed integers
Reject n <= 0 for this lesson. Extending the definition to negatives is not standard for “power of two” in interviews.
& vs &&Bitwise vs logical
num & (num - 1) uses bitwise AND on integers. The outer test often uses && so short-circuiting can skip work when num is zero (style varies; both guards are fine if written clearly).
⏱️ Time and space complexity
| Approach | Time (single n) | Extra space |
|---|---|---|
Bitwise n & (n-1) | O(1) | O(1) |
| Divide by 2 loop | O(log n) | O(1) |
Scan [1, U] with per-value test | O(U) | O(1) |
Summary
- Idea: powers of two are
1, 2, 4, 8, …— positive integers with a single1in binary. - Code:
(n > 0) && ((n & (n - 1)) == 0)is the usual constant-time test. - Fallback: keep halving even numbers; you should finish at
1only for powers of two.
Did you know?
Many sizes in computing are powers of two: bytes group into kilobytes, memory chips, and texture widths. That is why “is this number a power of two?” shows up beside bit masks, alignment, and binary trees.
About the author
8 people found this page helpful