12
\$\begingroup\$

Your job is to implement bitwise addition.

To ensure that this is done, you will compute and print the result of addition without carry (or bitwise XOR). Then, you will compute the carry of the addition (bitwise AND) and multiply it by two (bitwise left shift). If the carry is nonzero, then you add the carry and the previous result until the carry is zero, at which point you stop producing output. If all is done correctly, the final result printed should be the sum of the two integers that you received as input.

Here's an ungolfed reference implementation in C:

#include <stdio.h>

void print_add(unsigned a, unsigned b)
{
    unsigned carry;

    while(b)
    {
        carry = a & b;
        a ^= b;
        printf("%u\n", a);
        b = carry << 1;
    }
}

Input

Two positive integers in any convenient format.

Output

A list of positive integers in any convenient format representing each result of addition without carry. Leading/trailing whitespace/newlines are allowed.

Rules

Testcases

1, 1 -> 0, 2
3, 17 -> 18, 16, 20
6, 7 -> 1, 13
21, 19 -> 6, 36, 32, 40
10, 9 -> 3, 19
20, 20 -> 0, 40

Your code must work for at least all pairs of positive integers that your integer type can represent the sum of.

\$\endgroup\$
2
  • \$\begingroup\$ This would have been far more interesting (at least to me) as an efficiency-golf challenge. \$\endgroup\$
    – Cody Gray
    Apr 29, 2020 at 22:32
  • 1
    \$\begingroup\$ @CodyGray As in fastest-code or fastest-algorithm? fastest-code would be somewhat hard to test and fastest-algorithm is trivial, it's used here. \$\endgroup\$
    – S.S. Anne
    Apr 29, 2020 at 22:34

16 Answers 16

5
\$\begingroup\$

JavaScript (ES6), 34 bytes

Takes input as (A)(B), where A+B is a positive-looking 32-bit integer, i.e. less than 0x80000000.

Returns an array.

A=>g=B=>B?[A^=B,...g((B&~A)*2)]:[]

Try it online!

Or for 35 bytes, a BigInt version with unlimited input:

A=>g=B=>B?[A^=B,...g((B&~A)*2n)]:[]

Try it online!

How?

In order to use only 2 variables and pass a single variable to the recursive function, we apply the XOR right away to A and prepend the result to the output array.

Instead of computing (A AND B) * 2, we now need to compute (B AND (A XOR B)) * 2. Fortunately this can also be expressed as:

(B AND (NOT A)) * 2

leading to the rather short (B&~A)*2 in JS syntax.

\$\endgroup\$
0
5
\$\begingroup\$

sed -En, 120 bytes

:L;s/0(.{8})0/a\1a/;s/0(.{8})1/b\1a/;s/1(.{8})0/b\1a/;s/1(.{8})1/a\1b/;tL;y/ab /01\
/;P;s/$/0/;tM;:M;s/\
.(.*1)/\
\1/;tL

Try it online!

Or try all the test cases online!

Input: Two 8-bit integers written in binary (on one line, with a space in between them).

Output: Also 8-bit binary numbers.

For convenience this is written for 8-bit integers, but if you want to use 32-bit integers, for instance, just change the instances of 8 in the script to 32. You can try out the 32-bit version here.

\$\endgroup\$
4
\$\begingroup\$

C (gcc), 65 \$\cdots\$ 46 45 bytes

Saved 5 bytes thanks to ceilingcat!!!

f(a,b){for(;b;b&=~a,b*=2)printf("%d ",a^=b);}

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ I added a clarification so you don't need that long -- ugh. \$\endgroup\$
    – S.S. Anne
    Apr 27, 2020 at 23:31
  • \$\begingroup\$ @S.S.Anne Great - thanks for the clarification! :-) \$\endgroup\$
    – Noodle9
    Apr 27, 2020 at 23:53
4
\$\begingroup\$

Bash, 69 \$\cdots\$ 56 45 bytes

11 bytes less, thank to Mitchell Spector!

d()(echo $[a=$1^$2];((c=$1&$2))&&d $a $[c*2])

Try it online!

Commented long version:

# Defines function d with parenthesis sub-shell block (commands), rather than
# curly-braces commands block, to save leading space and trailing semicolons.
d () 
(
  # Print and assign new value, using deprecated $[expression] syntax, rather
  # than modern's $((expression)) syntax, saves 2 bytes.
  echo $[a=$1^$2]
  # Bash stand-alone arithmetic expression's return-code, conditions recursive
  # call, with argument 2 computed inline, using deprecated but shorter
  # arithmetic expression.
  ((c=$1&$2)) && d $a $[c*2]
)

Note that the shorter but deprecated $[expression] syntax is going to be removed in later Bash versions.

See: man bash Bash 5.0.3(1)-release

Arithmetic expansion allows the evaluation of an arithmetic expression and the substitution of the result.

The format for arithmetic expansion is:

$((expression))

The old format $[expression] is deprecated and will be removed in upcoming versions of bash.

See also: bug-bash ML:

On Sun, Apr 8, 2012 at 12:50 AM, Linda Walsh wrote:

Re: status on $[arith] for eval arith vsl $((arith))?? ... Some linux distributions patch the man page and document $[ ] as deprecated.

The SUS rationale says:

In early proposals, a form $[expression] was used. It was functionally equivalent to the "$(())" of the current text, but objections were lodged that the 1988 KornShell had already implemented "$(())" and there was no compelling reason to invent yet another syntax. Furthermore, the "$[]" syntax had a minor incompatibility involving the patterns in case statements.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Welcome to Code Golf, Léa! Congrats on your first entry, hope the 69 was just a coincidence :p Unfortunately, I don't know Bash, so I can't comment on the execution. However, as for the format: You'll soon notice many people use TIO to link to their code in a functioning environment for all to play around with! Not just that, but it makes it easier to show off the test inputs, in the footer or input slot depending, and boilerplate can be hidden in the header. Finally, it'll autogenerate your post which you can paste! \$\endgroup\$
    – AviFS
    Apr 29, 2020 at 3:20
  • 1
    \$\begingroup\$ All that'll be left to add is an explanation, and you'll notice nearly everyone copies and pastes that autogenerated bit, which is why all the answers have the same format! Here's the TIO link I created for you, with the input cases as well! To copy the classic formatting after you click on the link, just press Esc1, S and then G... Vim Style!!! I highly recommend pasting that here. Golf away! \$\endgroup\$
    – AviFS
    Apr 29, 2020 at 3:24
  • \$\begingroup\$ @AviF.S. Really nice guidance with TIO. Shortened code even more than my initial submission. \$\endgroup\$
    – Léa Gris
    Apr 29, 2020 at 4:58
  • 1
    \$\begingroup\$ Welcome -- Nice first answer! By the way, I think you can shorten it to 45 bytes like this. \$\endgroup\$ Apr 30, 2020 at 6:22
  • \$\begingroup\$ Do you happen to know what the "minor incompatibility" is between the $[...] syntax and case-statement patterns? I know that $[...] is said for many years to have been heading towards deprecation, so I don't use it in production code, but I don't see what parsing issues could arise in a case statement that uses it. \$\endgroup\$ Apr 30, 2020 at 18:57
3
\$\begingroup\$

Python 2, 39 bytes

def f(a,b):1/b;print a^b;f(a^b,(a&b)*2)

Try it online!

A recursive function that prints all intermediate values, then terminates with an exception.


Python 2, 41 bytes

f=lambda a,b:b*[0]and[a^b]+f(a^b,(a&b)*2)

Try it online!

A recursive function that takes in two summands and returns a list of intermediate results.

\$\endgroup\$
3
\$\begingroup\$

Jelly,  12  11 bytes

&/Ḥṭ^/ƲƬḢ€Ḋ

A monadic Link accepting a list of two integers which yields a list of integers.

Try it online!

How?

Note that at the end of proceedings we'll have the sum and a carry of zero, and if we were to compute the addition without carry and the carry once more we'd get the same results, so we can keep going until [sum-without-carry, carry] does not change...

&/Ḥṭ^/ƲƬḢ€Ḋ - Link: list of two integers, [a,b]
       Ƭ    - Collect up (starting with [a,b]) while results are distinct applying:
      Ʋ     -   last four links as a monad:
 /          -     reduce (current pair, [x,y]) by:
&           -       bitwise AND
  Ḥ         -     double
     /      -     reduce (current pair, [x,y]) by:
    ^       -       bitwise XOR
   ṭ        -     tack -> [x^y, (x&y)*2]
        Ḣ€  - head each
          Ḋ - dequeue (remove a from the front)
\$\endgroup\$
3
\$\begingroup\$

Batch, 68 bytes

@if %2==0 exit/b
@set/a"a=%1^%2,b=(%1&%2)*2
@echo %a%
@%0 %a% %b%

Explanation:

@if %2==0 exit/b

Repeat until b is zero.

@set/a"a=%1^%2,b=(%1&%2)*2

Calculate the XOR and the carry.

@echo %a%

Output the next result.

@%0 %a% %b%

Restart with the new operands.

\$\endgroup\$
3
\$\begingroup\$

MATL, 13 bytes

`Z~t1MZ&Et]xx

Try it online! Or verify all test cases.

Explanation

`       % Do...while
  Z~    %   Bitwise XOR. Takes the two inputs implicitly the first time
  t     %   Duplicate
  1M    %   Push the inputs of the latest bitwise XOR again
  Z&    %   Bitwise AND
  E     %   Multiply by 2
  t     %   Duplicate. This copy will be used as loop condition
]       % End. If the top of the stack is not 0 a new iteration is run
xx      % Delete top two elements (a 0 from the last bitwise AND and a
        % copy of the result from the last bitwise XOR)
        % Implicitly display
\$\endgroup\$
3
\$\begingroup\$

Rust, 69 68 bytes

|mut a:u8,mut b:u8|while b>0{let c=(a&b)*2;a^=b;b=c;print!("{} ",a)}

A port of math junkie's python answer.

Try it on Rust Playground.

I had to use a temporary variable because destructuring in assignments is still being worked on

\$\endgroup\$
2
  • \$\begingroup\$ I believe the trailing semicolon shouldn't be included in the byte count (as it is part of the assignment to g and not the closure), which saves a byte. \$\endgroup\$
    – Endenite
    Apr 29, 2020 at 18:47
  • \$\begingroup\$ You're probably right, as the code without the semicolon is an expression that evaluates to a closure, which could also be used as a return value. \$\endgroup\$
    – corvus_192
    Apr 29, 2020 at 18:55
2
\$\begingroup\$

Python 2, 44 43 bytes

-1 byte thanks to @SurculoseSputum

a,b=input()
while b:a,b=a^b,(a&b)*2;print a

Try it online!

Very simple implementation. Pretty much a golfed version of the reference code.

\$\endgroup\$
2
  • \$\begingroup\$ -1 byte by not using c. \$\endgroup\$ Apr 27, 2020 at 22:59
  • \$\begingroup\$ @SurculoseSputum Ah, thanks. I played around with that a little bit, but I didn't get the ordering quite right \$\endgroup\$ Apr 27, 2020 at 23:00
2
\$\begingroup\$

Charcoal, 24 bytes

NθNηWη«≧&θη≔⁻|θιηθ≦⊗η⟦Iθ

Try it online! Link is to verbose version of code. Explanation:

NθNη

Input a and b.

Wη«

Repeat while b is non-zero. This also makes a copy of b.

≧&θη

Bitwise And b with a.

≔⁻|θιηθ

Bitwise Or a with the copy of b, and subtract the above value, thus replacing a with the Bitwise Xor of a and b.

≦⊗η

Bitwise left shift b as it is now the carry.

⟦Iθ

Output the value of a on its own line.

\$\endgroup\$
2
\$\begingroup\$

Javascript ES6, 48 chars, uint32 full support

a=>b=>{for(;b;alert(a>>>0))[a,b]=[a^b,(a&b)<<1]}

Test with console.log instead of alert:

f=a=>b=>{for(;b;console.log(a>>>0))[a,b]=[a^b,(a&b)<<1]}

g=(x,y,...res)=>console.log(`=== ${x} ${y} => ${res} ===`)+f(x)(y)

g(2147483648, 2147483648, 0)
g(3000000000, 1, 3000000001)
g(2147483648, 0)
g(1, 1, 0, 2)
g(3, 17, 18, 16, 20)
g(6, 7, 1, 13)
g(21, 19, 6, 36, 32, 40)
g(10, 9, 3, 19)
g(20, 20, 0, 40)
.as-console-wrapper.as-console-wrapper { max-height: 100vh }

Javascript ES6, 43 chars, int32 except 2**32

a=>b=>{for(;b;alert(a))[a,b]=[a^b,(a&b)*2]}

Test with console.log instead of alert:

f=a=>b=>{for(;b;console.log(a))[a,b]=[a^b,(a&b)*2]}

g=(x,y,...res)=>console.log(`=== ${x} ${y} => ${res} ===`)+f(x)(y)

g(2147483648, 2147483648, 0, 'never')
g(3000000000, 3000000000, 0, 1705032704)
g(3000000000, 1, 3000000001)
g(2147483648, 0)
g(1, 1, 0, 2)
g(3, 17, 18, 16, 20)
g(6, 7, 1, 13)
g(21, 19, 6, 36, 32, 40)
g(10, 9, 3, 19)
g(20, 20, 0, 40)
.as-console-wrapper.as-console-wrapper { max-height: 100vh }

Javascript ES 2020, 44 chars, infinite integers

a=>b=>{for(;b;alert(a))[a,b]=[a^b,(a&b)*2n]}

Test with console.log instead of alert:

alert=x=>console.log(x+"")

f=a=>b=>{for(;b;alert(a))[a,b]=[a^b,(a&b)*2n]}

g=(x,y,...res)=>console.log(`=== ${x} ${y} => ${res} ===`)+f(x)(y)

g(2147483648n, 2147483648n, 0, 4294967296)
g(3000000000n, 3000000000n, 0, 6000000000)
g(3000000000n, 1n, 3000000001)
g(2147483648n, 0)
g(1n, 1n, 0, 2)
g(3n, 17n, 18, 16, 20)
g(6n, 7n, 1, 13)
g(21n, 19n, 6, 36, 32, 40)
g(10n, 9n, 3, 19)
g(20n, 20n, 0, 40)
.as-console-wrapper.as-console-wrapper { max-height: 100vh }

\$\endgroup\$
6
  • \$\begingroup\$ psst neither 2^31 nor 2^32 can be represented in any traditional integer format (which Javascript's integer type is) \$\endgroup\$
    – S.S. Anne
    Apr 28, 2020 at 0:01
  • \$\begingroup\$ This answer shows that they can ;) \$\endgroup\$
    – Qwertiy
    Apr 28, 2020 at 0:06
  • \$\begingroup\$ Sorry, meant to say "signed integer format". \$\endgroup\$
    – S.S. Anne
    Apr 28, 2020 at 0:06
  • \$\begingroup\$ Formally js doesn't have integer type at all, only double. And BigInt from 2020 standard. \$\endgroup\$
    – Qwertiy
    Apr 28, 2020 at 0:07
  • \$\begingroup\$ interesting. Still, 32-bit signed two's complement has bitwise 0x80000000 as negative. \$\endgroup\$
    – S.S. Anne
    Apr 28, 2020 at 0:08
2
\$\begingroup\$

Java (JDK), 54 bytes

(a,b)->{for(;b>0;b=(b&~a)*2)System.out.println(a^=b);}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 12 bytes

Δ`^=y`&D_#·)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

C# (Visual C# Interactive Compiler), 48 bytes

(a,b,c,d)=>{for(;b>0;c=a&b,d.Add(a^=b),b=c<<1);}

Try it online!

This is my first time using a for loop to do operations within the actual iterator, which feels weird, and uncomfortable, but also calming.

Mostly just tried to play with the reference, and make it more compact. Will be returning to this later. Need to double check my answer is fully legal (using the List), but this is my initial attempt.

More Info:

(a,b,c,d)=>{         //Pass in variables via lambda expression, and now a  for loop
                     //Note, the c# for statement format is: 
                     //for (initializer; condition; iterator)
                     ////body
                     //
    for(             //Start of for loop statement
        ;            //A mustache... jk. I am using no initializers, so just a ";" - totally blank
        b>0;         //My for loop conditional.  I used an int rather than a c bool, which is not as compact, maybe there's a better way        
                     //For loop Iterators:
        c=a&b,       //c is carry
        d.Add(a^=b), //Append to end of list: a equals a xor b
        b=c<<1       //left shift 
    )                //End Initializers, condition, and iterator parts of for loop           
    ;                //Body of for loop (nothing)
}                    //End lambda expression
\$\endgroup\$
6
  • \$\begingroup\$ Why no c# link? \$\endgroup\$
    – S.S. Anne
    Apr 28, 2020 at 0:09
  • \$\begingroup\$ Try the above link "Try It online!", does that work? \$\endgroup\$ Apr 28, 2020 at 2:48
  • \$\begingroup\$ I meant the link to an implementation. I've been curious to see what c# is like for a while. \$\endgroup\$
    – S.S. Anne
    Apr 28, 2020 at 3:09
  • \$\begingroup\$ I updated my code, sorry, I think that's what you meant right? \$\endgroup\$ Apr 28, 2020 at 3:53
  • \$\begingroup\$ It looks like you removed the link that TIO puts in for C# in your answer. I'll add it back, hang on... (there are some templates for Code Golf if you click the chain link on the top middle). I run Linux so Microsoft's C# doesn't work for me. Since I know that TIO runs on Linux, I knew there had to be a free implementation. That turns out to be Mono. \$\endgroup\$
    – S.S. Anne
    Apr 28, 2020 at 13:43
1
\$\begingroup\$

K4, 32 31 bytes

Solution:

1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\

Examples:

q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\1 1
0 2
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\3 17
18 16 20
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\6 7
1 13
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\21 19
6 36 32 40
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\10 9
3 19
q)k)1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\20 20
0 40

Explanation:

Lots of eaches...

1_*+(1 2*2/:'(~=/;&/)@\:0b\:')\ / the solution
    (                        )\ / iterate
                        0b\:'   / convert each into into binary
                     @\:        / apply (@) each-left (\:) function to right
             (   ;  )           / two item list
                  &/            / AND
              ~=/               / XOR
         2/:'                   / convert each from binary
     1 2*                       / multiply first item by 1, 2nd by 2
   +                            / flip
  *                             / first
1_                              / drop first element
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.