How to add two numbers without using + operator in C using bit manipulation

Question

I recently came across this interview question and I'm not good in bit manipulation. Can you guys explain what the function 'f' does. I'm not sure what this recursive function does.

unsigned int f (unsigned int a , unsigned int b)
{
   return a ?   f ( (a&b) << 1, a ^b) : b;
}

I tried to paste the code in Visual Studio to test the logic but compiler is throwing some error message "cannot implicitly convert type 'uint' to 'bool'. Is the condition statement (a ?) in the return missing something? but I'm sure the interview question was exactly same as mentioned above

It's a great interview question: For the majority of programmers, it is not a test of skill, it a test of whether or not they have seen that trick in the past. Run from employers who are screening for "stupid programmer tricks." — Wayne Conrad
– Wayne Conrad, Commented Nov 1, 2013 at 21:01
Is there any way to figure this out besides trying a bunch of inputs and noting the results end up in the sum and just saying that's what it does after so many tests? — Kevin DiTraglia
– Kevin DiTraglia, Commented Nov 1, 2013 at 21:13

Kevin DiTraglia · Accepted Answer · 2013-11-01 21:25:43Z

4

Well already a few people in the comments mentioning this just adds two numbers. I'm not sure of a better way to figure that out than just try some inputs and note the results.

Ex:

f(5,1) --> returns f(2,4) --> returns f(0,6) --> returns 6

 1.) 5&1 = 1 bit shifted = 2:  5^1 = 4
 2.) 2&4 = 0 bit shifted = 0:  2^4 = 6
 3.) a = 0 so return b of 6

f(4,3) --> returns f(0,7) --> returns 7

1.) 4&3 = 0 bit shifted = 0:  4^3 = 7
2.) a = 0 so return b of 7

After you show a few examples of the output I suppose you could postulate f returns the two inputs added together.

answered Nov 1, 2013 at 21:25

Kevin DiTraglia

26.2k20 gold badges95 silver badges145 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

David C. Rankin · Accepted Answer · 2014-07-02 01:44:35Z

0

The prospective employer is either very thorough, or enjoys cruel & unusual punishment.

For the answer to the question, a review of the freely available chapter 2 from HackersDelight is worth its weight in gold. The addition operator in the function is taken from HAKMEM memo -- Item 23 and substitutes a left-shift in place of multiplying by 2. The original HAKMEM memo proposes:

(A AND B) + (A OR B) = A + B = (A XOR B) + 2 (A AND B)

or re-written in C:

x + y = (x ^ y) + 2 * (x & y)

The creative employer then uses (x & y) << 1 in place of 2 * (x & y) and recursion to compute to sum and or a and b until a = 0 at which time b is returned.

Glad it wasn't my interview.

edited Jul 2, 2014 at 1:44

answered Jul 2, 2014 at 0:33

David C. Rankin

85.1k6 gold badges67 silver badges95 bronze badges

Collectives™ on Stack Overflow

How to add two numbers without using + operator in C using bit manipulation

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related