BIT MANIPULATION › BASIC BIT CONCEPTS
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Try it yourself first →A binary number is built from powers of two, just as a decimal number is built from powers of ten. When you divide an integer by 2, the remainder tells you whether its lowest binary bit is 0 or 1. The quotient contains all the higher binary places, so repeating the same operation walks through the representation one bit at a time.
The first remainder is the least significant bit, but the answer must begin with the most significant 1. Therefore, append each remainder as you divide, then reverse the collected characters. Because the process stops when the quotient becomes zero, it naturally stops immediately after the highest useful bit and never creates leading zeroes.
| MEASURE | BOUND | WHY |
|---|---|---|
| Time | O(log n) | Each iteration records one bit and replaces n with roughly half its previous value. The value therefore reaches zero after one iteration per binary place, and reversing the collected string touches each recorded bit once more. |
| Space | O(1) extra | The returned string contains O(log n) characters, but output storage is excluded from the working-space bound. The bits are reversed in place, so no additional structure grows with the input; the worst valid input simply produces the maximum 31-character output. |
#include <algorithm>
#include <string>
using namespace std;
class Solution {
public:
string decToBinary(int n) {
string bits;
while (n > 0) {
bits.push_back(char('0' + (n & 1)));
n >>= 1;
}
reverse(bits.begin(), bits.end());
return bits;
}
};The two bit operations have different jobs. n & 1 reads the bit that must be appended now, while n >>= 1 discards that bit and exposes the next one. Keeping those lines in this order matters: shifting first would lose the current lowest bit before it is recorded. The final reverse is required because extraction proceeds from low place to high place.
You can avoid collecting bits backward by first finding the largest power of two that does not exceed n. Then inspect powers of two from that value down to 1, appending 1 when the current power fits and subtracting it, or appending 0 otherwise. This has the same O(log n) time and O(1) extra space, but it needs an initial search and a second loop, so repeated division is usually the shorter solution.
#include <string>
using namespace std;
class Solution {
public:
string decToBinary(int n) {
int place = 1;
while (place <= n / 2) {
place *= 2;
}
string bits;
while (place > 0) {
if (n >= place) {
bits.push_back('1');
n -= place;
} else {
bits.push_back('0');
}
place /= 2;
}
return bits;
}
};