Quote:Original post by Hodgman
Off the top of my head, I think it's something like return -(~x);...
How about return (int)( (unsigned int)(~x) ); ??
although I'm not sure...
With C, how can I add one but without the symbols +-*/
How about return (int)( (unsigned int)(~x) ); ??
although I'm not sure...
Quote:Original post by jorelmbNot quite. However this does work:
How about return (int)( (unsigned int)(~x) ); ??
although I'm not sure...
unsigned plus(unsigned n) { return abs(~n);}Here's a cute C99 solution:
unsigned plus(unsigned n) { return sizeof(struct { char padding, array[n]; });}[Edited by - implicit on October 28, 2008 11:22:09 PM]
static int AddAwesome(int x, char p[]){ return (int)&x[&p[1]];}int AddOne(int x){ return AddAwesome(x, 0);}Quote:Original post by hh10k
*** Source Snippet Removed ***
From MSDN
Quote:Usually, the value represented by postfix-expression is a pointer value, such as an array identifier, and expression is an integral value (including enumerated types). However, all that is required syntactically is that one of the expressions be of pointer type and the other be of integral type. Thus the integral value could be in the postfix-expression position and the pointer value could be in the brackets in the expression or subscript position.
Huh. You learn something new every day. The code threw me until I found that out.
Rewritten for genericity:
int Add(int x, int y){ char *p = 0; return (int)&x[&p[y]];}int main(){ int eight = Add(5, 3); return 0;}Quote:Original post by jhq
And I think the context of this question is to improve the efficiency, not only bit manipulation
If you think this, then either the company deserves to go bankrupt, or you have already failed the interview.
Quote:Original post by hh10k
*** Source Snippet Removed ***
Now that's freaking awesome. It took a whole lot of thinking to figure out why that one worked. I likes it. (thanks scjohnno for the link, I never would have figured it out without that).
Tested some of the versions
Result:
The times fluctuate with up to 5 ms each time I run the test. Quite surprising that the asm was so much slower though.
Heres the testing code
Edit: fixed
Result:
C time: 475 mspinacolada time: 630 msZahlman time: 473 mshh10k time: 472 msDevFred time: 941 msThe times fluctuate with up to 5 ms each time I run the test. Quite surprising that the asm was so much slower though.
Heres the testing code
#include stuff.. int addOnepinacolada(int i){ __asm { mov eax, i; add eax, 1; mov i, eax; }}int addOneDevFred(int i){ __asm { inc i; } return i;}int addOneC(int i){ return i + 1;}int increment(int x) { return (x & 1) ? (increment(x >> 1) << 1) : (x | 1);}static int AddAwesome(int x, char p[]){ return (int)&x[&p[1]];}int addOnehh10k(int x){ return AddAwesome(x, 0);}int _tmain(int argc, _TCHAR* argv[]){ timeBeginPeriod(1); int ta, tb; __int64 counts = 500000000; ta = timeGetTime(); for(__int64 i = 0; i < counts; i++) int q = addOneC(1234); tb = timeGetTime(); cout << "C time: " << tb - ta << " ms\n"; ta = timeGetTime(); for(__int64 i = 0; i < counts; i++) int q = addOnepinacolada(1234); tb = timeGetTime(); cout << "pinacolada time: " << tb - ta << " ms\n"; ta = timeGetTime(); for(__int64 i = 0; i < counts; i++) int q = increment(1234); tb = timeGetTime(); cout << "Zahlman time: " << tb - ta << " ms\n"; ta = timeGetTime(); for(__int64 i = 0; i < counts; i++) int q = addOnehh10k(1234); tb = timeGetTime(); cout << "hh10k time: " << tb - ta << " ms\n"; ta = timeGetTime(); for(__int64 i = 0; i < counts; i++) int q = addOneDevFred(1234); tb = timeGetTime(); cout << "DevFred time: " << tb - ta << " ms\n"; cin.ignore(1); timeEndPeriod(1); return 0;}Edit: fixed
Quote:Original post by Jesper T
Quite surprising that the asm was so much slower though.
No it's not. MSVC's optimiser is really paranoid about what you could do with your ASM, so it generates sub-optimal code around it - probably saving a whole bunch of registers, etc, which take time. As I predicted, the "C" version will be optimised to about as fast as you can get.
Quote:Original post by Jesper T
Tested some of the versions
Result:C time: 475 mspinacolada time: 630 msZahlman time: 473 mshh10k time: 472 msDevFred time: 941 ms
The times fluctuate with up to 5 ms each time I run the test. Quite surprising that the asm was so much slower though.
Was this a release build?
Some of those times should be 0. Any compiler should completely remove the inner for loop, since it doesn't do anything.
In the following:
for(__int64 i = 0; i < counts; i++) int q = addOneC(1234);q is inside the for loop scope, it's not printed, and as such should not be evaluated at all.
There was a thread a while back which discussed this.
The comparative test should probably be something like:
int q = 0;for(__int64 i = 0; i < counts; i++) q += addOneC(1234);std::cout << q;But, as it turns out, MVC is pretty clever, and is capable of evaluating such things during compile-time, resulting in entire above loop being eliminated.
Quote:And I think the context of this question is to improve the efficiency, not only bit manipulation
This is one of those pointless arcane questions HR likes to ask. They find such corner cases, the test how people can "think outside of box". It's all fairly pointless with regard to actual job demands, unless one is applying for puzzle maker.
IMHO, a much more valuable test would be to argument different solutions, what are the benefits, costs, and so on.
Also - posting __asm solutions should automatically fail the candidate due to inability to read or respect the requirements. I don't see Intel's architecture being mentioned anywhere.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
