regex101: Adding binary numbers

Explanation

Pro

Definition Group(?(DEFINE) (?<add> \s*\+\s* ) (?<eq> \s*=\s* ) # Remove all zeroes except the last one if the number is 0 (?<zero> (?:0(?=\d))*+ ) # cl: last digit of left operand being 1, cr: last digit of right operand being 1, \d(?:0|\b) check if last digit from result is 0 # there will be carry if cl and cr are set, or cl or cr are set and the last digit from result is 0 (?<carry> (?(cl)(?(cr)|\d(?:0|\b))|(?(cr)\d(?:0|\b)|(*F))) ) # add carry with l1 (current digit of left operand being 1) and r1 (current digit of right operand being 1) # i.e. returns result of carry + l1 + r1 in Z/2Z (?<digitadd> (?(?= (?(?=(?(l1)(?(r1)|(*F))|(?(r1)(*F))))(?&carry)|(?!(?&carry))) )1|0) ) # check for a single digit at the current offset whether the result is correct # ro: right operand out of bounds (i.e. the current digit is at a higher offset than the size of the left operand) # if we're out of bounds of the right operand, cr is just not set (i.e. handled as if there were leading zeroes) (?<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) (?&zero) (?:\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) (?&zero) (?:\k<r>(?<ro>)|\d*(?<r>\d\k<r>)) (?&eq) \d*(?<f>\d\k<f>)\b) \d(?&recursedigit) ) # run the check, sets l1 and cl accordingly and initializes the r (right operand) and f (final result) groups to be empty (?<checkdigit> (?:0|1(?<l1>)) (?=(?<cl>1)?) (?<r>) (?<f>) (?&recursedigit) ) # "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 (?<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 ) ) # ensure correct lengths of the final operand and handle right operands being longer than the left operand (?<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)(?(addone)1)|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 # otherwise there will be some carry which needs to be applied before copying the leading digits to the final result | (?&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) # check - only at the first non-leading zero - whether the right operand is longer than the current offset of the iteration, or just as long and having a carry (i.e. the digit at that offset in the final result is 0) (?(nullchecked)|(?=(?<addone>(?=0)(?=(?:\d(?=\d*(?&add)\d*(?&eq)\d*(?<c>\d\k<c>)\b))+(?&add))(?<longer>(?&add)0*|\d(?&longer)\d)(\d+(?&eq)|(?&eq)\d*(?=0)\k<c>))?)(?=(?<nullchecked>0)?)) \d(?&recurseoverflow) ) (?<s> (?=\d) 0*? (?<arg>[01]+)? (?&add) (?=\d) 0*? (?<arg>(?(arg)(*F))[01]+)? (?&eq) (*PRUNE) \k<arg> | (?&zero) # 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) # remove leading zeroes and 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 0*? (?<r>) (?<f>) (?<c>) (?=(?<addone>1+(?&add))?) (?&recurseoverflow) # Handle 0 + x or x + 0 separately to avoid messing around in the big subpatterns ) )

Group add(?<add> \s*\+\s* )

\s*any whitespace character, repeated any number of times

\+the literal + (43₁₀ / 53₈ / 2B₁₆)

\s*any whitespace character, repeated any number of times

Group eq(?<eq> \s*=\s* )

\s*any whitespace character, repeated any number of times

=the literal = (61₁₀ / 75₈ / 3D₁₆)

\s*any whitespace character, repeated any number of times

Comment: Remove all zeroes except the last one if the number is 0

Group zero(?<zero> (?:0(?=\d))*+ )

Non-Capturing Group(?:0(?=\d))*+

*+repeats the group contents below any number of times:

0the literal 0 (48₁₀ / 60₈ / 30₁₆)

Positive Lookahead(?=\d)

\da digit

Comment: cl: last digit of left operand being 1, cr: last digit of right operand being 1, \d(?:0|\b) check if 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)|\d(?:0|\b))|(?(cr)\d(?:0|\b)|(*F))) )

Condition(?(cl)(?(cr)|\d(?:0|\b))|(?(cr)\d(?:0|\b)|(*F)))

Uses the first branch if group cl matched

If the condition is true, match this branch:(?(cr)|\d(?:0|\b))

Condition(?(cr)|\d(?:0|\b))

Uses the first branch if group cr matched

If the condition is true, match this branch: — matches an empty string

Otherwise, match this branch:\d(?:0|\b)

\da digit

Non-Capturing Group(?:0|\b)

1st Alternative0

0the literal 0 (48₁₀ / 60₈ / 30₁₆)

2nd Alternative\b

\ban ASCII word boundary

Otherwise, match this branch:(?(cr)\d(?:0|\b)|(*F))

Condition(?(cr)\d(?:0|\b)|(*F))

Uses the first branch if group cr matched

If the condition is true, match this branch:\d(?:0|\b)

\da digit

Non-Capturing Group(?:0|\b)

1st Alternative0

0the literal 0 (48₁₀ / 60₈ / 30₁₆)

2nd Alternative\b

\ban ASCII word boundary

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))))

If the condition is true, match this branch:(?&carry)

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) (?&zero) (?:\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) (?&zero) (?:\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)(?(addone)1)|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 # otherwise there will be some carry which needs to be applied before copying the leading digits to the final result | (?&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) # check - only at the first non-leading zero - whether the right operand is longer than the current offset of the iteration, or just as long and having a carry (i.e. the digit at that offset in the final result is 0) (?(nullchecked)|(?=(?<addone>(?=0)(?=(?:\d(?=\d*(?&add)\d*(?&eq)\d*(?<c>\d\k<c>)\b))+(?&add))(?<longer>(?&add)0*|\d(?&longer)\d)(\d+(?&eq)|(?&eq)\d*(?=0)\k<c>))?)(?=(?<nullchecked>0)?)) \d(?&recurseoverflow) )

Group s(?<s> (?=\d) 0*? (?<arg>[01]+)? (?&add) (?=\d) 0*? (?<arg>(?(arg)(*F))[01]+)? (?&eq) (*PRUNE) \k<arg> | (?&zero) # 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) # remove leading zeroes and 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 0*? (?<r>) (?<f>) (?<c>) (?=(?<addone>1+(?&add))?) (?&recurseoverflow) # Handle 0 + x or x + 0 separately to avoid messing around in the big subpatterns )

\ban ASCII word boundary

(?&s)calls group s as a subroutine

\ban ASCII word boundary

Global pattern flags

x modifier: extended. Ignores unescaped whitespace and comments outside character classes

g modifier: global. Finds all matches instead of stopping after the first

J modifier: Allow duplicate subpattern names

Quick Reference

25 tokens

Regular Expression

(?(DEFINE)
(?<add> \s*\+\s* )
(?<eq> \s*=\s* )
# Remove all zeroes except the last one if the number is 0
(?<zero> (?:0(?=\d))*+ )
# cl: last digit of left operand being 1, cr: last digit of right operand being 1, \d(?:0|\b) check if last digit from result is 0
# there will be carry if cl and cr are set, or cl or cr are set and the last digit from result is 0
(?<carry> (?(cl)(?(cr)|\d(?:0|\b))|(?(cr)\d(?:0|\b)|(*F))) )
# add carry with l1 (current digit of left operand being 1) and r1 (current digit of right operand being 1)
# i.e. returns result of carry + l1 + r1 in Z/2Z
(?<digitadd> (?(?= (?(?=(?(l1)(?(r1)|(*F))|(?(r1)(*F))))(?&carry)|(?!(?&carry))) )1|0) )
# check for a single digit at the current offset whether the result is correct
# ro: right operand out of bounds (i.e. the current digit is at a higher offset than the size of the left operand)
# if we're out of bounds of the right operand, cr is just not set (i.e. handled as if there were leading zeroes)
(?<recursedigit>
# now,

- 1 + 1 = 0
- 1 + 1 = 1
- 0 + 1 = 11
+ 1 + 1 = 10
- 1 + 10 = 101
- 0 + 11 = 101
+ 0 + 1 = 1
- 0 + 0 = 10
+ 1 + 0 = 1
- 1 + 101 = 1010
+ 10 + 0 = 10
+ 10 + 1 = 11
+ 11 + 1 = 100
+ 100 + 1 = 101
+ 01 + 10 = 11
+ 10 + 10 = 100
+ 010 + 010 = 100
+ 101 + 11 = 1000
- 101 + 10 = 1111
- 100 + 10 = 111
- 101 + 10 = 101
+ 101 + 10 = 111
+ 11 + 101 = 1000
+ 11 + 1011 = 1110
+ 11 + 10101 = 11000
+ 1 + 1111 = 10000
+ 111 + 11 = 1010
+ 1110 + 100 = 10010
+ 11 + 11 = 110
+ 1111 + 11 = 10010
- 010 + 010 = 000
- 100 + 100 = 1100
+ 100 + 100 = 1000
+ 1000 + 100 = 1100
+ 1 + 1000 = 1001
+ 1000 + 1 = 1001
+ 110 + 1100 = 10010
- 110 + 1010 = 1000
- 10 + 1 = 11111001