// 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
To restrict the number of recursions, assuming length of A >= length of B
type Bit = 1 | 0
type BinaryAdd<A extends Bit[], B extends Bit[],
Sum extends Bit[] = {[I in keyof A]: [A[I], B[I & keyof B]] extends [1, 0] | [0, 1] ? 1 : 0},
Carry extends Bit[] = {[I in keyof A]: [A[I], B[I & keyof B]] extends [1, 1] ? 1 : 0}
> = Carry extends [1, ...any] ? BinaryAdd<[...Carry, 0], [0, ...Sum]>
: Carry extends [any, 1, ...any] ? BinaryAdd<Carry, Sum>
: Sum
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