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));
javascript operators add
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 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));
javascript operators add
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
8 hours ago
1
Possible duplicate of Adding two numbers without + operator (Clarification)
– Iłya Bursov
6 hours ago
@Ilmari Karonen Ok...I'll edit this question
– Jacky
11 mins ago
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 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));
javascript operators add
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 operators add
javascript operators add
edited 10 mins ago
Jacky
asked yesterday
JackyJacky
25710
25710
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
8 hours ago
1
Possible duplicate of Adding two numbers without + operator (Clarification)
– Iłya Bursov
6 hours ago
@Ilmari Karonen Ok...I'll edit this question
– Jacky
11 mins ago
add a comment |
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
8 hours ago
1
Possible duplicate of Adding two numbers without + operator (Clarification)
– Iłya Bursov
6 hours ago
@Ilmari Karonen Ok...I'll edit this question
– Jacky
11 mins ago
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
8 hours ago
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
8 hours ago
1
1
Possible duplicate of Adding two numbers without + operator (Clarification)
– Iłya Bursov
6 hours ago
Possible duplicate of Adding two numbers without + operator (Clarification)
– Iłya Bursov
6 hours ago
@Ilmari Karonen Ok...I'll edit this question
– Jacky
11 mins ago
@Ilmari Karonen Ok...I'll edit this question
– Jacky
11 mins ago
add a comment |
4 Answers
4
active
oldest
votes
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
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
7 hours ago
@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
4 hours ago
add a comment |
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
So the snippet above is working like this
const Sum=a^b; // sum = a xor 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
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
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
17 hours ago
@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 youa + b + 2*carry
. A real full adder takes 3 inputsa + b + carryIn = sum + 2*carryOut
– phuclv
16 hours ago
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
7 hours 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 |
^
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 1
s 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.
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-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
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
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
7 hours ago
@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
4 hours ago
add a comment |
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
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
7 hours ago
@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
4 hours ago
add a comment |
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
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
edited 1 hour ago
answered yesterday
flppvflppv
1,317725
1,317725
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
7 hours ago
@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
4 hours ago
add a comment |
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
7 hours ago
@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
4 hours ago
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
7 hours ago
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
7 hours ago
@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
4 hours ago
@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
4 hours ago
add a comment |
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
So the snippet above is working like this
const Sum=a^b; // sum = a xor 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
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
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
17 hours ago
@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 youa + b + 2*carry
. A real full adder takes 3 inputsa + b + carryIn = sum + 2*carryOut
– phuclv
16 hours ago
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
7 hours ago
add a comment |
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
So the snippet above is working like this
const Sum=a^b; // sum = a xor 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
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
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
17 hours ago
@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 youa + b + 2*carry
. A real full adder takes 3 inputsa + b + carryIn = sum + 2*carryOut
– phuclv
16 hours ago
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
7 hours ago
add a comment |
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
So the snippet above is working like this
const Sum=a^b; // sum = a xor 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
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
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
So the snippet above is working like this
const Sum=a^b; // sum = a xor 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
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
answered 23 hours ago
phuclvphuclv
15.5k854229
15.5k854229
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
17 hours ago
@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 youa + b + 2*carry
. A real full adder takes 3 inputsa + b + carryIn = sum + 2*carryOut
– phuclv
16 hours ago
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
7 hours ago
add a comment |
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
17 hours ago
@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 youa + b + 2*carry
. A real full adder takes 3 inputsa + b + carryIn = sum + 2*carryOut
– phuclv
16 hours ago
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
7 hours ago
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
17 hours ago
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
17 hours ago
@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
16 hours ago
@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
16 hours ago
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
7 hours ago
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
7 hours 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 yesterday
answered yesterday
Ayan_84Ayan_84
530513
530513
add a comment |
add a comment |
^
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 1
s 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.
add a comment |
^
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 1
s 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.
add a comment |
^
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 1
s 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.
^
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 1
s 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.
answered 2 hours ago
HTNWHTNW
10.1k1832
10.1k1832
add a comment |
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-a-b-and-a-b-1%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
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
8 hours ago
1
Possible duplicate of Adding two numbers without + operator (Clarification)
– Iłya Bursov
6 hours ago
@Ilmari Karonen Ok...I'll edit this question
– Jacky
11 mins ago