Adobe Interview Question Software Engineer / Developers
Sum of two bits can be obtained by performing XOR (^) of the two bits. Carry bit can be obtained by performing AND (&) of two bits.
Above is simple Half Adder logic that can be used to add 2 single bits. We can extend this logic for integers. If x and y don’t have set bits at same position(s), then bitwise XOR (^) of x and y gives the sum of x and y. To incorporate common set bits also, bitwise AND (&) is used. Bitwise AND of x and y gives all carry bits. We calculate (x & y) << 1 and add it to x ^ y to get the required result.
#include<stdio.h>
int Add(int x, int y)
{
// Iterate till there is no carry
while (y != 0)
{
// carry now contains common set bits of x and y
int carry = x & y;
// Sum of bits of x and y where at least one of the bits is not set
x = x ^ y;
// Carry is shifted by one so that adding it to x gives the required sum
y = carry << 1;
}
return x;
}
int main()
{
printf("%d", Add(15, 32));
return 0;
}
Following is recursive implementation for the same approach.
int Add(int x, int y)
{
if (y == 0)
return x;
else
return Add( x ^ y, (x & y) << 1);
}
The following code in python will do.
If it has to be coded in c++, the for loop can use shifting as well.
add2(a, b, n) is a function to add n-bit numbers a and b.
##################
import sys
def lsb(n):
return n & 1
def add2(a, b, n):
s = 0
c = 0
for i in range(n):
lsba = lsb(a)
lsbb = lsb(b)
lsbc = lsb(c)
s += (lsba ^ lsbb ^ lsbc) << i
c = lsba & lsbb | lsbb & lsbc | lsbc & lsba
a >>= 1
b >>= 1
return s
if __name__ == "__main__":
print add2(int(sys.argv[1]), int(sys.argv[2]), int(sys.argv[3]))
unfortunately with python .. you need to atleast do proper indentation, else its really confusing to find out where the loop ends. (this code above has lost its indentation) and hence totally unreadable. (maybe you can put comments to indicate where the loops start and end)
yippie .. captcha is out :-)
Added some comments and fixed an error (used '|' instead of '+'). It's simply emulating a binary adder.
##################
import sys
# function to extract LSB
def lsb(n):
return n & 1
# function to add 2 n-bit numbers a & b
def add2(a, b, n):
# intialize sum and carry
s = 0
c = 0
# for loop begins
for i in range(n):
lsba = lsb(a)
lsbb = lsb(b)
lsbc = lsb(c)
s |= (lsba ^ lsbb ^ lsbc) << i
c = lsba & lsbb | lsbb & lsbc | lsbc & lsba
a >>= 1
b >>= 1
# for loop ends
return s
if __name__ == "__main__":
print add2(int(sys.argv[1]), int(sys.argv[2]),
int(sys.argv[3]))
Piece of code in java that serve this functionality is
public class Test1 {
public static void main(String[] args) {
System.out.println((new Test1()).addNumbers(8888, 1976543));
}
/**
* write an function to add two numbers, without using any arithmetic
* operator. Even the ++ in for statement is not allowed.
*/
public int addNumbers(int a, int b) {
String result = "";
String num1 = Integer.toBinaryString(a);
String num2 = Integer.toBinaryString(b);
boolean carry = false;
String res = "";
if (num1.length() == num2.length()) {
for (int i = num1.length() - 1; i >= 0; i--) {
res = addBinaryNumber(num1.charAt(i), num2.charAt(i));
if (carry) {
if (res.charAt(0) == '0')
carry = false;
res = addBinaryNumber(res.charAt(1), '1');
}
if (res.charAt(0) == '1')
carry = true;
result += res.charAt(1);
}
if (carry)
result += '1';
}
else if (num1.length() < num2.length()) {
for (int i = num1.length() - 1; i >= 0; i--) {
res = addBinaryNumber(num1.charAt(i), num2.charAt(i + num2.length() - num1.length()));
if (carry) {
if (res.charAt(0) == '0')
carry = false;
res = addBinaryNumber(res.charAt(1), '1');
}
if (res.charAt(0) == '1')
carry = true;
result += res.charAt(1);
}
for (int i = num2.length() - num1.length() - 1; i >= 0; i--) {
if (carry) {
res = addBinaryNumber(num2.charAt(i), '1');
carry = false;
if (res.charAt(0) == '1')
carry = true;
result += res.charAt(1);
}
else
result += num2.charAt(i);
}
if (carry)
result += '1';
}
else {
for (int i = num2.length() - 1; i >= 0; i--) {
res = addBinaryNumber(num2.charAt(i), num1.charAt(i + num1.length() - num2.length()));
if (carry) {
if (res.charAt(0) == '0')
carry = false;
res = addBinaryNumber(res.charAt(1), '1');
}
if (res.charAt(0) == '1')
carry = true;
result += res.charAt(1);
}
for (int i = num1.length() - num2.length() - 1; i >= 0; i--) {
if (carry) {
res = addBinaryNumber(num1.charAt(i), '1');
carry = false;
if (res.charAt(0) == '1')
carry = true;
result += res.charAt(1);
}
else
result += num1.charAt(i);
}
if (carry)
result += '1';
}
return BinaryToInt(reverse(result));
}
private String addBinaryNumber(char a, char b) {
String result = "";
if (a == '0' && b == '0')
result = "00";
if (a == '0' && b == '1')
result = "01";
if (a == '1' && b == '0')
result = "01";
if (a == '1' && b == '1')
result = "10";
return result;
}
private String reverse(String arg) {
String reverseString = "";
for (int i = arg.length() - 1; i >= 0; i--) {
reverseString += arg.charAt(i);
}
return reverseString;
}
private int BinaryToInt(String num) {
int result = 0;
for (int i = 0; i < num.length(); i++) {
if (num.charAt(i) == '1')
result += Math.pow(2, num.length() - i - 1);
}
return result;
}
}
public class Test1 {
public static void main(String[] args) {
System.out.println((new Test1()).addNumbers(8888, 1976543));
}
/**
* write an function to add two numbers, without using any arithmetic
* operator. Even the ++ in for statement is not allowed.
*/
public int addNumbers(int a, int b) {
String result = "";
String num1 = Integer.toBinaryString(a);
String num2 = Integer.toBinaryString(b);
boolean carry = false;
String res = "";
if (num1.length() == num2.length()) {
for (int i = num1.length() - 1; i >= 0; i--) {
res = addBinaryNumber(num1.charAt(i), num2.charAt(i));
if (carry) {
if (res.charAt(0) == '0')
carry = false;
res = addBinaryNumber(res.charAt(1), '1');
}
if (res.charAt(0) == '1')
carry = true;
result += res.charAt(1);
}
if (carry)
result += '1';
}
else if (num1.length() < num2.length()) {
for (int i = num1.length() - 1; i >= 0; i--) {
res = addBinaryNumber(num1.charAt(i), num2.charAt(i + num2.length() - num1.length()));
if (carry) {
if (res.charAt(0) == '0')
carry = false;
res = addBinaryNumber(res.charAt(1), '1');
}
if (res.charAt(0) == '1')
carry = true;
result += res.charAt(1);
}
for (int i = num2.length() - num1.length() - 1; i >= 0; i--) {
if (carry) {
res = addBinaryNumber(num2.charAt(i), '1');
carry = false;
if (res.charAt(0) == '1')
carry = true;
result += res.charAt(1);
}
else
result += num2.charAt(i);
}
if (carry)
result += '1';
}
else {
for (int i = num2.length() - 1; i >= 0; i--) {
res = addBinaryNumber(num2.charAt(i), num1.charAt(i + num1.length() - num2.length()));
if (carry) {
if (res.charAt(0) == '0')
carry = false;
res = addBinaryNumber(res.charAt(1), '1');
}
if (res.charAt(0) == '1')
carry = true;
result += res.charAt(1);
}
for (int i = num1.length() - num2.length() - 1; i >= 0; i--) {
if (carry) {
res = addBinaryNumber(num1.charAt(i), '1');
carry = false;
if (res.charAt(0) == '1')
carry = true;
result += res.charAt(1);
}
else
result += num1.charAt(i);
}
if (carry)
result += '1';
}
return BinaryToInt(reverse(result));
}
private String addBinaryNumber(char a, char b) {
String result = "";
if (a == '0' && b == '0')
result = "00";
if (a == '0' && b == '1')
result = "01";
if (a == '1' && b == '0')
result = "01";
if (a == '1' && b == '1')
result = "10";
return result;
}
private String reverse(String arg) {
String reverseString = "";
for (int i = arg.length() - 1; i >= 0; i--) {
reverseString += arg.charAt(i);
}
return reverseString;
}
private int BinaryToInt(String num) {
int result = 0;
for (int i = 0; i < num.length(); i++) {
if (num.charAt(i) == '1')
result += Math.pow(2, num.length() - i - 1);
}
return result;
}
}
int main(int argc, char *argv[])
{
if (argc != 3) {
cerr << "Enter a,b" << endl;
return 1;
}
int a = atoi(argv[1]);
int b = atoi(argv[2]);
int c = (a&b) << 1;
int sum = a^b;
while (c != 0) {
int tmp_sum = sum;
sum ^= c;
c = c & tmp_sum;
c <<= 1;
}
cout << "a+b = " << sum << endl;
return 0;
}
i think the while loop is not needed as it always happens once. we just need to xor with the carry
while (c != 0) {
int tmp_sum = sum;
sum ^= c;
c = c & tmp_sum;
c <<= 1;
}
replaced by
sum ^=c;
I think Rohan's answer is correct. If there is no while then it wont work when there is more than one carry.
Here is the recursive call. I am trying to figure out wat exactly it means. anyone ????
#include<stdio.h>
#include<conio.h>
int add(int a, int b){
printf("%d %d\n",a,b);
if (!a) return b;
else
return add((a & b) << 1, a ^ b);
}
int main(){
printf("Enter the two numbers: \n");
int a,b;
scanf("%d",&a);
scanf("%d",&b);
printf("Sum is: %d %d",add(a,b));
getch();
}
Here is the recursive call. I am trying to figure out wat exactly it means. anyone ????
#include<stdio.h>
#include<conio.h>
int add(int a, int b){
printf("%d %d\n",a,b);
if (!a) return b;
else
return add((a & b) << 1, a ^ b);
}
int main(){
printf("Enter the two numbers: \n");
int a,b;
scanf("%d",&a);
scanf("%d",&b);
printf("Sum is: %d %d",add(a,b));
getch();
}
@neoreaves
I think what u proposed is incorrect.
Take the example of 001 & 111
Step 1: a&b and a^b
001 001
&111 ^111
----- -----
001 110
(c) (sum)
Step2: c<< 010
Step3:sum^c
110
^010
-----
100 (incorrect-should be 1000)
Actually,the sequential XORing of c can pop up new carrys which have to be taken care of.
u've missed the last 2 steps here.
u have the new sum as 100 and carry also as 100 (110&010 << 1) . Now the xor (sum part) of these two is 000, while the carry is 100 & 100 << 1 which is 1000. Now the new sum is 0000 ^ 1000 which is 1000 and carry is 0000 & 1000 which is 0 and now we return the sum which is 1000!
Answer is very simple if both numbers are positive.
Lets say 2 numbers are A and B. where A is the bigger number and B is smaller number
To achieve A+B we can do this
A+B = A*2 - (A - B)
This works because A*2 essentially is A+A and then we subtract the extra that we added by sutracting the difference between A and B.
Here is recursive and non recursive answer:
// Add 2 unsigned digit without using arithmetic operator
public uint Add2DigitWithoutArithmeticOperator(uint i, uint j)
{
uint c = i & j;
while (c != 0)
{
i = i ^ j;
j = c << 1;
c = i & j;
}
return i ^ j;
}
public uint Add2DigitWithoutArithmeticOperatorRecursive(uint i, uint j)
{
uint c = i & j;
if (c == 0)
{
return i ^ j;
}
else
{
Add2DigitWithoutArithmeticOperatorRecursive(i ^ j, c << 1);
}
}
Can anybody pls explain how @rohan or @sv solution works ... Please give some hints so that we can start ....
the code with explanation ....
simple xoring gives us the sum but it will not handle carry . so we and first and then xor , at any instant if carry becomes 0 we stop and output .
int temp,sum,carry;
carry= (a&b)<<1;
sum=a^b;
while(carry!=0)
{
t=sum;
sum=sum^carry;
carry=carry^t;
carry<<=1;
}
clear explanation is here
- Jack December 28, 2014campuscoke.blogspot.in/2014/12/add-two-numbers-without-using.html