Disclaimer: I have 1 semester left of undergrad, so I've only done internship interviews so far. These are just my intuitions from visualizing myself as a senior engineer trying to hire competent engineers and whatever interview experience I have as a candidate.
During a technical interview, my experience is that it's best to talk to your interviewer and interact with them as you solve the problem. Usually you will get a nudge in the right direction, and you'll find the problem is not nearly as daunting as your initial impression.
Even if you don't end up getting the question right, the interviewer can get a positive impression based on your problem-solving approach and how well you communicate your thought process.
This really isn't as difficult of a question as you think, especially in an interactive environment (interview) as opposed to noninteractive (pencil and paper test). I would not be surprised to see this question on a test for sophomores or even 2nd semester freshmen in ECE here at UIUC. Not that everyone would get it right... But that's the point of tests and interviews anyway.
Finally, keep in mind that based on this question, the position the interview was for probably required some decent low-level understanding. If you find it daunting, it's probably not a position you would have interviewed for anyway, so you wouldn't have to worry about it. (Basing this on the statement that deriving addition with bit-logic would only be a "maybe" for you. This knowledge would be a given for most Computer Engineers or Electrical Engineers. I hope neither of those was your discipline of choice. No offense!)