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 answer's JS:

var getSum=function(a,b){

         const Sum=a^b;//I can't understand it.Please give me an example to understand it

         const carry=(a&b)<<1;//I can't understand it too

               if(!carry){

                    return Sum

               }

        return getSum(Sum,carry);

};

console.log(getSum(5,1));

asked 1 hour ago

Jacky

1758

add a comment |

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 answer's JS:

var getSum=function(a,b){

         const Sum=a^b;//I can't understand it.Please give me an example to understand it

         const carry=(a&b)<<1;//I can't understand it too

               if(!carry){

                    return Sum

               }

        return getSum(Sum,carry);

};

console.log(getSum(5,1));

asked 1 hour ago

Jacky

1758

add a comment |

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 answer's JS:

var getSum=function(a,b){

         const Sum=a^b;//I can't understand it.Please give me an example to understand it

         const carry=(a&b)<<1;//I can't understand it too

               if(!carry){

                    return Sum

               }

        return getSum(Sum,carry);

};

console.log(getSum(5,1));

asked 1 hour ago

Jacky

1758

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 answer's JS:

var getSum=function(a,b){

         const Sum=a^b;//I can't understand it.Please give me an example to understand it

         const carry=(a&b)<<1;//I can't understand it too

               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 it.Please give me an example to understand it

         const carry=(a&b)<<1;//I can't understand it too

               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 it.Please give me an example to understand it

         const carry=(a&b)<<1;//I can't understand it too

               if(!carry){

                    return Sum

               }

        return getSum(Sum,carry);

};

console.log(getSum(5,1));

javascript

asked 1 hour ago

Jacky

1758

asked 1 hour ago

Jacky

1758

asked 1 hour ago

Jacky

1758

asked 1 hour ago

Jacky

1758

asked 1 hour ago

Jacky

1758

add a comment |

3 Answers
3

active

oldest

votes

Let's 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 (6 in decimal)

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

edited 30 mins ago

answered 48 mins ago

vicodin

1,097624

2

Thanks for your explanation!

– Jacky
30 mins ago

You're welcome!

– vicodin
30 mins ago

1

Great explanation! I always find the bitwise operations hard to understand

– Francisco Hanna
24 mins ago

add a comment |

 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.

edited 33 mins ago

answered 38 mins ago

Ayan_84

520513

add a comment |

-1

These are bitwise operations. They're close to hardware language.

answered 1 hour ago

WofWca

40819

7

Too short.You didn't explain why this works and how

– Jacky
1 hour ago

1

Link-only answers are discouraged here. Please add the relevant content in the answer itself.

– Ian McLaird
53 mins ago

3

It’s binary math. WofWca would have to give you a very very long explanation on binary to explain it. You should really read the W3 Schools article or watch some videos on Bitwise calculations. It’s the kind of thing that would be a few days of class work in college. The comment about link-only answers is fair, but I doubt you’ll grasp the concept from a StackOverflow post alone though.

– Nate
52 mins ago

@Nate Sorry,But I am not the computer science's student

– Jacky
49 mins ago

add a comment |

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

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

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

Post as a guest

Name

Required, but never shown

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

Let's 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 (6 in decimal)

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

edited 30 mins ago

answered 48 mins ago

vicodin

1,097624

2

Thanks for your explanation!

– Jacky
30 mins ago

You're welcome!

– vicodin
30 mins ago

1

Great explanation! I always find the bitwise operations hard to understand

– Francisco Hanna
24 mins ago

add a comment |

Let's 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 (6 in decimal)

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

edited 30 mins ago

answered 48 mins ago

vicodin

1,097624

2

Thanks for your explanation!

– Jacky
30 mins ago

You're welcome!

– vicodin
30 mins ago

1

Great explanation! I always find the bitwise operations hard to understand

– Francisco Hanna
24 mins ago

add a comment |

Let's 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 (6 in decimal)

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

edited 30 mins ago

answered 48 mins ago

vicodin

1,097624

Let's 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 (6 in decimal)

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

edited 30 mins ago

answered 48 mins ago

vicodin

1,097624

edited 30 mins ago

answered 48 mins ago

vicodin

1,097624

answered 48 mins ago

vicodin

1,097624

answered 48 mins ago

vicodin

1,097624

2

Thanks for your explanation!

– Jacky
30 mins ago

You're welcome!

– vicodin
30 mins ago

1

Great explanation! I always find the bitwise operations hard to understand

– Francisco Hanna
24 mins ago

add a comment |

2

Thanks for your explanation!

– Jacky
30 mins ago

You're welcome!

– vicodin
30 mins ago

1

Great explanation! I always find the bitwise operations hard to understand

– Francisco Hanna
24 mins ago

Thanks for your explanation!

– Jacky
30 mins ago

You're welcome!

– vicodin
30 mins ago

Great explanation! I always find the bitwise operations hard to understand

– Francisco Hanna
24 mins ago

add a comment |

 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

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.

edited 33 mins ago

answered 38 mins ago

Ayan_84

520513

add a comment |

 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

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.

edited 33 mins ago

answered 38 mins ago

Ayan_84

520513

add a comment |

 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

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.

edited 33 mins ago

answered 38 mins ago

Ayan_84

520513

 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

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.

edited 33 mins ago

answered 38 mins ago

Ayan_84

520513

edited 33 mins ago

answered 38 mins ago

Ayan_84

520513

answered 38 mins ago

Ayan_84

520513

answered 38 mins ago

Ayan_84

520513

add a comment |

-1

These are bitwise operations. They're close to hardware language.

answered 1 hour ago

WofWca

40819

7

Too short.You didn't explain why this works and how

– Jacky
1 hour ago

1

Link-only answers are discouraged here. Please add the relevant content in the answer itself.

– Ian McLaird
53 mins ago

3

It’s binary math. WofWca would have to give you a very very long explanation on binary to explain it. You should really read the W3 Schools article or watch some videos on Bitwise calculations. It’s the kind of thing that would be a few days of class work in college. The comment about link-only answers is fair, but I doubt you’ll grasp the concept from a StackOverflow post alone though.

– Nate
52 mins ago

@Nate Sorry,But I am not the computer science's student

– Jacky
49 mins ago

add a comment |

-1

These are bitwise operations. They're close to hardware language.

answered 1 hour ago

WofWca

40819

7

Too short.You didn't explain why this works and how

– Jacky
1 hour ago

1

Link-only answers are discouraged here. Please add the relevant content in the answer itself.

– Ian McLaird
53 mins ago

3

It’s binary math. WofWca would have to give you a very very long explanation on binary to explain it. You should really read the W3 Schools article or watch some videos on Bitwise calculations. It’s the kind of thing that would be a few days of class work in college. The comment about link-only answers is fair, but I doubt you’ll grasp the concept from a StackOverflow post alone though.

– Nate
52 mins ago

@Nate Sorry,But I am not the computer science's student

– Jacky
49 mins ago

add a comment |

-1

These are bitwise operations. They're close to hardware language.

answered 1 hour ago

WofWca

40819

These are bitwise operations. They're close to hardware language.

answered 1 hour ago

WofWca

40819

answered 1 hour ago

WofWca

40819

answered 1 hour ago

WofWca

40819

answered 1 hour ago

WofWca

40819

7

Too short.You didn't explain why this works and how

– Jacky
1 hour ago

1

Link-only answers are discouraged here. Please add the relevant content in the answer itself.

– Ian McLaird
53 mins ago

3

It’s binary math. WofWca would have to give you a very very long explanation on binary to explain it. You should really read the W3 Schools article or watch some videos on Bitwise calculations. It’s the kind of thing that would be a few days of class work in college. The comment about link-only answers is fair, but I doubt you’ll grasp the concept from a StackOverflow post alone though.

– Nate
52 mins ago

@Nate Sorry,But I am not the computer science's student

– Jacky
49 mins ago

add a comment |

7

Too short.You didn't explain why this works and how

– Jacky
1 hour ago

1

Link-only answers are discouraged here. Please add the relevant content in the answer itself.

– Ian McLaird
53 mins ago

3

It’s binary math. WofWca would have to give you a very very long explanation on binary to explain it. You should really read the W3 Schools article or watch some videos on Bitwise calculations. It’s the kind of thing that would be a few days of class work in college. The comment about link-only answers is fair, but I doubt you’ll grasp the concept from a StackOverflow post alone though.

– Nate
52 mins ago

@Nate Sorry,But I am not the computer science's student

– Jacky
49 mins ago

Too short.You didn't explain why this works and how

– Jacky
1 hour ago

Link-only answers are discouraged here. Please add the relevant content in the answer itself.

– Ian McLaird
53 mins ago

It’s binary math. WofWca would have to give you a very very long explanation on binary to explain it. You should really read the W3 Schools article or watch some videos on Bitwise calculations. It’s the kind of thing that would be a few days of class work in college. The comment about link-only answers is fair, but I doubt you’ll grasp the concept from a StackOverflow post alone though.

– Nate
52 mins ago

@Nate Sorry,But I am not the computer science's student

– Jacky
49 mins ago

add a comment |

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

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Bdtyktl

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

3 Answers
3

Your Answer

Post as a guest

3 Answers
3

3 Answers
3

Post as a guest

Popular posts from this blog

flock() on closed filehandle LOCK_FILE at /usr/bin/apt-mirror

Mangá

Eduardo VII do Reino Unido

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

3 Answers 3

Your Answer

Sign up or log in

Post as a guest

Post as a guest

3 Answers 3

3 Answers 3

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Popular posts from this blog

flock() on closed filehandle LOCK_FILE at /usr/bin/apt-mirror

Mangá

Eduardo VII do Reino Unido

3 Answers
3

3 Answers
3

3 Answers
3