Perform Gray Addition

Question

Objective

Given two non-negative integers encoded in unbounded-length Gray code, add them and output the result, where the result is also encoded in Gray code.

Gray code

There are many equivalent formulations of Gray code, but here's an intuitive one.

The Gray code encodes each non-negative integer as an infinite bit-string. Starting from encoding zero, as the enumeration goes, the least significant bit keeps cycling through "0110". Each place of bit keeps cycling through what the previously significant bit cycles through, but doubled entry-wise. To summarize:

0th LSB: Cycles through "0110"
1st LSB: Cycles through "00111100"
2nd LSB: Cycles through "0000111111110000"
3rd LSB: Cycles through "00000000111111111111111100000000"
(And so on)

That gives the encodings of few non-negative integers as:

Integer = Gray code
("..." stands for infinitely many leading zeroes)
0 = "...00000"
1 = "...00001"
2 = "...00011"
3 = "...00010"
4 = "...00110"
5 = "...00111"
6 = "...00101"
7 = "...00100"
8 = "...01100"
9 = "...01101"

Note that, for each pair of integers differing by one, their Gray codes differ by only one bit.

I/O format

Flexible. Standard loopholes apply.

Examples

Here, inputs and outputs are Gray codes with their leading zeroes stripped off.

"" + "" = ""
"1" + "1" = "11"
"1" + "10" = "110"
"10" + "1" = "110"
"10" + "11" = "111"
"111" + "111" = "1111"

Answer 1

Jelly, 9 bytes

^\€ḄSH^$B

Try it online!

A monadic link taking a pair of lists of binary digits as its argument and returning a list of binary digits. Expects the Gray coding with all leading zeros removed other than for zero itself; returns a Gray coded number in the same format.

Explanation

^\€       | Reduce each by xor, collecting up intermediate results
   Ḅ      | Convert from binary
    S     | Sum
     H^$  | Xor with half
        B | Convert to binary digits

Answer 2

JavaScript (Node.js), 41 bytes

a=>b=>(t=e(a)+e(b))^t/2
e=t=>t&&t^e(t>>1)

Try it online!

Answer 3

05AB1E, 11 bytes

€ηOÉJCOD;^b

Port of @NickKennedy's Jelly answer, so make sure to upvote that answer as well!

Input as a pair of lists of binary digits without leading 0s (where 0 could be either [0] or []).

Try it online or verify all test cases.

Explanation:

€            # Map over each inner list of the (implicit) input-pair:
 η           #  Get its prefixes
  O          # Sum each inner prefix-list
   É         # Check for each sum whether it's odd
    J        # Join each inner list of binary digits together to a string
     C       # Convert each from a binary-string to a base-10 integer
      O      # Sum the pair together
       D;    # Push a copy of this sum, and halve it
         ^   # Bitwise-XOR the sum and halved sum together
             # (where both are treated as floored integers, ignoring any `.5` decimals)
          b  # Convert this from a base-10 integer to a binary-string
             # (which is output implicitly as result)

Answer 4

Charcoal, 31 bytes

≔⍘ΣＥＥ²Ｓ↨²Ｅι﹪Σ…ι⊕첦²θ⭆θ¬⁼ι§⁺0θκ

Try it online! Link is to verbose version of code. Uses bit strings for I/O. Explanation: Somewhat limited by the lack of a bitwise XOR function.

≔⍘ΣＥＥ²Ｓ↨²Ｅι﹪Σ…ι⊕첦²θ

For each input, get all of its prefixes, take the digit sum modulo 2, and interpret the results as base 2. Then convert the sum back to base 2.

⭆θ¬⁼ι§⁺0θκ

Compare each bit with the previous and output 0 if they the same and 1 if they differ.