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));
javascript
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));
javascript
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));
javascript
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
javascript
asked 49 mins ago
JackyJacky
1758
1758
add a comment |
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
2
Thanks for your explanation!
– Jacky
12 mins ago
You're welcome!
– vicodin
11 mins ago
1
Great explanation! I always find the bitwise operations hard to understand
– Francisco Hanna
6 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.
add a comment |
These are bitwise operations. They're close to hardware language.
7
Too short.You didn't explain why this works and how
– Jacky
41 mins ago
1
Link-only answers are discouraged here. Please add the relevant content in the answer itself.
– Ian McLaird
34 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
34 mins ago
@Nate Sorry,But I am not the computer science's student
– Jacky
31 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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
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
2
Thanks for your explanation!
– Jacky
12 mins ago
You're welcome!
– vicodin
11 mins ago
1
Great explanation! I always find the bitwise operations hard to understand
– Francisco Hanna
6 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
2
Thanks for your explanation!
– Jacky
12 mins ago
You're welcome!
– vicodin
11 mins ago
1
Great explanation! I always find the bitwise operations hard to understand
– Francisco Hanna
6 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
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 12 mins ago
answered 29 mins ago
vicodinvicodin
1,088624
1,088624
2
Thanks for your explanation!
– Jacky
12 mins ago
You're welcome!
– vicodin
11 mins ago
1
Great explanation! I always find the bitwise operations hard to understand
– Francisco Hanna
6 mins ago
add a comment |
2
Thanks for your explanation!
– Jacky
12 mins ago
You're welcome!
– vicodin
11 mins ago
1
Great explanation! I always find the bitwise operations hard to understand
– Francisco Hanna
6 mins ago
2
2
Thanks for your explanation!
– Jacky
12 mins ago
Thanks for your explanation!
– Jacky
12 mins ago
You're welcome!
– vicodin
11 mins ago
You're welcome!
– vicodin
11 mins ago
1
1
Great explanation! I always find the bitwise operations hard to understand
– Francisco Hanna
6 mins ago
Great explanation! I always find the bitwise operations hard to understand
– Francisco Hanna
6 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.
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.
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.
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 14 mins ago
answered 19 mins ago
Ayan_84Ayan_84
520513
520513
add a comment |
add a comment |
These are bitwise operations. They're close to hardware language.
7
Too short.You didn't explain why this works and how
– Jacky
41 mins ago
1
Link-only answers are discouraged here. Please add the relevant content in the answer itself.
– Ian McLaird
34 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
34 mins ago
@Nate Sorry,But I am not the computer science's student
– Jacky
31 mins ago
add a comment |
These are bitwise operations. They're close to hardware language.
7
Too short.You didn't explain why this works and how
– Jacky
41 mins ago
1
Link-only answers are discouraged here. Please add the relevant content in the answer itself.
– Ian McLaird
34 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
34 mins ago
@Nate Sorry,But I am not the computer science's student
– Jacky
31 mins ago
add a comment |
These are bitwise operations. They're close to hardware language.
These are bitwise operations. They're close to hardware language.
answered 45 mins ago
WofWcaWofWca
40819
40819
7
Too short.You didn't explain why this works and how
– Jacky
41 mins ago
1
Link-only answers are discouraged here. Please add the relevant content in the answer itself.
– Ian McLaird
34 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
34 mins ago
@Nate Sorry,But I am not the computer science's student
– Jacky
31 mins ago
add a comment |
7
Too short.You didn't explain why this works and how
– Jacky
41 mins ago
1
Link-only answers are discouraged here. Please add the relevant content in the answer itself.
– Ian McLaird
34 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
34 mins ago
@Nate Sorry,But I am not the computer science's student
– Jacky
31 mins ago
7
7
Too short.You didn't explain why this works and how
– Jacky
41 mins ago
Too short.You didn't explain why this works and how
– Jacky
41 mins ago
1
1
Link-only answers are discouraged here. Please add the relevant content in the answer itself.
– Ian McLaird
34 mins ago
Link-only answers are discouraged here. Please add the relevant content in the answer itself.
– Ian McLaird
34 mins ago
3
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
34 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
34 mins ago
@Nate Sorry,But I am not the computer science's student
– Jacky
31 mins ago
@Nate Sorry,But I am not the computer science's student
– Jacky
31 mins ago
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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