Decimal to Binary

Q: Can you convert to binary with bit operations instead of division?

Yes. n & 1 gives the lowest bit and n >> 1 drops it, which is the same as n % 2 and n / 2 for non-negative numbers. The loop and the reversal stay the same. Division is easier to explain, while the shift version is common in low level code.

BeginnerMath and simulation Bit manipulation

+10

You get a non-negative integer n. Return its binary representation as a string of 0s and 1s, with no leading zeros. The only number whose answer starts with 0 is zero itself, which is written "0".

Function

toBinary(n: integer) → string

ninteger: the number to convert
Returnsstring: the binary digits of n as a string

Constraints

0 ≤ n ≤ 2³¹-1
Build the string yourself instead of calling a built-in base conversion.

Examples

Input: n = 13
Output: "1101"
Explanation: 13 = 8 + 4 + 1. The places for 8, 4, 2 and 1 hold 1, 1, 0 and 1, which reads 1101.

Input: n = 0
Output: "0"
Explanation: Zero has no set bits, but the answer still needs one digit, so it is "0" rather than an empty string.

Input: n = 64
Output: "1000000"
Explanation: 64 is 2^6, a single 1 in the 64s place followed by six 0s for the places 32 down to 1.

+16 hidden tests on Submit

Follow-up

Can you convert n to any base from 2 to 16 with the same loop, using the letters a to f for the digits above 9?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A binary number is a sum of powers of two, and each digit says whether one power is in the sum. You can decide the digits from the top by subtracting powers of two, or read them off from the bottom as the remainders of repeated division by 2. The division loop is the standard method: it never has to find the largest power first, and it works the same way for every base.

Subtract powers of two from the top

Intuition

This is how you convert by hand. Find the largest power of two that fits into n; that is the first digit, a 1. Then go down one power at a time. If the power still fits into what is left, write 1 and subtract it; otherwise write 0.

For 13 the largest power is 8. Write 1 and keep 5. Then 4 fits (1, keep 1), 2 does not (0), and 1 fits (1). The digits read 1101. The first digit is always a 1, so no leading zero can appear.

Finding the largest power needs care. Doubling power until it passes n overflows a 32-bit integer once n ≥ 2^30, because the next power is 2^31. Doubling only while power ≤ n / 2 stops at the right power without ever going past n. A 31-bit number takes 31 steps, which is O(log n).

Algorithm

If n is 0, return "0".
Start power at 1 and double it while power ≤ n / 2.
While power > 0: if n ≥ power, append 1 and subtract power from n; otherwise append 0.
Halve power and repeat.
Return the digits you appended.

def toBinary(n):
    if n == 0:
        return "0"
    # Largest power of two that is at most n. Comparing with n // 2 avoids overflow.
    power = 1
    while power <= n // 2:
        power *= 2
    bits = []
    while power > 0:
        if n >= power:
            bits.append("1")
            n -= power
        else:
            bits.append("0")
        power //= 2
    return "".join(bits)

Repeated division by 2

Intuition

The last binary digit of n says whether n is odd, which is n % 2. Dividing by 2 and dropping the remainder shifts every digit one place to the right, so the next digit becomes the last one. Repeat until nothing is left and you collect every digit, lowest first.

For 13: 13 leaves remainder 1, 6 leaves 0, 3 leaves 1, and 1 leaves 1, then the number is 0. The remainders in order are 1, 0, 1, 1; reversed they read 1101. The loop stops when the number reaches 0, so the highest digit it writes is always a 1 and no leading zero appears. Zero itself never enters the loop, which is why it needs its own check.

Each step halves the number, so a 31-bit value takes 31 steps, O(log n) time, and the string of digits is O(log n) space.

Algorithm

If n is 0, return "0".
While n > 0, append n % 2 as a digit and set n to n / 2, rounded down.
Reverse the digits, because they came out lowest first.
Return them as a string.

def toBinary(n):
    if n == 0:
        return "0"
    bits = []
    while n > 0:
        # The remainder is the lowest bit that is left.
        bits.append(str(n % 2))
        n //= 2
    # The bits came out lowest first, so turn them around.
    bits.reverse()
    return "".join(bits)

Pitfalls and edge cases

The loop is short, and most wrong answers come from its two ends.

Returning an empty string for 0. The division loop never runs for zero, so check it first.
Forgetting to reverse. The remainders arrive lowest digit first, so 6 comes out as 011 instead of 110.
Using / in a language where it returns a fraction, such as JavaScript, Lua or PHP. 13 / 2 must become 6, so round down or use integer division.
Building the largest power by doubling past n. For n = 2^31-1 the next power, 2^31, does not fit in a 32-bit integer.
Allocating too little in C. A 31-bit number needs 31 characters plus the terminating '\0'.

Frequently asked questions4

How do you convert a decimal number to binary?

Divide the number by 2 again and again, writing down each remainder, until the number reaches 0. Read the remainders from the last one to the first. For 13 the remainders are 1, 0, 1, 1, so 13 in binary is 1101.

Why are the remainders read in reverse order?

The first division by 2 tells you whether the number is odd, which is the last binary digit. Each later division reveals the next digit to the left. So the remainders come out lowest digit first, and you reverse them to write the number the usual way.

What is the time complexity of converting decimal to binary?

Each step halves the number, so the loop runs once per binary digit, which is about log2(n) times. That is O(log n) time, and the answer string takes O(log n) space. For a 32-bit integer this is at most 31 steps.

Can you convert to binary with bit operations instead of division?

Yes. n & 1 gives the lowest bit and n >> 1 drops it, which is the same as n % 2 and n / 2 for non-negative numbers. The loop and the reversal stay the same. Division is easier to explain, while the shift version is common in low level code.