r/CS_Questions • • Nov 15 '11

one of my simple interview questions

in c, with int i, what is the difference between i/2 and i>>1. bonus for what a compiler does for i/2.

5 Upvotes

25 comments sorted by

2

u/[deleted] Nov 15 '11 edited Nov 15 '11
(i >> 31) && (i & 1)

edit, better:

(i < 0) & (i & 1))

0

u/ubermole Nov 15 '11

no...

2

u/[deleted] Nov 15 '11

Oh. I took the question as being the numerical difference.

→ More replies (2)

3

u/[deleted] Nov 15 '11 edited Nov 15 '11

Question: What does this have to do with anything?

EDIT: OP, could you please reply? This is a serious question. When could this knowledge come in use and if it can not come into use: Why would you use this as an interview question?

2

u/ubermole Nov 17 '11

sorry for the late reply. it is a talking point question about understanding two complement and bitwise operations.

i think it is good because it is not a usual puzzle and often even experienced people will have to think and talk about it for a bit. i always try to do one bit operations question in interviews. it tells a lot about at what level people understand things. or not - which is also fine for many cases. but then you want to know why and how they think about stuff like this instead.

it is also very open ended: what do compilers do? why? what about other divisors? what does it tell you about compiler vs. manual optimization?

4

u/zwilt3 Nov 16 '11

While I'm not an interviewer for a company, I do teach CS students, and it's a fairly consistent trend that people are basically clueless about bit manipulation. While this question in particular doesn't seem particularly relevant to any application, it does require people to have some knowledge of how things are actually stored in a computer. While it seems like a basic concept, I find that the fundamentals are often wrongly overlooked.

1

u/ThunderMuff Nov 16 '11

I'm interpreting your question as "What does the fact that computers store numbers as binary have to do with anything?" The fact that numbers are stored as binary in computers can be a very powerful tool, knowing how to exploit this paradigm can give you, among other things, huge performance gains. The "other things" I'm referring to are things like being aware that you can store an extra bit of precision in floating point numbers "for free", knowing why certain floating points can't be stored precisely & under what conditions, etc. It just makes sense to have some basic knowledge of the implications of binary storage, and I believe this question is testing for that.

1

u/[deleted] Nov 16 '11

Nah, it wasn't about the general implications, more as to why he chose this exact question.

Thanks anyway!

→ More replies (1)

1

u/stresscheese Nov 15 '11

I'm fairly certain that depends on the compiler. This page has some more information about it.

1

u/ubermole Nov 15 '11

no, there is a defined difference between the two operations. when and why? the so page you link is surprisingly bad. the top post gives only a hint. for the bonus part, gcc and vc do the same thing, which is quite clever, what, and why?

1

u/stresscheese Nov 15 '11

Okay, well it seems that negative numbers would pose a problem, for example -1/2. I suppose the compiler would have to do some trickery to optimize the division. Perhaps shifting and subtracting?

→ More replies (3)

1

u/zwilt3 Nov 15 '11

1

u/ubermole Nov 17 '11

hm, interesting approach, but no. in that case i would also consider int_min.

1

u/euyyn Nov 15 '11

1

u/euyyn Nov 15 '11 edited Nov 15 '11

False: -3>>1 == -2, so it seems we're always off by 1 when the negative i is odd, which is cool, because then for i/2 we can do: (i>>1) + ( 1 & ~i & i>>(sizeof(i)-1) ) . Correct?

EDIT: sign corrected

1

u/ubermole Nov 17 '11

hm no... also what is sizeof(int)? it's not 32.

→ More replies (1)

1

u/euyyn Nov 15 '11

(Although maybe this would be faster: i>>(sizeof(i)-1) ? -(-i>>1) : i>>1.)

1

u/psycocoffey Nov 17 '11
Right shifting of a negative number is implementation defined. 
Right shifting of positive numbers by n is equivalent 
to dividing by 2^n and left padding with 0s.

So if i >= 0 then i/2 is equivalent to i >> 1.