Type Challenges: 32532-hard-binary-addition Solution

// Add one to A
// eg.
// AddOne<[1, 0]> -> [1, 1]
// AddOne<[1, 1]> -> [1, 0, 0]
type AddOne<A extends Bit[]> = A extends [...infer Rest extends Bit[], infer Last]
  ? Last extends 0
    ? [...Rest, 1]
    : [...AddOne<Rest>, 0]
  : [1];

type BinaryAdd<A extends Bit[], B extends Bit[]> = B extends [...infer BRest extends Bit[], infer BLast]
  ? BLast extends 1
    ? AddOne<A> extends [...infer ARest extends Bit[], infer ALast]
      ? [...BinaryAdd<ARest, BRest>, ALast]
      : never
    : A extends [...infer ARest extends Bit[], infer ALast]
    ? [...BinaryAdd<ARest, BRest>, ALast]
    : B
  : A;

Solution by yukicountry #34437

type Bit = 1 | 0

type CarryBit<A extends Bit, B extends Bit, PreviousCarry extends Bit> =
  `${A}${B}${PreviousCarry}` extends `${any}1${any}1${any}` ? 1 : 0

type AddBit<A extends Bit, B extends Bit, PreviousCarry extends Bit> =
  `${A}${B}${PreviousCarry}` extends `111` ? 1 :
  `${A}${B}${PreviousCarry}` extends `${any}1${any}1${any}` ? 0 :
  `${A}${B}${PreviousCarry}` extends `${any}1${any}` ? 1 : 0

type BinaryAdd<A extends Bit[], B extends Bit[], Carry extends Bit = 0, FinalArray extends Bit[] = []> =
  A extends [...infer RestOfA extends Bit[], infer LastBitA extends Bit] ?
    B extends [...infer RestOfB extends Bit[], infer LastBitB extends Bit] ?
      BinaryAdd<RestOfA, RestOfB, CarryBit<LastBitA, LastBitB, Carry>, [AddBit<LastBitA, LastBitB, Carry>, ...FinalArray]> :
      // assumption that the binary arrays are same length so will never get to this never type
      never :
    Carry extends 1 ?
      [1, ...FinalArray] :
      FinalArray

Solution by M-Kusumgar #33729

Support A's length is not equal to B's length.

// your answers
type Bit = 1 | 0

type LastBit<T extends Bit[]> = T extends [...Bit[], infer B extends Bit] ? B : never
type PoppedBits<T extends Bit[]> = T extends [...infer Rest extends Bit[], Bit] ? Rest : never
type FilterOne<T extends Bit[]> = T extends [] ? [] : [...(LastBit<T> extends 0 ? [] : [1]), ...FilterOne<PoppedBits<T>>]
type NumOfOne<T extends Bit[]> = FilterOne<T>['length']

type BinaryAdd<
  A extends Bit[], 
  B extends Bit[],
  Carry extends Bit = 0,
  Result extends Bit[] = [],
  // Internals
  CurrentBitA extends Bit = LastBit<A>,
  CurrentBitB extends Bit = LastBit<B>,
  CurrentBitResult extends Bit = NumOfOne<[CurrentBitA, CurrentBitB, Carry]> extends (0 | 2) ? 0 : 1,
  NextA extends Bit[] = PoppedBits<A> extends [] ? [0] : PoppedBits<A>,
  NextB extends Bit[] = PoppedBits<B> extends [] ? [0] : PoppedBits<B>,
  NextCarry extends Bit = NumOfOne<[CurrentBitA, CurrentBitB, Carry]> extends (2 | 3) ? 1 : 0,
> = [A, B, Carry] extends [[0], [0], 0]
  ? Result
  : BinaryAdd<
      NextA,
      NextB,
      NextCarry,
      [CurrentBitResult, ...Result]
    >

Solution by DevilTea #33275

type BinaryAdd<A extends Bit[], B extends Bit[]> = Sum<A, B>

type Sum<A extends Bit[], B extends Bit[]>
  = 1 extends B[number]
    ? Carry<A, B> extends 1 ? Sum<[0, ...Xor<A, B>], [1, ...ShiftLeft<And<A, B>>]>
    : Sum<Xor<A, B>, ShiftLeft<And<A, B>>>
  : A

type And<A, B> = {[K in keyof A]: K extends keyof B ? 0 extends A[K] | B[K] ? 0 : 1 : A[K]}

type Xor<A, B> = {[K in keyof A]: K extends keyof B ? A[K] extends B[K] ? 0 : 1 : A[K]}

type ShiftLeft<A> = A extends [Bit, ...infer Trail extends Bit[]] ? [...Trail, 0] : A

type Carry<A extends Bit[], B extends Bit[]> = A extends [1, ...any] ? B extends [1, ...any] ? 1 : 0 : 0

type Bit = 1 | 0

Playground

Initial Addition:
- Xor<A, B> computes the sum of bits in A and B without considering the carry.
- And<A, B> computes the carry for each bit position.
- ShiftLeft<And<A, B>> shifts the carry bits to the next higher bit position.
Recursive Step:
- The recursive Sum continues to add the new sum and carry until there are no more carries (i.e., B becomes all zeros).
Base Case:
- The recursion stops when B (the carry) contains no 1s. At this point, B[number] is not 1, and the final sum is A.

Number of Recursive Steps

The number of recursive steps is directly related to the number of carry operations needed to complete the binary addition:

If there are no carry operations needed, the recursion will stop after one step.
If each addition generates a carry, the recursion will continue until all carry bits are propagated through the binary digits.

In the worst case, if every bit position generates a carry, the number of recursive steps required is approximately equal to the number of bits in the longest input array. This is because each step processes one level of carry propagation.

Example

Consider adding two 4-bit binary numbers, A = [1, 0, 1, 1] and B = [0, 1, 1, 0]:

Initial Addition:
- Xor<A, B> = [1, 1, 0, 1]
- And<A, B> = [0, 0, 1, 0]
- ShiftLeft<And<A, B>> = [0, 1, 0, 0]
First Recursive Step:
- Sum<[1, 1, 0, 1], [0, 1, 0, 0]>
- Xor = [1, 0, 0, 1]
- And = [0, 1, 0, 0]
- ShiftLeft<And> = [0, 0, 1, 0]
Second Recursive Step:
- Sum<[1, 0, 0, 1], [0, 0, 1, 0]>
- Xor = [1, 0, 1, 1]
- And = [0, 0, 0, 0]
- ShiftLeft<And> = [0, 0, 0, 0]
Third Recursive Step:
- Sum<[1, 0, 1, 1], [0, 0, 0, 0]>
- Since B is now all zeros, the recursion stops.

Solution by teamchong #32986

type Bit = 1 | 0;
type Shifts = '011' | '101' | '110' | '111';
type Ones = '001' | '010' | '100' | '111';

type BinaryAdd<A extends Bit[], B extends Bit[], S extends Bit = 0, R extends Bit[] = []> = 
  [A, B] extends [[...infer AR extends Bit[], infer X extends Bit], [...infer BR extends Bit[], infer Y extends Bit]]
    ? BinaryAdd<AR, BR, `${S}${X}${Y}` extends Shifts ? 1 : 0, [`${S}${X}${Y}` extends Ones ? 1 : 0, ...R]>
    : S extends 1 ? [1, ...R] : R;

Solution by alexandroppolus #32964

type Bit = 1 | 0

type Single<A extends Bit, B extends Bit, Carry extends boolean = false> =
  `${A}${B}` extends `11`
    ?  { carry: true, tail: Carry extends true ? 1 : 0 }
    : `${A}${B}` extends `10` | `01`
      ? { carry: Carry, tail: Carry extends true ? 0 : 1 }
      : { carry: false, tail: Carry extends true ? 1 : 0 }

type BinaryAdd<A extends Bit[], B extends Bit[], Carry extends boolean = false, Res extends Bit[] = []> =
  A extends [ ...infer RestA extends Bit[], infer FA extends Bit ]
    ? B extends [ ...infer RestB extends Bit[], infer FB extends Bit ]
      ? Single<FA, FB, Carry> extends infer F
        ? F extends { carry: boolean, tail: Bit }
          ? BinaryAdd<RestA, RestB, F['carry'], [F['tail'], ...Res]>
          : never
        :never
      : never
    : [ ...(Carry extends true ? [1] : []), ...Res ]

Solution by lvjiaxuan #32943

type Bit = 1 | 0
//    { 00 = 0
// 0  { 01 = 1
//    { 11 = 0 +1
//
//    { 00 = 1
// 1+ { 01 = 0 +1
//    { 11 = 1 +1
type AddPattern<A extends Bit, B extends Bit, _Carry extends Bit = 0> = //[Result, NextCarry]
  [A & B] extends [never] ? [_Carry extends 1 ? 0 : 1, _Carry extends 1 ? 1 : 0] :  //01
  [_Carry extends 1 ? 1 : 0, A extends 1 ? 1 : 0];  //00 | 11
  
type BinaryAdd<A extends Bit[], B extends Bit[], _Carry extends Bit = 0> =
  A extends [...infer RA extends Bit[], infer LA extends Bit] ?
  B extends [...infer RB extends Bit[], infer LB extends Bit] ?
  AddPattern<LA, LB, _Carry> extends [infer Result, infer NextCarry extends Bit] ? [...BinaryAdd<RA, RB, NextCarry>, Result] : never :
  never :
  _Carry extends 1 ? [1] : [];  //pop

Solution by E-uler #32792

type Bit = 1 | 0

type BinaryAdd<A extends Bit[], B extends Bit[], _Carry extends Bit = 0> =
  A['length'] extends 0
    ? _Carry extends 1 ? [1] : []
    : [A, B] extends [[...infer RestA extends Bit[], infer LastA extends Bit], [...infer RestB extends Bit[], infer LastB extends Bit]]
      ? [...BinaryAdd<RestA, RestB, Carry<[LastA, LastB, _Carry]>>, XOr<_Carry, XOr<LastA, LastB>>]
      : never

type XOr<A extends Bit, B extends Bit> = A extends B ? 0 : 1
type Carry<T extends Bit[]> = Reject<T, 0>['length'] extends 0 | 1 ? 0 : 1
type Reject<T extends any[], K> = T extends [infer Head, ...infer Rest]
  ? Head extends K ? Reject<Rest, K> : [Head, ...Reject<Rest, K>]
  : []

Solution by Sun79 #32750