Decimal to Binary

Base conversion with no arithmetic operators in sight.

DecimalToBinary<N> takes an integer N and returns a string type holding its binary representation. N ranges over the whole safe-integer interval, from Number.MIN_SAFE_INTEGER to Number.MAX_SAFE_INTEGER, so negative inputs and values up to 2^53 - 1 both have to work.

type binary1 = DecimalToBinary<7> // expected to be '111'
type binary2 = DecimalToBinary<-170> // expected to be '-10101010'

The usual type-level counting trick, building a tuple of length N and reading its length, dies immediately here. TypeScript caps tuples at 10000 elements, and the largest test case is 9007199254740991. The only representation of a number that big the type system will hand you is its decimal string, so that string is what the solution has to do arithmetic on.

/* _____________ Your Code Here _____________ */

type DecimalToBinary<N extends number> = any

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '../helpers'

type cases = [
  Expect<Equal<DecimalToBinary<2>, "10">>,
  Expect<Equal<DecimalToBinary<3>, "11">>,
  Expect<Equal<DecimalToBinary<0>, "0">>,
  Expect<Equal<DecimalToBinary<255>, "11111111">>,
  Expect<Equal<DecimalToBinary<-170>, '-10101010'>>,
  Expect<Equal<DecimalToBinary<10000>, "10011100010000">>,
  Expect<Equal<DecimalToBinary<9007199254740991>, "11111111111111111111111111111111111111111111111111111

Detailed Explanation

The solution in full:

type Digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
type Bit = '0' | '1'
 
type HalfStep = {
  '00': ['0', '0']; '01': ['0', '1']; '02': ['1', '0']; '03': ['1', '1']; '04': ['2', '0']
  '05': ['2', '1']; '06': ['3', '0']; '07': ['3', '1']; '08': ['4', '0']; '09': ['4', '1']
  '10': ['5', '0']; '11': ['5', '1']; '12': ['6', '0']; '13': ['6', '1']; '14': ['7', '0']
  '15': ['7', '1']; '16': ['8', '0']; '17': ['8', '1']; '18': ['9', '0']; '19': ['9', '1']
}
 
type TrimZeros<S extends string> = S extends `0${infer Rest}` ? TrimZeros<Rest> : S
 
type Halve<
  S extends string,
  Carry extends Bit = '0',
  Acc extends string = '',
> = S extends `${infer D extends Digit}${infer Rest}`
  ? HalfStep[`${Carry}${D}`] extends [infer Q extends Digit, infer Next extends Bit]
    ? Halve<Rest, Next, `${Acc}${Q}`>
    : never
  : [TrimZeros<Acc>, Carry]
 
type ToBinary<S extends string, Acc extends string = ''> = S extends ''
  ? Acc extends ''
    ? '0'
    : Acc
  : Halve<S> extends [infer Q extends string, infer R extends Bit]
    ? ToBinary<Q, `${R}${Acc}`>
    : never
 
type DecimalToBinary<N extends number> = `${N}` extends `-${infer Abs}`
  ? `-${ToBinary<Abs>}`
  : ToBinary<`${N}`>

The algorithm, before any types

Repeated division by two is how you convert a decimal number to binary by hand. Divide, write down the remainder, divide the quotient again, and keep going until the quotient is zero. The remainders, read bottom to top, are the binary digits.

// 13 / 2 = 6 remainder 1   <- last bit
//  6 / 2 = 3 remainder 0
//  3 / 2 = 1 remainder 1
//  1 / 2 = 0 remainder 1   <- first bit, so 13 is '1101'

Dividing a decimal string by two

Long division by two reads the digits left to right and carries at most one unit of 10 into the next column. At each digit the current value is carry * 10 + digit, the output digit is half of that, and the new carry is the leftover remainder. Both inputs come from a tiny alphabet, two possible carries and ten possible digits, so all twenty cases fit in a lookup object keyed by the pair.

// HalfStep['07'] is ['3', '1']   carry 0, digit 7 -> 7/2 = 3 remainder 1
// HalfStep['13'] is ['6', '1']   carry 1, digit 3 -> 13/2 = 6 remainder 1

Halve walks the string with the pattern `${infer D extends Digit}${infer Rest}`. Two adjacent infer placeholders make the first one match exactly one character, and the extends Digit clause narrows D from string to a literal, which is what makes HalfStep[`${Carry}${D}`] a legal index. The quotient digit is appended to the accumulator, the remainder becomes the next carry, and the recursion continues on Rest.

When the string runs out, Halve returns the pair [quotient, remainder]. The quotient goes through TrimZeros first, because halving '10' produces the raw accumulator '05' and the next round has to see '5'. Trimming every leading zero also turns '0' and '00' into the empty string, which doubles as the termination signal.

The outer loop

ToBinary is the division loop itself. It halves the current decimal string, prepends the remainder bit to the accumulator so the bits come out in the right order, and recurses on the quotient. The empty string means the quotient reached zero and the accumulator is the answer.

// ToBinary<'13'>  -> ToBinary<'6', '1'>
//                 -> ToBinary<'3', '01'>
//                 -> ToBinary<'1', '101'>
//                 -> ToBinary<'', '1101'>  -> '1101'

Each round strictly shrinks the number, so the loop always terminates: 53 rounds for the largest test case, with a 16 character inner walk each time. Both recursions are in tail position inside their conditional types, so TypeScript's tail-call elimination keeps them flat instead of nesting 53 instantiations deep.

The entry point

`${N}` is the only bridge from a numeric literal type to something a template literal pattern can take apart. Matching it against `-${infer Abs}` splits the sign off and the magnitude is converted on its own, then the minus is glued back onto the result. Positive numbers skip the branch and convert directly.

Edge cases the tests cover

• DecimalToBinary<0>: '0' halves to the quotient '' with remainder '0', so the second round sees an empty string and hands back the accumulator '0'. The Acc extends '' ? '0' guard is the safety net for the other order, an empty string arriving before a single bit has been collected.
• DecimalToBinary<-170> and DecimalToBinary<-9007199254740991>: handled by the sign split, so the magnitude path never has to think about a leading -.
• DecimalToBinary<9007199254740991>: 53 bits, far past any tuple-based approach, and the reason the whole solution works on strings.
• DecimalToBinary<255> and DecimalToBinary<10000>: ordinary cases that exercise the carry across several digits, including the trailing zeros of 10000 that TrimZeros has to clear each round.