Decimal to Binary
Last Updated: June 7, 2026
Understanding the Problem
Binary is base 2, so every number is written using only 0 and 1, with each position carrying a power of two. Reading 1010 from right to left, the positions are worth 1, 2, 4, and 8. The set bits are the 2 and 8 positions, so 1010 is 8 + 2, which is 10 in decimal. Converting decimal to binary means finding which powers of two add up to the value and writing a 1 or 0 for each position.
The output is a string, not a number, and leading-zero rules matter. The string "101" and the string "0101" represent the same value, but the problem asks for the form with no leading zeros, so "101" is the only accepted answer for 5.
Two cases need attention. The first is 0. A loop that peels off bits by dividing the value down produces nothing for 0, leaving an empty string, so 0 is returned directly as "0". The second is bit order. Extracting bits naturally gives them from the least significant position, the opposite of how the string is read, so the order has to be corrected before returning.
Key Constraints:
ncan be0→ A divide-down loop produces no bits for0, leaving an empty string. Return"0"as a separate case.- No leading zeros → The result for any positive
nmust start with1. Building the string from the highest set bit downward, or trimming nothing because the divide method never emits a leading zero, both satisfy this. - Bit order → Extracting bits by remainder yields them least significant first. The string is read most significant first, so the collected bits must be reversed before returning.
Approach 1: Repeated Division by 2
Intuition
The last bit of a binary number is n % 2: it is 1 when n is odd and 0 when n is even. After recording that bit, dividing n by 2 shifts every bit one place to the right and discards the bit just read, leaving a smaller number whose last bit is the next one to record.
Repeating this peels off one bit per step, from least significant to most significant, until n reaches 0. The bits come out in reverse of how they are written, so the collected remainders are read back to front to form the answer. The value 0 produces no remainders, so it is handled before the loop as "0".
Algorithm
- If
nis0, return"0". - Create an empty buffer for the bits.
- While
nis greater than0, appendn % 2to the buffer, then setnton / 2. - Reverse the buffer.
- Return the buffer as a string.
Example Walkthrough
Input:
The value 10 is not 0, so the loop runs. 10 % 2 is 0, so the first recorded bit is 0, and 10 / 2 is 5. 5 % 2 is 1, so the next bit is 1, and 5 / 2 is 2. 2 % 2 is 0, so the next bit is 0, and 2 / 2 is 1. 1 % 2 is 1, so the next bit is 1, and 1 / 2 is 0. The loop stops. The bits were recorded in the order 0, 1, 0, 1, which is least significant first. Reading them in reverse gives 1, 0, 1, 0, so the result is "1010".
Code
- Time Complexity: O(b), where b is the number of bits in
n. Since the bit count grows with the logarithm of the value, this is O(log n). The loop runs once per bit, and the reversal touches each bit once more. - Space Complexity: O(b). The buffer holds one character per bit, so its size grows with the number of bits.
Approach 2: Bit Inspection (Shifting)
Intuition
Instead of peeling bits off the right end, this approach reads them left to right, the order they appear in the final string. The bit at position i is (n >> i) & 1: shifting right by i moves that bit into the lowest position, and the mask isolates it.
To produce the string with no leading zeros, the reading must start at the highest set bit rather than a fixed position like bit 31. The highest set bit is the largest i for which 2^i is less than or equal to n. Reading down from it to position 0 appends each bit in the correct order, so no reversal is needed. The value 0 has no set bit, so it is returned directly as "0".
Algorithm
- If
nis0, return"0". - Find the highest bit position
highsuch that(n >> high) & 1is1and no higher bit is set. - For
ifromhighdown to0, append(n >> i) & 1to the result. - Return the result as a string.
Example Walkthrough
Input:
The value 10 is not 0. The highest power of two that fits inside 10 is 8, which is 2^3, so the highest set bit is at position 3. Reading from position 3 down to position 0: (10 >> 3) & 1 is 1, (10 >> 2) & 1 is 0, (10 >> 1) & 1 is 1, and (10 >> 0) & 1 is 0. Appending these in order produces 1, 0, 1, 0, so the result is "1010" directly, with no reversal needed.
Code
- Time Complexity: O(b), where b is the number of bits in
n. Finding the highest set bit scans up through the bit positions, and reading the bits scans back down, each step proportional to the bit count, which is O(log n). - Space Complexity: O(b). The output string holds one character per bit, so its size grows with the number of bits.