15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Bit manipulation works directly on the binary digits of an integer, using AND, OR, XOR and shifts. Each operator acts on one aligned bit position at a time. For example, n & (n - 1) is 0 exactly when a positive n is a power of two, and it costs O(1) time.
| AND, OR, XOR | Result bit is 1 when both bits are 1, at least one is 1, or the bits differ |
|---|---|
| Shifts | n << 1 is n × 2 when it fits; n >> 1 is floor(n / 2); both for nonnegative n |
| Power of two | n > 0 and (n & (n - 1)) == 0 |
| Decimal to binary | Divide by 2, record remainders LSB first, reverse; O(log n) time |
| One bit operation | O(1) time and O(1) extra space for a fixed-width integer |
The lesson uses modular arithmetic’s division rule:
When dividing by 2, the remainder is either 0 or 1. That remainder is the lowest binary bit of .
Binary is positional notation. Bit position has weight .
The least significant bit (LSB) is position 0, on the right. It has the smallest weight. The most significant set bit is the leftmost bit equal to 1.
For a nonnegative integer, a binary representation is the sum of the weights at its set-bit positions.
| Position | 3 | 2 | 1 | 0 |
|---|---|---|---|---|
| Weight | ||||
| Bit | 1 | 1 | 0 | 0 |
Bitwise operators work one aligned bit position at a time.
| Operator | Result bit is 1 when... |
|---|---|
a & b AND | both bits are 1 |
a | b OR | at least one bit is 1 |
a ^ b XOR | the two bits differ |
For nonnegative integers:
n << 1 moves each bit one position left. This corresponds to when the result is representable.n >> 1 discards the LSB. This corresponds to .These shift rules are limited to nonnegative integers. A bounded integer type can overflow on a left shift. Signed right shifts for negative values depend on the selected language and its rules.
Use:
Write 12 in binary by selecting its place values:
So its bits at weights are:
The rightmost bit is the LSB. For , it is 0.
The leftmost set bit has weight .
Inspect the bit operations with fixed-width, four-bit notation:
| Expression | Four-bit result | Meaning |
|---|---|---|
| Both numbers have the 8-bit set. | ||
| A bit is set if either row has it set. | ||
| A bit is set where the rows differ. | ||
| , if representable. | ||
| . |
The main question is whether 12 is a power of two.
A positive power of two has exactly one set bit:
But has two set bits, so it should fail the test.
Repeated division by 2 discovers binary digits from right to left.
12 in binary is 1100: halving collects the bits lowest first, then you reverse them. And n AND n − 1 gives 1000 for 12, not zero, so 12 is not a power of two.
Start with current = 12. At each step:
current by 2.current with the quotient.| Step | Division | Quotient becomes | Remainder recorded | Recorded bits, LSB first |
|---|---|---|---|---|
| Start | — | 12 | — | empty |
| 1 | 6 | 0 | 0 | |
| 2 | 3 | 0 | 0, 0 | |
| 3 | 1 | 1 | 0, 0, 1 | |
| 4 | 0 | 1 | 0, 0, 1, 1 |
The first remainder is the LSB, so the recorded order is backwards for normal binary writing.
Reverse the recorded bits:
Therefore:
Now perform the power-of-two check.
First subtract 1:
Then AND the aligned bits:
| Bit position | 3 | 2 | 1 | 0 |
|---|---|---|---|---|
| 1 | 1 | 0 | 0 | |
| 1 | 0 | 1 | 1 | |
| AND | 1 | 0 | 0 | 0 |
The result is not zero. Therefore 12 is not a power of two.
After each division step, the remainders already recorded describe the low-order part of the original number.
The quotient is what remains to process, and the recorded remainders already account for the rightmost binary positions.
More precisely, after recording remainders:
Check the statement on the example.
| Recorded remainders | Current quotient | Check |
|---|---|---|
| none | 12 | |
0 | 6 | |
0, 0 | 3 | |
0, 0, 1 | 1 | |
0, 0, 1, 1 | 0 |
At termination, the quotient is 0. The recorded bits represent the entire original number. They were recorded from low order to high order, which is why reversing them produces the usual binary string.
For the power-of-two test, use a different fact:
There is no position where both numbers have a 1. Their AND is zero.
If a positive number is not a power of two, it has at least two set bits. Subtracting 1 clears its lowest set bit, but at least one higher set bit remains unchanged. That higher bit is set in both and , so the AND is nonzero.
The state trace gives the procedure:
"0".current mod 2 as the next binary digit,current with floor(current / 2).The value 12 takes four divisions because it has four binary digits.
A number must first be positive.
Then evaluate:
n has exactly one set bit and is a power of two.The condition n > 0 is required. Zero has no set bits, and:
would otherwise incorrectly classify 0 as a power of two.
reverseDigits(digits):
'0' or '1'.digits.1function toBinary(n):
2 input: nonnegative integer n
3 returns: the exact binary string for n
4 mutation: does not mutate n
5
61. if n == 0:
72. return "0"
8
93. digits = empty sequence of characters
104. current = n
11
125. while current > 0:
136. remainder = current mod 2
147. append character('0' + remainder) to digits
158. current = floor(current / 2)
16
179. return string(reverseDigits(digits))1function isPowerOfTwo(n):
2 input: nonnegative integer n
3 returns: true exactly when n is a positive power of two
4 mutation: does not mutate n
5
61. if n == 0:
72. return false
8
93. return (n & (n - 1)) == 0The expression on line 3 uses bitwise AND, not logical AND.
Trace toBinary(12) line by line.
| Executed line | n | current | remainder | digits | Result |
|---|---|---|---|---|---|
| 1 | 12 | — | — | — | n == 0 is false |
| 3 | 12 | — | — | empty | create storage |
| 4 | 12 | 12 | — | empty | copy input into current |
| 5 | 12 | 12 | — | empty | enter: |
| 6 | 12 | 12 | 0 | empty | |
| 7 | 12 | 12 | 0 | 0 | append LSB |
| 8 | 12 | 6 | 0 | 0 | |
| 5 | 12 | 6 | 0 | 0 | enter: |
| 6 | 12 | 6 | 0 | 0 | |
| 7 | 12 | 6 | 0 | 0, 0 | append next bit |
| 8 | 12 | 3 | 0 | 0, 0 | |
| 5 | 12 | 3 | 0 | 0, 0 | enter: |
| 6 | 12 | 3 | 1 | 0, 0 | |
| 7 | 12 | 3 | 1 | 0, 0, 1 | append next bit |
| 8 | 12 | 1 | 1 | 0, 0, 1 | |
| 5 | 12 | 1 | 1 | 0, 0, 1 | enter: |
| 6 | 12 | 1 | 1 | 0, 0, 1 | |
| 7 | 12 | 1 | 1 | 0, 0, 1, 1 | append next bit |
| 8 | 12 | 0 | 1 | 0, 0, 1, 1 | |
| 5 | 12 | 0 | 1 | 0, 0, 1, 1 | stop: is false |
| 9 | 12 | 0 | 1 | 0, 0, 1, 1 | reverse to "1100" |
So:
1toBinary(12) returns "1100"Now trace isPowerOfTwo(12).
| Executed line | Expression | Value |
|---|---|---|
| 1 | n == 0 | false |
| 3 | n - 1 | |
| 3 | n & (n - 1) | |
| 3 | (1000₂ == 0) | false |
So:
1isPowerOfTwo(12) returns falsetoBinaryLet the original input be original_n.
The loop invariant is:
where is the number of recorded remainders.
Initialization. Before the loop, current = original_n and no remainders have been recorded. The recorded value is 0, so:
The invariant holds.
Preservation. Suppose the invariant holds before an iteration. The algorithm computes:
where is either 0 or 1, q = floor(current / 2), and r = current mod 2.
The remainder is exactly the bit at the next low-order position. Appending it extends the recorded bit sequence by one binary position. Replacing current by leaves the invariant true with one more recorded bit.
Termination. The loop stops when current = 0. The invariant then becomes:
Thus the recorded bits represent the original number. They were found from least significant to most significant, so reversing them returns the conventional binary representation.
For n = 0, the algorithm returns "0" directly, which is its binary representation.
isPowerOfTwoIf n is a positive power of two. Then for some , so its binary form has one set bit:
Subtracting 1 gives:
No bit is set in both values. Therefore:
The function returns true.
If n is positive but not a power of two. Then it has at least two set bits. Subtracting 1 clears the least significant set bit. Every set bit above it remains set. Since there is at least one such higher set bit, and share a set bit. Therefore:
The function returns false.
Zero. The function explicitly returns false for n = 0, so zero is not misclassified.
Therefore, isPowerOfTwo(n) returns true exactly for positive powers of two.
For , a binary number has:
digits.
toBinaryEach loop iteration performs one remainder operation, one append, and one division by 2. The loop runs once per binary digit.
For n = 12, there are four binary digits, so there are four iterations.
Therefore:
The special case n = 0 performs constant work.
isPowerOfTwoThe function performs:
Under the fixed-width integer-operation model, each operation is constant time.
Therefore:
The same fixed-width model treats one AND, OR, XOR, left shift, or right shift as time and auxiliary space.
Incorrect line:
1return (n & (n - 1)) == 0Smallest exposing input:
1n = 0Wrong state:
Wrong result:
1trueCorrection:
1if n == 0:
2 return false
3return (n & (n - 1)) == 0Incorrect assumption: The first remainder is the leftmost binary digit.
Exposing input:
1n = 6Division gives remainders:
The discovered sequence is:
10, 1, 1Wrong result:
1"011"Correct result:
1"110"Correction: Remainders arrive LSB first. Reverse the sequence before returning it.
Incorrect line:
1return (n && (n - 1)) == 0Exposing input:
1n = 12
2n - 1 = 11Logical AND combines truth values. Since both 12 and 11 are nonzero, it produces a Boolean value rather than the bit mask .
Wrong result: A Boolean operation is performed instead of computing:
Correction: Use the language’s bitwise AND operator:
1return (n & (n - 1)) == 0Incorrect claim:
1n >> 1 always equals floor(n / 2)Exposing input: A negative integer in a language whose signed right shift is implementation-specific or sign-extending.
Wrong assumption: The nonnegative-integer rule is applied outside its stated boundary.
Correction: Restrict the lesson’s shift statement to nonnegative integers:
Incorrect assumption: A left shift always safely computes multiplication by 2.
Exposing input: A value whose left shift cannot be represented by the selected bounded integer type.
Wrong state: The result exceeds the type’s capacity.
Correction: Check capacity before shifting, or follow the selected language’s defined overflow-handling rules.
Implement these two functions:
1isPowerOfTwo(n)Contract:
true exactly when n is a positive power of two.0, 1, powers of two, and nearby non-powers.1toBinary(n)Contract:
n >= 0.n."0" for 0.Tests verify 0, 1, powers of two, nearby non-powers, and exact binary strings.
For background on using binary decomposition when processing values by their bits, see Binary exponentiation.
1def to_binary(n):
2 if n == 0:
3 return "0"
4 digits = []
5 current = n
6 while current > 0:
7 digits.append(str(current % 2)) # remainders arrive LSB first
8 current //= 2
9 return "".join(reversed(digits))
10
11def is_power_of_two(n):
12 if n == 0:
13 return False
14 return (n & (n - 1)) == 0 # bitwise AND, not logical
15
16print("toBinary(12) =", to_binary(12))
17print("12 & 11 =", 12 & 11)
18print("isPowerOfTwo(12) =", str(is_power_of_two(12)).lower())
19print("isPowerOfTwo(16) =", str(is_power_of_two(16)).lower())
20print("isPowerOfTwo(0) =", str(is_power_of_two(0)).lower())1public class Main {
2 static String toBinary(int n) {
3 if (n == 0) return "0";
4 StringBuilder digits = new StringBuilder();
5 int current = n;
6 while (current > 0) {
7 digits.append((char) ('0' + current % 2)); // remainders arrive LSB first
8 current /= 2;
9 }
10 return digits.reverse().toString();
11 }
12
13 static boolean isPowerOfTwo(int n) {
14 if (n == 0) return false;
15 return (n & (n - 1)) == 0; // bitwise AND, not logical
16 }
17
18 public static void main(String[] args) {
19 System.out.println("toBinary(12) = " + toBinary(12));
20 System.out.println("12 & 11 = " + (12 & 11));
21 System.out.println("isPowerOfTwo(12) = " + isPowerOfTwo(12));
22 System.out.println("isPowerOfTwo(16) = " + isPowerOfTwo(16));
23 System.out.println("isPowerOfTwo(0) = " + isPowerOfTwo(0));
24 }
25}1#include <algorithm>
2#include <iostream>
3#include <string>
4using namespace std;
5
6string toBinary(unsigned n) {
7 if (n == 0) return "0";
8 string digits;
9 unsigned current = n;
10 while (current > 0) {
11 digits += char('0' + current % 2); // remainders arrive LSB first
12 current /= 2;
13 }
14 reverse(digits.begin(), digits.end());
15 return digits;
16}
17
18bool isPowerOfTwo(unsigned n) {
19 if (n == 0) return false;
20 return (n & (n - 1)) == 0; // bitwise AND, not logical
21}
22
23int main() {
24 cout << boolalpha;
25 cout << "toBinary(12) = " << toBinary(12) << endl;
26 cout << "12 & 11 = " << (12 & 11) << endl;
27 cout << "isPowerOfTwo(12) = " << isPowerOfTwo(12) << endl;
28 cout << "isPowerOfTwo(16) = " << isPowerOfTwo(16) << endl;
29 cout << "isPowerOfTwo(0) = " << isPowerOfTwo(0) << endl;
30}1function toBinary(n) {
2 if (n === 0) return "0";
3 const digits = [];
4 let current = n;
5 while (current > 0) {
6 digits.push(String(current % 2)); // remainders arrive LSB first
7 current = Math.floor(current / 2);
8 }
9 return digits.reverse().join("");
10}
11
12function isPowerOfTwo(n) {
13 if (n === 0) return false;
14 return (n & (n - 1)) === 0; // bitwise AND, not logical
15}
16
17console.log("toBinary(12) = " + toBinary(12));
18console.log("12 & 11 = " + (12 & 11));
19console.log("isPowerOfTwo(12) = " + isPowerOfTwo(12));
20console.log("isPowerOfTwo(16) = " + isPowerOfTwo(16));
21console.log("isPowerOfTwo(0) = " + isPowerOfTwo(0));No. Bit masking is one technique inside bit manipulation: you build a mask and apply it with AND, OR or XOR to read, set or clear chosen bits. Bit manipulation also covers shifts and tricks such as n & (n - 1).
Bitwise operations take O(1) time on a fixed-width integer. They give short tests such as the power-of-two check and compact ways to store many yes/no flags in one integer.
A power of two has one set bit, and subtracting 1 clears it and sets every lower bit, so the AND is 0. Any other positive number keeps a higher set bit in both values. 12 & 11 = 1000, which is 8, not 0.
Test bit i with (n >> i) & 1. Set it with n | (1 << i), clear it with n & ~(1 << i), and toggle it with n ^ (1 << i). Check the lowest bit with n & 1.
Because 0 & (0 - 1) is 0, so without the check zero would be reported as a power of two.