What is a ^ b and (a & b) << 1?

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;








26















I was doing this question in leetcode.



Request:




Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.




I can't understand the solution it gave



Could someone explain how this getSum function works?



Here is the answer in JS:






var getSum=function(a,b) 
const Sum = a^b; //I can't understand how those two line's code can
const carry = (a & b) << 1; //get the sum
if(!carry)
return Sum

return getSum(Sum,carry);
;
console.log(getSum(5,1));












share|improve this question



















  • 1





    Please edit your question to clarify what it is that you don't understand about those lines. Are you unfamiliar with what the ^, & and << operators do in JavaScript? Or are you just confused about how they can be used to calculate the sum of two numbers? "I can't understand it" is not a good question.

    – Ilmari Karonen
    Mar 16 at 20:16






  • 1





    Possible duplicate of Adding two numbers without + operator (Clarification)

    – Iłya Bursov
    Mar 16 at 22:57











  • @Ilmari Karonen Ok...I'll edit this question

    – Jacky
    Mar 17 at 4:56

















26















I was doing this question in leetcode.



Request:




Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.




I can't understand the solution it gave



Could someone explain how this getSum function works?



Here is the answer in JS:






var getSum=function(a,b) 
const Sum = a^b; //I can't understand how those two line's code can
const carry = (a & b) << 1; //get the sum
if(!carry)
return Sum

return getSum(Sum,carry);
;
console.log(getSum(5,1));












share|improve this question



















  • 1





    Please edit your question to clarify what it is that you don't understand about those lines. Are you unfamiliar with what the ^, & and << operators do in JavaScript? Or are you just confused about how they can be used to calculate the sum of two numbers? "I can't understand it" is not a good question.

    – Ilmari Karonen
    Mar 16 at 20:16






  • 1





    Possible duplicate of Adding two numbers without + operator (Clarification)

    – Iłya Bursov
    Mar 16 at 22:57











  • @Ilmari Karonen Ok...I'll edit this question

    – Jacky
    Mar 17 at 4:56













26












26








26


4






I was doing this question in leetcode.



Request:




Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.




I can't understand the solution it gave



Could someone explain how this getSum function works?



Here is the answer in JS:






var getSum=function(a,b) 
const Sum = a^b; //I can't understand how those two line's code can
const carry = (a & b) << 1; //get the sum
if(!carry)
return Sum

return getSum(Sum,carry);
;
console.log(getSum(5,1));












share|improve this question
















I was doing this question in leetcode.



Request:




Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.




I can't understand the solution it gave



Could someone explain how this getSum function works?



Here is the answer in JS:






var getSum=function(a,b) 
const Sum = a^b; //I can't understand how those two line's code can
const carry = (a & b) << 1; //get the sum
if(!carry)
return Sum

return getSum(Sum,carry);
;
console.log(getSum(5,1));








var getSum=function(a,b) 
const Sum = a^b; //I can't understand how those two line's code can
const carry = (a & b) << 1; //get the sum
if(!carry)
return Sum

return getSum(Sum,carry);
;
console.log(getSum(5,1));





var getSum=function(a,b) 
const Sum = a^b; //I can't understand how those two line's code can
const carry = (a & b) << 1; //get the sum
if(!carry)
return Sum

return getSum(Sum,carry);
;
console.log(getSum(5,1));






javascript bitwise-operators






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Mar 17 at 8:18









flppv

1,8631328




1,8631328










asked Mar 16 at 3:22









JackyJacky

320110




320110







  • 1





    Please edit your question to clarify what it is that you don't understand about those lines. Are you unfamiliar with what the ^, & and << operators do in JavaScript? Or are you just confused about how they can be used to calculate the sum of two numbers? "I can't understand it" is not a good question.

    – Ilmari Karonen
    Mar 16 at 20:16






  • 1





    Possible duplicate of Adding two numbers without + operator (Clarification)

    – Iłya Bursov
    Mar 16 at 22:57











  • @Ilmari Karonen Ok...I'll edit this question

    – Jacky
    Mar 17 at 4:56












  • 1





    Please edit your question to clarify what it is that you don't understand about those lines. Are you unfamiliar with what the ^, & and << operators do in JavaScript? Or are you just confused about how they can be used to calculate the sum of two numbers? "I can't understand it" is not a good question.

    – Ilmari Karonen
    Mar 16 at 20:16






  • 1





    Possible duplicate of Adding two numbers without + operator (Clarification)

    – Iłya Bursov
    Mar 16 at 22:57











  • @Ilmari Karonen Ok...I'll edit this question

    – Jacky
    Mar 17 at 4:56







1




1





Please edit your question to clarify what it is that you don't understand about those lines. Are you unfamiliar with what the ^, & and << operators do in JavaScript? Or are you just confused about how they can be used to calculate the sum of two numbers? "I can't understand it" is not a good question.

– Ilmari Karonen
Mar 16 at 20:16





Please edit your question to clarify what it is that you don't understand about those lines. Are you unfamiliar with what the ^, & and << operators do in JavaScript? Or are you just confused about how they can be used to calculate the sum of two numbers? "I can't understand it" is not a good question.

– Ilmari Karonen
Mar 16 at 20:16




1




1





Possible duplicate of Adding two numbers without + operator (Clarification)

– Iłya Bursov
Mar 16 at 22:57





Possible duplicate of Adding two numbers without + operator (Clarification)

– Iłya Bursov
Mar 16 at 22:57













@Ilmari Karonen Ok...I'll edit this question

– Jacky
Mar 17 at 4:56





@Ilmari Karonen Ok...I'll edit this question

– Jacky
Mar 17 at 4:56












4 Answers
4






active

oldest

votes


















26














Let's learn by example. Imagine that a = 3 and b = 5



In binary notation they are a = 0011 and b = 0101



XOR:
a^b is XOR operator. When compare two bits it returns 0 if they are same and 1 if they are different. 01^10 => 11



So when we're doing a^b result will be 0110.



AND + SHIFT



a&b performs logical AND operation. It returns 1 only when a = b = 1.



In our case the result is 0001



<< shifts it(adds 0 on the right side) and result became 0010 which sets carry variable true. (only 0000 will be false).



Next iterations:



Everything repeats but now a = 0110 and b = 0010 (Sum and carry from last execution)



Now a^b = 0100 and (a&b)<<1 = 0100



Repeating again.



Now a^b = 0000 and (a&b)<<1 = 1000



And again.



Now a^b = 1000 and (a&b)<<1 = 0000. Now carry is finally false. And we're returning 1000 which is decimal 8.



Everything worked fine since 3+5=8






share|improve this answer




















  • 2





    This only seems to discuss that particular case, not how the algorithm works in general. How are we to know from this that it works for all possible inputs?

    – ilkkachu
    Mar 16 at 22:01











  • @ilkkachu you can try different input values, it will work with maybe different number of iterations. My goal was to explain the algorithm by example.

    – flppv
    Mar 17 at 0:35


















35














It's basically replicating the half-adder



Adding 2 bits A and B produces 2 outputs: a sum and a carry bit like below



╔═══════╤═════════════╗
║ Input │ Output ║
╠═══╤═══╪═══════╤═════╣
║ A │ B │ carry │ sum ║
╟───┼───┼───────┼─────╢
║ 0 │ 0 │ 0 │ 0 ║
╟───┼───┼───────┼─────╢
║ 1 │ 0 │ 0 │ 1 ║
╟───┼───┼───────┼─────╢
║ 0 │ 1 │ 0 │ 1 ║
╟───┼───┼───────┼─────╢
║ 1 │ 1 │ 1 │ 0 ║
╚═══╧═══╧═══════╧═════╝


From the table we get the logic for the outputs: carry = A and B, sum = A xor B





XOR is also called a carry-less add operator, and represented by ⊕ with the + symbol inside



So the snippet above is working like this



const Sum=a^b; // sum = a xor b = a ⊕ b
const carry=(a&b)<<1; // carry = 2*(a and b), since we carry to the next bit
if(!carry)
return Sum; // no carry, so sum + carry = sum

return getSum(Sum,carry); // a + b = sum + carry


So a^b adds each bit in a and b simultaneously, leaving the non-carry sum of a and b in Sum. Then we have to add carry to the carry-less sum to get the final result, since we have only a half-adder instead of a full-adder which does a + b = a ⊕ b + carry



See also



  • Adding two numbers without + operator (Clarification)

  • What is the best way to add two numbers without using the + operator?

  • adds two numbers without using + or any arithmetic operators

  • Adding two numbers without using the addition operator





share|improve this answer

























  • If I'm not mistaken, it would be more accurate to say it replicates full adder, because of the function's recursive call to itself - one xor plus and stage leading to another.

    – Sergiy Kolodyazhnyy
    Mar 16 at 12:04











  • @SergiyKolodyazhnyy here the input has only a and b which is the half adder. The full adder capability is achieved by the recursive call which gives you a + b + 2*carry. A real full adder takes 3 inputs a + b + carryIn = sum + 2*carryOut

    – phuclv
    Mar 16 at 12:14






  • 2





    Might be worth pointing out that it's a half-adder for each bit simultaneously, unlike the truth table that only shows a single bit position.

    – ilkkachu
    Mar 16 at 21:59


















2














 int result = p ^ q; // XOR Operator, + without carry 0+0=0, 0+1=1+0=1, 1+1=0
int carry = (p & q) << 1; // Left Shift, 1+1=2
if (carry != 0)
return getSum(result, carry);

return result;


Start By p=5,q=6. Then the XOR would be,



0101
0110
------
0011


So, XORing results in (0011) which is actually 3 in decimal. Then ANDing p and q we get,



0101
0110
-------
0100


We get 4 (100 in binary) by ANDing 5 & 6, now if we left shift this value by 1, we get



 0100<<1=1000


So we get 8 (1000 in binary) after first recursion.As the result (carry variable) isnt zero, lets recursion again by xor value and carry value.



getSum(3, 8);


So, doing the first XORing we get,



0011
1000
-------
1011


The XORing this time yielded in 11 (1011 binary),so we perform the AND now,



0011
1000
-------
0000


We get all ZERO for ANDing 3 and 8, so this time the left shift operator also results in ZERO, as we have no 1 here which may give us a value by left shifing zeroes.
As the carry variable is now Zero, we come to the end of recursion and the XORed value will be the Sum, which is 11 (1011 in Binary).



Hope you get the working of the procedure. You can learn more by learning bitwise operation, as its the way the machine do the arithmatic operations.






share|improve this answer
































    0














    ^ is XOR, a bitwise operation. On a single bit, the rules are 0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 0, and 1 ^ 1 = 0, and you simply extend perform it on corresponding bits when dealing with multi-bit values. The name is short for "exclusive or", and comes from the fact that A ^ B is 1 if and only if either A or B is 1, not both. But, it's more interesting to talk about its other name, ⊕. ⊕ is + but slightly different. You'll notice that the rules for ⊕ are similar to the rules for addition: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10. ⊕ is +, except 1 ⊕ 1 = 0; that is, ⊕ is +, except without carrying. This holds for multiple bits: 011 + 001 = 100, because you carry a 1 out of the ones place into the twos place, and then carry a 1 again into the fours place. Then, 011 ⊕ 001 = 010, because you just don't carry.



    Now, when doing real addition, when do you carry? In binary, the answer is very simple: you carry a 1 into the next place when there are two 1s in a given place. This is easily understood as a bitwise AND, &. 1 & 1 = 1, and 0 otherwise. For 011 + 001, addition without carrying gives 011 ⊕ 001 = 010, and we can tell we need to carry a 1 out of the ones place because 011 & 001 = 001. The shifting in (a & b) << 1 turns a number "where do I need to carry from?" into "where do I need to add carries?": (011 & 001) << 1 = 010; I need to add a carry bit in the twos place.



    So, in getSum, we want to know a + b. We compute the addition without carrying with a ^ b, and we find where we need to add carry bits with (a & b) << 1. Now, we just need to add those two together. Well, we already have a function for adding numbers together; it's called getSum. So, we basically just write function getSum(a, b) return getSum(a ^ b, (a & b) << 1); , except we make sure to short-circuit if there is nothing to carry, saving us from infinite recursion.






    share|improve this answer























      Your Answer






      StackExchange.ifUsing("editor", function ()
      StackExchange.using("externalEditor", function ()
      StackExchange.using("snippets", function ()
      StackExchange.snippets.init();
      );
      );
      , "code-snippets");

      StackExchange.ready(function()
      var channelOptions =
      tags: "".split(" "),
      id: "1"
      ;
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function()
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled)
      StackExchange.using("snippets", function()
      createEditor();
      );

      else
      createEditor();

      );

      function createEditor()
      StackExchange.prepareEditor(
      heartbeatType: 'answer',
      autoActivateHeartbeat: false,
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader:
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      ,
      onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      );



      );













      draft saved

      draft discarded


















      StackExchange.ready(
      function ()
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55193135%2fwhat-is-a-b-and-a-b-1%23new-answer', 'question_page');

      );

      Post as a guest















      Required, but never shown

























      4 Answers
      4






      active

      oldest

      votes








      4 Answers
      4






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      26














      Let's learn by example. Imagine that a = 3 and b = 5



      In binary notation they are a = 0011 and b = 0101



      XOR:
      a^b is XOR operator. When compare two bits it returns 0 if they are same and 1 if they are different. 01^10 => 11



      So when we're doing a^b result will be 0110.



      AND + SHIFT



      a&b performs logical AND operation. It returns 1 only when a = b = 1.



      In our case the result is 0001



      << shifts it(adds 0 on the right side) and result became 0010 which sets carry variable true. (only 0000 will be false).



      Next iterations:



      Everything repeats but now a = 0110 and b = 0010 (Sum and carry from last execution)



      Now a^b = 0100 and (a&b)<<1 = 0100



      Repeating again.



      Now a^b = 0000 and (a&b)<<1 = 1000



      And again.



      Now a^b = 1000 and (a&b)<<1 = 0000. Now carry is finally false. And we're returning 1000 which is decimal 8.



      Everything worked fine since 3+5=8






      share|improve this answer




















      • 2





        This only seems to discuss that particular case, not how the algorithm works in general. How are we to know from this that it works for all possible inputs?

        – ilkkachu
        Mar 16 at 22:01











      • @ilkkachu you can try different input values, it will work with maybe different number of iterations. My goal was to explain the algorithm by example.

        – flppv
        Mar 17 at 0:35















      26














      Let's learn by example. Imagine that a = 3 and b = 5



      In binary notation they are a = 0011 and b = 0101



      XOR:
      a^b is XOR operator. When compare two bits it returns 0 if they are same and 1 if they are different. 01^10 => 11



      So when we're doing a^b result will be 0110.



      AND + SHIFT



      a&b performs logical AND operation. It returns 1 only when a = b = 1.



      In our case the result is 0001



      << shifts it(adds 0 on the right side) and result became 0010 which sets carry variable true. (only 0000 will be false).



      Next iterations:



      Everything repeats but now a = 0110 and b = 0010 (Sum and carry from last execution)



      Now a^b = 0100 and (a&b)<<1 = 0100



      Repeating again.



      Now a^b = 0000 and (a&b)<<1 = 1000



      And again.



      Now a^b = 1000 and (a&b)<<1 = 0000. Now carry is finally false. And we're returning 1000 which is decimal 8.



      Everything worked fine since 3+5=8






      share|improve this answer




















      • 2





        This only seems to discuss that particular case, not how the algorithm works in general. How are we to know from this that it works for all possible inputs?

        – ilkkachu
        Mar 16 at 22:01











      • @ilkkachu you can try different input values, it will work with maybe different number of iterations. My goal was to explain the algorithm by example.

        – flppv
        Mar 17 at 0:35













      26












      26








      26







      Let's learn by example. Imagine that a = 3 and b = 5



      In binary notation they are a = 0011 and b = 0101



      XOR:
      a^b is XOR operator. When compare two bits it returns 0 if they are same and 1 if they are different. 01^10 => 11



      So when we're doing a^b result will be 0110.



      AND + SHIFT



      a&b performs logical AND operation. It returns 1 only when a = b = 1.



      In our case the result is 0001



      << shifts it(adds 0 on the right side) and result became 0010 which sets carry variable true. (only 0000 will be false).



      Next iterations:



      Everything repeats but now a = 0110 and b = 0010 (Sum and carry from last execution)



      Now a^b = 0100 and (a&b)<<1 = 0100



      Repeating again.



      Now a^b = 0000 and (a&b)<<1 = 1000



      And again.



      Now a^b = 1000 and (a&b)<<1 = 0000. Now carry is finally false. And we're returning 1000 which is decimal 8.



      Everything worked fine since 3+5=8






      share|improve this answer















      Let's learn by example. Imagine that a = 3 and b = 5



      In binary notation they are a = 0011 and b = 0101



      XOR:
      a^b is XOR operator. When compare two bits it returns 0 if they are same and 1 if they are different. 01^10 => 11



      So when we're doing a^b result will be 0110.



      AND + SHIFT



      a&b performs logical AND operation. It returns 1 only when a = b = 1.



      In our case the result is 0001



      << shifts it(adds 0 on the right side) and result became 0010 which sets carry variable true. (only 0000 will be false).



      Next iterations:



      Everything repeats but now a = 0110 and b = 0010 (Sum and carry from last execution)



      Now a^b = 0100 and (a&b)<<1 = 0100



      Repeating again.



      Now a^b = 0000 and (a&b)<<1 = 1000



      And again.



      Now a^b = 1000 and (a&b)<<1 = 0000. Now carry is finally false. And we're returning 1000 which is decimal 8.



      Everything worked fine since 3+5=8







      share|improve this answer














      share|improve this answer



      share|improve this answer








      edited Mar 17 at 3:49

























      answered Mar 16 at 3:43









      flppvflppv

      1,8631328




      1,8631328







      • 2





        This only seems to discuss that particular case, not how the algorithm works in general. How are we to know from this that it works for all possible inputs?

        – ilkkachu
        Mar 16 at 22:01











      • @ilkkachu you can try different input values, it will work with maybe different number of iterations. My goal was to explain the algorithm by example.

        – flppv
        Mar 17 at 0:35












      • 2





        This only seems to discuss that particular case, not how the algorithm works in general. How are we to know from this that it works for all possible inputs?

        – ilkkachu
        Mar 16 at 22:01











      • @ilkkachu you can try different input values, it will work with maybe different number of iterations. My goal was to explain the algorithm by example.

        – flppv
        Mar 17 at 0:35







      2




      2





      This only seems to discuss that particular case, not how the algorithm works in general. How are we to know from this that it works for all possible inputs?

      – ilkkachu
      Mar 16 at 22:01





      This only seems to discuss that particular case, not how the algorithm works in general. How are we to know from this that it works for all possible inputs?

      – ilkkachu
      Mar 16 at 22:01













      @ilkkachu you can try different input values, it will work with maybe different number of iterations. My goal was to explain the algorithm by example.

      – flppv
      Mar 17 at 0:35





      @ilkkachu you can try different input values, it will work with maybe different number of iterations. My goal was to explain the algorithm by example.

      – flppv
      Mar 17 at 0:35













      35














      It's basically replicating the half-adder



      Adding 2 bits A and B produces 2 outputs: a sum and a carry bit like below



      ╔═══════╤═════════════╗
      ║ Input │ Output ║
      ╠═══╤═══╪═══════╤═════╣
      ║ A │ B │ carry │ sum ║
      ╟───┼───┼───────┼─────╢
      ║ 0 │ 0 │ 0 │ 0 ║
      ╟───┼───┼───────┼─────╢
      ║ 1 │ 0 │ 0 │ 1 ║
      ╟───┼───┼───────┼─────╢
      ║ 0 │ 1 │ 0 │ 1 ║
      ╟───┼───┼───────┼─────╢
      ║ 1 │ 1 │ 1 │ 0 ║
      ╚═══╧═══╧═══════╧═════╝


      From the table we get the logic for the outputs: carry = A and B, sum = A xor B





      XOR is also called a carry-less add operator, and represented by ⊕ with the + symbol inside



      So the snippet above is working like this



      const Sum=a^b; // sum = a xor b = a ⊕ b
      const carry=(a&b)<<1; // carry = 2*(a and b), since we carry to the next bit
      if(!carry)
      return Sum; // no carry, so sum + carry = sum

      return getSum(Sum,carry); // a + b = sum + carry


      So a^b adds each bit in a and b simultaneously, leaving the non-carry sum of a and b in Sum. Then we have to add carry to the carry-less sum to get the final result, since we have only a half-adder instead of a full-adder which does a + b = a ⊕ b + carry



      See also



      • Adding two numbers without + operator (Clarification)

      • What is the best way to add two numbers without using the + operator?

      • adds two numbers without using + or any arithmetic operators

      • Adding two numbers without using the addition operator





      share|improve this answer

























      • If I'm not mistaken, it would be more accurate to say it replicates full adder, because of the function's recursive call to itself - one xor plus and stage leading to another.

        – Sergiy Kolodyazhnyy
        Mar 16 at 12:04











      • @SergiyKolodyazhnyy here the input has only a and b which is the half adder. The full adder capability is achieved by the recursive call which gives you a + b + 2*carry. A real full adder takes 3 inputs a + b + carryIn = sum + 2*carryOut

        – phuclv
        Mar 16 at 12:14






      • 2





        Might be worth pointing out that it's a half-adder for each bit simultaneously, unlike the truth table that only shows a single bit position.

        – ilkkachu
        Mar 16 at 21:59















      35














      It's basically replicating the half-adder



      Adding 2 bits A and B produces 2 outputs: a sum and a carry bit like below



      ╔═══════╤═════════════╗
      ║ Input │ Output ║
      ╠═══╤═══╪═══════╤═════╣
      ║ A │ B │ carry │ sum ║
      ╟───┼───┼───────┼─────╢
      ║ 0 │ 0 │ 0 │ 0 ║
      ╟───┼───┼───────┼─────╢
      ║ 1 │ 0 │ 0 │ 1 ║
      ╟───┼───┼───────┼─────╢
      ║ 0 │ 1 │ 0 │ 1 ║
      ╟───┼───┼───────┼─────╢
      ║ 1 │ 1 │ 1 │ 0 ║
      ╚═══╧═══╧═══════╧═════╝


      From the table we get the logic for the outputs: carry = A and B, sum = A xor B





      XOR is also called a carry-less add operator, and represented by ⊕ with the + symbol inside



      So the snippet above is working like this



      const Sum=a^b; // sum = a xor b = a ⊕ b
      const carry=(a&b)<<1; // carry = 2*(a and b), since we carry to the next bit
      if(!carry)
      return Sum; // no carry, so sum + carry = sum

      return getSum(Sum,carry); // a + b = sum + carry


      So a^b adds each bit in a and b simultaneously, leaving the non-carry sum of a and b in Sum. Then we have to add carry to the carry-less sum to get the final result, since we have only a half-adder instead of a full-adder which does a + b = a ⊕ b + carry



      See also



      • Adding two numbers without + operator (Clarification)

      • What is the best way to add two numbers without using the + operator?

      • adds two numbers without using + or any arithmetic operators

      • Adding two numbers without using the addition operator





      share|improve this answer

























      • If I'm not mistaken, it would be more accurate to say it replicates full adder, because of the function's recursive call to itself - one xor plus and stage leading to another.

        – Sergiy Kolodyazhnyy
        Mar 16 at 12:04











      • @SergiyKolodyazhnyy here the input has only a and b which is the half adder. The full adder capability is achieved by the recursive call which gives you a + b + 2*carry. A real full adder takes 3 inputs a + b + carryIn = sum + 2*carryOut

        – phuclv
        Mar 16 at 12:14






      • 2





        Might be worth pointing out that it's a half-adder for each bit simultaneously, unlike the truth table that only shows a single bit position.

        – ilkkachu
        Mar 16 at 21:59













      35












      35








      35







      It's basically replicating the half-adder



      Adding 2 bits A and B produces 2 outputs: a sum and a carry bit like below



      ╔═══════╤═════════════╗
      ║ Input │ Output ║
      ╠═══╤═══╪═══════╤═════╣
      ║ A │ B │ carry │ sum ║
      ╟───┼───┼───────┼─────╢
      ║ 0 │ 0 │ 0 │ 0 ║
      ╟───┼───┼───────┼─────╢
      ║ 1 │ 0 │ 0 │ 1 ║
      ╟───┼───┼───────┼─────╢
      ║ 0 │ 1 │ 0 │ 1 ║
      ╟───┼───┼───────┼─────╢
      ║ 1 │ 1 │ 1 │ 0 ║
      ╚═══╧═══╧═══════╧═════╝


      From the table we get the logic for the outputs: carry = A and B, sum = A xor B





      XOR is also called a carry-less add operator, and represented by ⊕ with the + symbol inside



      So the snippet above is working like this



      const Sum=a^b; // sum = a xor b = a ⊕ b
      const carry=(a&b)<<1; // carry = 2*(a and b), since we carry to the next bit
      if(!carry)
      return Sum; // no carry, so sum + carry = sum

      return getSum(Sum,carry); // a + b = sum + carry


      So a^b adds each bit in a and b simultaneously, leaving the non-carry sum of a and b in Sum. Then we have to add carry to the carry-less sum to get the final result, since we have only a half-adder instead of a full-adder which does a + b = a ⊕ b + carry



      See also



      • Adding two numbers without + operator (Clarification)

      • What is the best way to add two numbers without using the + operator?

      • adds two numbers without using + or any arithmetic operators

      • Adding two numbers without using the addition operator





      share|improve this answer















      It's basically replicating the half-adder



      Adding 2 bits A and B produces 2 outputs: a sum and a carry bit like below



      ╔═══════╤═════════════╗
      ║ Input │ Output ║
      ╠═══╤═══╪═══════╤═════╣
      ║ A │ B │ carry │ sum ║
      ╟───┼───┼───────┼─────╢
      ║ 0 │ 0 │ 0 │ 0 ║
      ╟───┼───┼───────┼─────╢
      ║ 1 │ 0 │ 0 │ 1 ║
      ╟───┼───┼───────┼─────╢
      ║ 0 │ 1 │ 0 │ 1 ║
      ╟───┼───┼───────┼─────╢
      ║ 1 │ 1 │ 1 │ 0 ║
      ╚═══╧═══╧═══════╧═════╝


      From the table we get the logic for the outputs: carry = A and B, sum = A xor B





      XOR is also called a carry-less add operator, and represented by ⊕ with the + symbol inside



      So the snippet above is working like this



      const Sum=a^b; // sum = a xor b = a ⊕ b
      const carry=(a&b)<<1; // carry = 2*(a and b), since we carry to the next bit
      if(!carry)
      return Sum; // no carry, so sum + carry = sum

      return getSum(Sum,carry); // a + b = sum + carry


      So a^b adds each bit in a and b simultaneously, leaving the non-carry sum of a and b in Sum. Then we have to add carry to the carry-less sum to get the final result, since we have only a half-adder instead of a full-adder which does a + b = a ⊕ b + carry



      See also



      • Adding two numbers without + operator (Clarification)

      • What is the best way to add two numbers without using the + operator?

      • adds two numbers without using + or any arithmetic operators

      • Adding two numbers without using the addition operator






      share|improve this answer














      share|improve this answer



      share|improve this answer








      edited Mar 17 at 8:32

























      answered Mar 16 at 5:13









      phuclvphuclv

      16.3k956236




      16.3k956236












      • If I'm not mistaken, it would be more accurate to say it replicates full adder, because of the function's recursive call to itself - one xor plus and stage leading to another.

        – Sergiy Kolodyazhnyy
        Mar 16 at 12:04











      • @SergiyKolodyazhnyy here the input has only a and b which is the half adder. The full adder capability is achieved by the recursive call which gives you a + b + 2*carry. A real full adder takes 3 inputs a + b + carryIn = sum + 2*carryOut

        – phuclv
        Mar 16 at 12:14






      • 2





        Might be worth pointing out that it's a half-adder for each bit simultaneously, unlike the truth table that only shows a single bit position.

        – ilkkachu
        Mar 16 at 21:59

















      • If I'm not mistaken, it would be more accurate to say it replicates full adder, because of the function's recursive call to itself - one xor plus and stage leading to another.

        – Sergiy Kolodyazhnyy
        Mar 16 at 12:04











      • @SergiyKolodyazhnyy here the input has only a and b which is the half adder. The full adder capability is achieved by the recursive call which gives you a + b + 2*carry. A real full adder takes 3 inputs a + b + carryIn = sum + 2*carryOut

        – phuclv
        Mar 16 at 12:14






      • 2





        Might be worth pointing out that it's a half-adder for each bit simultaneously, unlike the truth table that only shows a single bit position.

        – ilkkachu
        Mar 16 at 21:59
















      If I'm not mistaken, it would be more accurate to say it replicates full adder, because of the function's recursive call to itself - one xor plus and stage leading to another.

      – Sergiy Kolodyazhnyy
      Mar 16 at 12:04





      If I'm not mistaken, it would be more accurate to say it replicates full adder, because of the function's recursive call to itself - one xor plus and stage leading to another.

      – Sergiy Kolodyazhnyy
      Mar 16 at 12:04













      @SergiyKolodyazhnyy here the input has only a and b which is the half adder. The full adder capability is achieved by the recursive call which gives you a + b + 2*carry. A real full adder takes 3 inputs a + b + carryIn = sum + 2*carryOut

      – phuclv
      Mar 16 at 12:14





      @SergiyKolodyazhnyy here the input has only a and b which is the half adder. The full adder capability is achieved by the recursive call which gives you a + b + 2*carry. A real full adder takes 3 inputs a + b + carryIn = sum + 2*carryOut

      – phuclv
      Mar 16 at 12:14




      2




      2





      Might be worth pointing out that it's a half-adder for each bit simultaneously, unlike the truth table that only shows a single bit position.

      – ilkkachu
      Mar 16 at 21:59





      Might be worth pointing out that it's a half-adder for each bit simultaneously, unlike the truth table that only shows a single bit position.

      – ilkkachu
      Mar 16 at 21:59











      2














       int result = p ^ q; // XOR Operator, + without carry 0+0=0, 0+1=1+0=1, 1+1=0
      int carry = (p & q) << 1; // Left Shift, 1+1=2
      if (carry != 0)
      return getSum(result, carry);

      return result;


      Start By p=5,q=6. Then the XOR would be,



      0101
      0110
      ------
      0011


      So, XORing results in (0011) which is actually 3 in decimal. Then ANDing p and q we get,



      0101
      0110
      -------
      0100


      We get 4 (100 in binary) by ANDing 5 & 6, now if we left shift this value by 1, we get



       0100<<1=1000


      So we get 8 (1000 in binary) after first recursion.As the result (carry variable) isnt zero, lets recursion again by xor value and carry value.



      getSum(3, 8);


      So, doing the first XORing we get,



      0011
      1000
      -------
      1011


      The XORing this time yielded in 11 (1011 binary),so we perform the AND now,



      0011
      1000
      -------
      0000


      We get all ZERO for ANDing 3 and 8, so this time the left shift operator also results in ZERO, as we have no 1 here which may give us a value by left shifing zeroes.
      As the carry variable is now Zero, we come to the end of recursion and the XORed value will be the Sum, which is 11 (1011 in Binary).



      Hope you get the working of the procedure. You can learn more by learning bitwise operation, as its the way the machine do the arithmatic operations.






      share|improve this answer





























        2














         int result = p ^ q; // XOR Operator, + without carry 0+0=0, 0+1=1+0=1, 1+1=0
        int carry = (p & q) << 1; // Left Shift, 1+1=2
        if (carry != 0)
        return getSum(result, carry);

        return result;


        Start By p=5,q=6. Then the XOR would be,



        0101
        0110
        ------
        0011


        So, XORing results in (0011) which is actually 3 in decimal. Then ANDing p and q we get,



        0101
        0110
        -------
        0100


        We get 4 (100 in binary) by ANDing 5 & 6, now if we left shift this value by 1, we get



         0100<<1=1000


        So we get 8 (1000 in binary) after first recursion.As the result (carry variable) isnt zero, lets recursion again by xor value and carry value.



        getSum(3, 8);


        So, doing the first XORing we get,



        0011
        1000
        -------
        1011


        The XORing this time yielded in 11 (1011 binary),so we perform the AND now,



        0011
        1000
        -------
        0000


        We get all ZERO for ANDing 3 and 8, so this time the left shift operator also results in ZERO, as we have no 1 here which may give us a value by left shifing zeroes.
        As the carry variable is now Zero, we come to the end of recursion and the XORed value will be the Sum, which is 11 (1011 in Binary).



        Hope you get the working of the procedure. You can learn more by learning bitwise operation, as its the way the machine do the arithmatic operations.






        share|improve this answer



























          2












          2








          2







           int result = p ^ q; // XOR Operator, + without carry 0+0=0, 0+1=1+0=1, 1+1=0
          int carry = (p & q) << 1; // Left Shift, 1+1=2
          if (carry != 0)
          return getSum(result, carry);

          return result;


          Start By p=5,q=6. Then the XOR would be,



          0101
          0110
          ------
          0011


          So, XORing results in (0011) which is actually 3 in decimal. Then ANDing p and q we get,



          0101
          0110
          -------
          0100


          We get 4 (100 in binary) by ANDing 5 & 6, now if we left shift this value by 1, we get



           0100<<1=1000


          So we get 8 (1000 in binary) after first recursion.As the result (carry variable) isnt zero, lets recursion again by xor value and carry value.



          getSum(3, 8);


          So, doing the first XORing we get,



          0011
          1000
          -------
          1011


          The XORing this time yielded in 11 (1011 binary),so we perform the AND now,



          0011
          1000
          -------
          0000


          We get all ZERO for ANDing 3 and 8, so this time the left shift operator also results in ZERO, as we have no 1 here which may give us a value by left shifing zeroes.
          As the carry variable is now Zero, we come to the end of recursion and the XORed value will be the Sum, which is 11 (1011 in Binary).



          Hope you get the working of the procedure. You can learn more by learning bitwise operation, as its the way the machine do the arithmatic operations.






          share|improve this answer















           int result = p ^ q; // XOR Operator, + without carry 0+0=0, 0+1=1+0=1, 1+1=0
          int carry = (p & q) << 1; // Left Shift, 1+1=2
          if (carry != 0)
          return getSum(result, carry);

          return result;


          Start By p=5,q=6. Then the XOR would be,



          0101
          0110
          ------
          0011


          So, XORing results in (0011) which is actually 3 in decimal. Then ANDing p and q we get,



          0101
          0110
          -------
          0100


          We get 4 (100 in binary) by ANDing 5 & 6, now if we left shift this value by 1, we get



           0100<<1=1000


          So we get 8 (1000 in binary) after first recursion.As the result (carry variable) isnt zero, lets recursion again by xor value and carry value.



          getSum(3, 8);


          So, doing the first XORing we get,



          0011
          1000
          -------
          1011


          The XORing this time yielded in 11 (1011 binary),so we perform the AND now,



          0011
          1000
          -------
          0000


          We get all ZERO for ANDing 3 and 8, so this time the left shift operator also results in ZERO, as we have no 1 here which may give us a value by left shifing zeroes.
          As the carry variable is now Zero, we come to the end of recursion and the XORed value will be the Sum, which is 11 (1011 in Binary).



          Hope you get the working of the procedure. You can learn more by learning bitwise operation, as its the way the machine do the arithmatic operations.







          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited Mar 16 at 3:57

























          answered Mar 16 at 3:52









          Ayan_84Ayan_84

          5321514




          5321514





















              0














              ^ is XOR, a bitwise operation. On a single bit, the rules are 0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 0, and 1 ^ 1 = 0, and you simply extend perform it on corresponding bits when dealing with multi-bit values. The name is short for "exclusive or", and comes from the fact that A ^ B is 1 if and only if either A or B is 1, not both. But, it's more interesting to talk about its other name, ⊕. ⊕ is + but slightly different. You'll notice that the rules for ⊕ are similar to the rules for addition: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10. ⊕ is +, except 1 ⊕ 1 = 0; that is, ⊕ is +, except without carrying. This holds for multiple bits: 011 + 001 = 100, because you carry a 1 out of the ones place into the twos place, and then carry a 1 again into the fours place. Then, 011 ⊕ 001 = 010, because you just don't carry.



              Now, when doing real addition, when do you carry? In binary, the answer is very simple: you carry a 1 into the next place when there are two 1s in a given place. This is easily understood as a bitwise AND, &. 1 & 1 = 1, and 0 otherwise. For 011 + 001, addition without carrying gives 011 ⊕ 001 = 010, and we can tell we need to carry a 1 out of the ones place because 011 & 001 = 001. The shifting in (a & b) << 1 turns a number "where do I need to carry from?" into "where do I need to add carries?": (011 & 001) << 1 = 010; I need to add a carry bit in the twos place.



              So, in getSum, we want to know a + b. We compute the addition without carrying with a ^ b, and we find where we need to add carry bits with (a & b) << 1. Now, we just need to add those two together. Well, we already have a function for adding numbers together; it's called getSum. So, we basically just write function getSum(a, b) return getSum(a ^ b, (a & b) << 1); , except we make sure to short-circuit if there is nothing to carry, saving us from infinite recursion.






              share|improve this answer



























                0














                ^ is XOR, a bitwise operation. On a single bit, the rules are 0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 0, and 1 ^ 1 = 0, and you simply extend perform it on corresponding bits when dealing with multi-bit values. The name is short for "exclusive or", and comes from the fact that A ^ B is 1 if and only if either A or B is 1, not both. But, it's more interesting to talk about its other name, ⊕. ⊕ is + but slightly different. You'll notice that the rules for ⊕ are similar to the rules for addition: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10. ⊕ is +, except 1 ⊕ 1 = 0; that is, ⊕ is +, except without carrying. This holds for multiple bits: 011 + 001 = 100, because you carry a 1 out of the ones place into the twos place, and then carry a 1 again into the fours place. Then, 011 ⊕ 001 = 010, because you just don't carry.



                Now, when doing real addition, when do you carry? In binary, the answer is very simple: you carry a 1 into the next place when there are two 1s in a given place. This is easily understood as a bitwise AND, &. 1 & 1 = 1, and 0 otherwise. For 011 + 001, addition without carrying gives 011 ⊕ 001 = 010, and we can tell we need to carry a 1 out of the ones place because 011 & 001 = 001. The shifting in (a & b) << 1 turns a number "where do I need to carry from?" into "where do I need to add carries?": (011 & 001) << 1 = 010; I need to add a carry bit in the twos place.



                So, in getSum, we want to know a + b. We compute the addition without carrying with a ^ b, and we find where we need to add carry bits with (a & b) << 1. Now, we just need to add those two together. Well, we already have a function for adding numbers together; it's called getSum. So, we basically just write function getSum(a, b) return getSum(a ^ b, (a & b) << 1); , except we make sure to short-circuit if there is nothing to carry, saving us from infinite recursion.






                share|improve this answer

























                  0












                  0








                  0







                  ^ is XOR, a bitwise operation. On a single bit, the rules are 0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 0, and 1 ^ 1 = 0, and you simply extend perform it on corresponding bits when dealing with multi-bit values. The name is short for "exclusive or", and comes from the fact that A ^ B is 1 if and only if either A or B is 1, not both. But, it's more interesting to talk about its other name, ⊕. ⊕ is + but slightly different. You'll notice that the rules for ⊕ are similar to the rules for addition: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10. ⊕ is +, except 1 ⊕ 1 = 0; that is, ⊕ is +, except without carrying. This holds for multiple bits: 011 + 001 = 100, because you carry a 1 out of the ones place into the twos place, and then carry a 1 again into the fours place. Then, 011 ⊕ 001 = 010, because you just don't carry.



                  Now, when doing real addition, when do you carry? In binary, the answer is very simple: you carry a 1 into the next place when there are two 1s in a given place. This is easily understood as a bitwise AND, &. 1 & 1 = 1, and 0 otherwise. For 011 + 001, addition without carrying gives 011 ⊕ 001 = 010, and we can tell we need to carry a 1 out of the ones place because 011 & 001 = 001. The shifting in (a & b) << 1 turns a number "where do I need to carry from?" into "where do I need to add carries?": (011 & 001) << 1 = 010; I need to add a carry bit in the twos place.



                  So, in getSum, we want to know a + b. We compute the addition without carrying with a ^ b, and we find where we need to add carry bits with (a & b) << 1. Now, we just need to add those two together. Well, we already have a function for adding numbers together; it's called getSum. So, we basically just write function getSum(a, b) return getSum(a ^ b, (a & b) << 1); , except we make sure to short-circuit if there is nothing to carry, saving us from infinite recursion.






                  share|improve this answer













                  ^ is XOR, a bitwise operation. On a single bit, the rules are 0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 0, and 1 ^ 1 = 0, and you simply extend perform it on corresponding bits when dealing with multi-bit values. The name is short for "exclusive or", and comes from the fact that A ^ B is 1 if and only if either A or B is 1, not both. But, it's more interesting to talk about its other name, ⊕. ⊕ is + but slightly different. You'll notice that the rules for ⊕ are similar to the rules for addition: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 10. ⊕ is +, except 1 ⊕ 1 = 0; that is, ⊕ is +, except without carrying. This holds for multiple bits: 011 + 001 = 100, because you carry a 1 out of the ones place into the twos place, and then carry a 1 again into the fours place. Then, 011 ⊕ 001 = 010, because you just don't carry.



                  Now, when doing real addition, when do you carry? In binary, the answer is very simple: you carry a 1 into the next place when there are two 1s in a given place. This is easily understood as a bitwise AND, &. 1 & 1 = 1, and 0 otherwise. For 011 + 001, addition without carrying gives 011 ⊕ 001 = 010, and we can tell we need to carry a 1 out of the ones place because 011 & 001 = 001. The shifting in (a & b) << 1 turns a number "where do I need to carry from?" into "where do I need to add carries?": (011 & 001) << 1 = 010; I need to add a carry bit in the twos place.



                  So, in getSum, we want to know a + b. We compute the addition without carrying with a ^ b, and we find where we need to add carry bits with (a & b) << 1. Now, we just need to add those two together. Well, we already have a function for adding numbers together; it's called getSum. So, we basically just write function getSum(a, b) return getSum(a ^ b, (a & b) << 1); , except we make sure to short-circuit if there is nothing to carry, saving us from infinite recursion.







                  share|improve this answer












                  share|improve this answer



                  share|improve this answer










                  answered Mar 17 at 2:44









                  HTNWHTNW

                  10.2k1832




                  10.2k1832



























                      draft saved

                      draft discarded
















































                      Thanks for contributing an answer to Stack Overflow!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid


                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.

                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function ()
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55193135%2fwhat-is-a-b-and-a-b-1%23new-answer', 'question_page');

                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown






                      Popular posts from this blog

                      How to check contact read email or not when send email to Individual?

                      Displaying single band from multi-band raster using QGIS

                      How many registers does an x86_64 CPU actually have?