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, the same as n % 2 and n / 2 for non-negative numbers. The loop and the reversal stay the same.

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 1 in the 64s place, then six 0s for the places 32 down to 1.

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 find the digits from the top by subtracting powers of two, or from the bottom as remainders of repeated division by 2. Division is the standard method: it needs no largest power and works for every base.

Subtract powers of two from the top

Intuition

This is the conversion by hand. The largest power of two that fits into n gives the first digit, a 1. Then step down one power at a time: if the power fits into what is left, write 1 and subtract it; otherwise write 0.

For 13: 8 fits (keep 5), 4 fits (keep 1), 2 does not, 1 fits. The digits read 1101. The first digit is always a 1, so no leading zero appears. Doubling power only while power ≤ n / 2 finds the largest power without going past n. A 31-bit number takes 31 steps, 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

n % 2 is the last binary digit of n. Dividing by 2 and rounding down drops that digit and shifts the rest one place right, so the next digit becomes the last. Repeat until n is 0 and you collect every digit, lowest first.

For 13 the remainders are 1, 0, 1, 1 (from 13, 6, 3 and 1); reversed they read 1101. The loop stops at 0, so the highest digit it writes is a 1. Zero never enters the loop, which is why it needs its own check. Each step halves n: O(log n) time and 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

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 / where it returns a fraction, as in JavaScript, Lua or PHP. 13 / 2 must become 6, so round down.
Doubling the power until it passes n. For n ≥ 2^30 that reaches 2^31, which overflows a 32-bit integer.
In C, allocating too little: a 31-bit number needs 31 characters plus the terminating '\0'.

Frequently asked questions3

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.

What is the time complexity of converting decimal to binary?

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

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

Yes. n & 1 gives the lowest bit and n >> 1 drops it, the same as n % 2 and n / 2 for non-negative numbers. The loop and the reversal stay the same.