CODEWITHSUNDEEP
c
Manish Kumar
Manish Kumar

Reputation: 1469

Comparison of two functions in C

int r2 (int a, int b)
{
return (a + (1<<(b-1))) >>b;
}

int r3 (int a, int b)
{
 return (a + (1<<(b-1)) -1 -(a>>31)) >>b;
}
  1. What is the difference between them?
  2. What could be the advantage of using extra operations in a way it is done in function r3()?

this question was asked in an interview to me. I was easily able to expand the expressions but I did not get the answer to second question.

Upvotes: 4

Views: 570

Answers (3)

interjay
interjay

Reputation: 110118

Both these functions do shift-right with rounding. i.e. they return the value a / pow(2,b) rounded to the nearest integer.

The difference is what happens when the fractional part of a / pow(2,b) is exactly one half. In this case, the first function will always round up, while the second will round towards zero.

The first function rounds up because (1<<(b-1)) / pow(2,b) is 0.5, so it essentially returns floor((a+0.5) / pow(2,b)).

The second function rounds towards zero because a>>31 is 0 for positive a or -1 for negative a (assuming 32-bit two's complement ints). For negative a, -1 + (a>>31) == 0, so it returns the same value as the first function, i.e. it will be rounded up towards zero. For a positive a, -1 + (a>>31) == -1, so it will subtract one before shifting right which will cause a fractional value of one half to be rounded down.

Upvotes: 3

chux
chux

Reputation: 153507

1.What is the difference between them?

Both perform a division by a power-of-2 and round the result to nearest (with UB if b is outside a small range). r2 rounds ties up. r3 rounds ties toward 0.

2.What could be the advantage of using extra operations in a way it is done in function r3()?

r3 performs a rounding that is like int division. int division truncates toward 0.

Note: With the advent of 64-bit int and also the rise of embedded processors using 16-bit int, hard coding the 31 is questionable coding. Something like a>>(sizeof(int) *CHAR_BIT - 1) should be used instead of a>>31.

For me, this was the first thing that stood out. It made an opportunity, with maybe knowing the company's market, to show how this narrow view of C could adversely affect the firm.
Look beyond only answering the question. Consider the question's applicability.

Upvotes: 1

Jonathan Mee
Jonathan Mee

Reputation: 38919

It looks like these functions are trying to provide rounding rather than truncation for the division of a positive number a by 2 to the power b. If you expanded these functions out for the interviewer I'm sure that you explained the power of 2 thing to him.

(Hopefully you didn't turn your nose up at these functions as much as I did or you probably didn't get the job.)
I would have told him that these functions differed in the way they round *.5 division results, to support my statement I would have showed him 3 examples:

a = 13, b = 3: r2 => 2, r3 => 2: 13 / 2 ^ 3 = 1.625
a = 12, b = 3: r2 => 2, r3 => 1: 12 / 2 ^ 3 = 1.5
a = 11, b = 3: r2 => 1, r3 => 1: 11 / 2 ^ 3 = 1.375

(I wouldn't stress about not getting that on the interview to much if you could expand these out for him that should have been enough. Looks like he just wanted to show his "mad c skilz" off to you.)

Upvotes: 1

Related Questions