Group add(?<add> \s*\+\s* ) \s*any whitespace character, repeated any number of times
\+the literal + (4310 / 538 / 2B16)
\s*any whitespace character, repeated any number of times
\s*any whitespace character, repeated any number of times
=the literal = (6110 / 758 / 3D16)
\s*any whitespace character, repeated any number of times
Comment: cl: last digit of left operand being 1, cr: last digit of right operand being 1, \d0 checks whether last digit from result is 0
Comment: there will be carry if cl and cr are set, or cl or cr are set and the last digit from result is 0
Group carry(?<carry> (?(cl)(?(cr)|\d0)|(?(cr)\d0|(*F))) ) Condition(?(cl)(?(cr)|\d0)|(?(cr)\d0|(*F))) Uses the first branch if group cl matched
If the condition is true, match this branch:(?(cr)|\d0) Uses the first branch if group cr matched
If the condition is true, match this branch: — matches an empty string
Otherwise, match this branch:\d0 \da digit
0the literal 0 (4810 / 608 / 3016)
Otherwise, match this branch:(?(cr)\d0|(*F)) Uses the first branch if group cr matched
If the condition is true, match this branch:\d0 \da digit
0the literal 0 (4810 / 608 / 3016)
Otherwise, match this branch:(*F) (*F)forces the current match attempt to fail at this position
Comment: add carry with l1 (current digit of left operand being 1) and r1 (current digit of right operand being 1)
Comment: i.e. returns result of carry + l1 + r1 in Z/2Z
Group digitadd(?<digitadd> (?(?= (?(?= (?(l1)(?(r1)|(*F))|(?(r1)(*F))) )(?&carry)|(?!(?&carry))) )1|0) ) Condition(?(?= (?(?= (?(l1)(?(r1)|(*F))|(?(r1)(*F))) )(?&carry)|(?!(?&carry))) )1|0) Uses the first branch if the lookaround matches
Positive Lookahead(?= (?(?= (?(l1)(?(r1)|(*F))|(?(r1)(*F))) )(?&carry)|(?!(?&carry))) ) Condition(?(?= (?(l1)(?(r1)|(*F))|(?(r1)(*F))) )(?&carry)|(?!(?&carry))) Uses the first branch if the lookaround matches
Positive Lookahead(?= (?(l1)(?(r1)|(*F))|(?(r1)(*F))) ) Condition(?(l1)(?(r1)|(*F))|(?(r1)(*F))) Uses the first branch if group l1 matched
If the condition is true, match this branch:(?(r1)|(*F)) Uses the first branch if group r1 matched
If the condition is true, match this branch: — matches an empty string
Otherwise, match this branch:(*F) (*F)forces the current match attempt to fail at this position
Otherwise, match this branch:(?(r1)(*F)) Uses the first branch if group r1 matched
If the condition is true, match this branch:(*F) (*F)forces the current match attempt to fail at this position
If the condition is true, match this branch:(?&carry) (?&carry)calls group carry as a subroutine
Otherwise, match this branch:(?!(?&carry)) If the condition is true, match this branch:1 Otherwise, match this branch:0 Comment: check for a single digit at the current offset whether the result is correct
Comment: ro: right operand out of bounds (i.e. the current digit is at a higher offset than the size of the left operand)
Comment: if we're out of bounds of the right operand, cr is just not set (i.e. handled as if there were leading zeroes)
Group recursedigit(?<recursedigit>
# now, with the r and f, we can figure out r1 and cr at the current offset and also perform binary carry addition at that offset in the result
(?&add) 0*+ (?:\d*(?:0|1(?<r1>)))? (?(ro)|(?=(?<cr>1)?))\k<r> (?&eq) \d*(?&digitadd)\k<f>\b
# iterate through the whole left operand to find the sequences (for right operand and result) of the same length as the offset of the current digit
| (?=\d* (?&add) 0*+ (?:\k<r>(?<ro>)|\d*(?<r>\d\k<r>)) (?&eq) \d*(?<f>\d\k<f>)\b) \d(?&recursedigit)
) Comment: run the check, sets l1 and cl accordingly and initializes the r (right operand) and f (final result) groups to be empty
Group checkdigit(?<checkdigit> (?:0|1(?<l1>)) (?=(?<cl>1)?) (?<r>) (?<f>) (?&recursedigit) ) Comment: "trivial" increment of a binary number, i.e. a +1 is applied to the part of the right operand which exceeds the length of the left operand
Group carryoverflow(?<carryoverflow>
# number contains a zero, just update the part after the last zero
(?<x>\d+) 0 (?<y> \k<r> (?&eq) 0*\k<x>1 | 1(?&y)0 )
# number contains only ones, add a leading 1 and replace all the ones by zeroes
| (?<z> 1\k<r> (?&eq) 0*10 | 1(?&z)0 )
) Comment: ensure correct lengths of the final operand and handle right operands being longer than the left operand
Group recurseoverflow(?<recurseoverflow>
# the left operand is longer than or as long as the right one. In the latter case, the final result will always be exactly one digit longer than the operands
# in the former case, if the first non-leading zero (from the left) of the left operand is at a higher or equal offset to the length of the right operand, the final result will be one digit longer than the left operand
(?&add) 0*+ (?(rlast) \k<r> (?&eq) 0*+(?(ro)(?:1(?=0))?|1)\k<f>\b
# the right operand has a zero at the offset equal to the length of the left operand. Then just copy the leading digits to the final result
| (?:(?<remaining>\d+)(?=0\d* (?&eq) \d*(?=1)\k<f>\b)\k<r> (?&eq) (*PRUNE) 0*\k<remaining>\k<f>\b
| (?&carryoverflow)\k<f>\b))
# iterate through the whole left operand to find the sequences (for right operand and result) of the same length as the left operand
| (?=\d* (?&add) 0*+ (?:\k<r>(?<ro>)|(?=(?:\d\k<r>(?&eq)(?<rlast>))?)\d*(?<r>\d\k<r>)) (?&eq) \d*(?<f>\d\k<f>)\b)
\d(?&recurseoverflow)
) Group s(?<s>
# Handle 0 + x or x + 0 separately to avoid messing around in the big subpatterns
(0*? (?<arg>[01]+) (?&add) 0+ | 0+ (?&add) 0*? (?<arg>[01]+)) (?&eq) (*PRUNE) 0* \k<arg>
| 0*+
# traverse the digits one by one and verify the correctness of each offset individually
(?=(?<iteratedigits> (?=(?&checkdigit))\d (?:\b|(?&iteratedigits)) ))
# assert exact format here
(?=[01]+ (?&add) [01]+ (?&eq) [01]+ \b)
# force an additional digit on the final result in case the left operand is only ones and the right operand not longer than the left
(?<r>) (?<f>) (?&recurseoverflow)
)