Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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));
like image 700
Jacky Avatar asked Mar 16 '19 03:03

Jacky


People also ask

What is the A ab?

An ab is a stomach, or abdominal, muscle. Doing sit ups and crunches will help you tone your abs. Ab is shorthand for abdominal, which comes from the Latin abdomen, "belly," and it's a common name for what's formally known as the rectus abdominus muscle.

How do you explain AB testing?

A/B testing, also known as split testing, is a marketing experiment wherein you split your audience to test a number of variations of a campaign and determine which performs better. In other words, you can show version A of a piece of marketing content to one half of your audience, and version B to another.

Which is true of a B testing?

Essentially, A/B testing eliminates all the guesswork out of website optimization and enables experience optimizers to make data-backed decisions. In A/B testing, A refers to 'control' or the original testing variable. Whereas B refers to 'variation' or a new version of the original testing variable.

What is AB testing in digital marketing?

A/B testing (also known as split testing or bucket testing) is a method of comparing two versions of a webpage or app against each other to determine which one performs better.


3 Answers

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
like image 60
phuclv Avatar answered Oct 09 '22 12:10

phuclv


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

like image 31
flppv Avatar answered Oct 09 '22 10:10

flppv


 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.

like image 2
Ayan_84 Avatar answered Oct 09 '22 11:10

Ayan_84