[bmay]

You need some cleverness to code an add(x, y) method with only bitwise operators.

Then, you need to code a multiply(x, y) method using some more bit shifting cleverness and your new add method.

Then, do repeated squaring using your new multiply method.

[foldr]

Sure, but that's not a very satisfying answer because it doesn't rely on any special insight about how exponention works. It would be better to just ask someone to code up addition and/or multiplication using bitwise operations if that's what you want to test. That's sort of a reasonable question in the case of addition. Asking someone to implement multiplication using bitwise operations in a phone interview would be pretty crazy, though.