Sign in to follow this  

How to do adding/subtracting with bitwise operators

This topic is 4847 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I had to take a timed email test for a game job, and one of the questions was this (I had to pass on it): write a function "int add1(int val)" that returns val+1 without using +'s or -'s anywhere in your code. Yes, you will probably need to do some bitwise operations to accomplish this. How the heck to I do that? Is there a guide to this kind of stuff somewhere?

Share this post


Link to post
Share on other sites


int add1(int val)
{
if (val==0) return 1;
if (val==1) return 2;
if (val==2) return 3;
if (val==3) return 4;
if (val==4) return 5;
if (val==5) return 6;
if (val==6) return 7;
if (val==7) return 8;
...
...
if (val==2147483646) return 2147483647;
if (val==2147483647) return -2147483648;
if (val==-2147483648) return -2147483647;
if (val==-2147483647) return -2147483646;
...
...
if (val==-1) return 0;
}




They don't call me l337 h4x0r for nothing.

Share this post


Link to post
Share on other sites
A coworker came up with this.



int add1(int x)
{
return ~x * 0xFFFFFFFF;
}




Thanks for the interesting problem.
How long did you have to compleate this?

Armand

Share this post


Link to post
Share on other sites
int increment( int x )
{
int b = 1;
while ( ( x & b ) != 0 )
{
x ^= b;
b <<= 1;
}
x ^= b;

return x;
}


edit: just realized this is the same as Krumble's and similar to alvaro's. But Krumble's is less readable and alvaro's is un-readable and that would count against you in an interview.

Share this post


Link to post
Share on other sites
Most of the ones with a for loop seem to be implementations of how basic hardware addition works.

Armand: very neat -

return ~x * -1;

as inversion gives you -(x+1), I like it but feel quite stupid for not thinking of it. After programming on ARM which has MVN (which moves the bitwise inverse of a constant into a register) I really should have. :)

Share this post


Link to post
Share on other sites
OK. I had a change of heart, since the poster mentioned the problem was time-based and I know that some companies do issue time-based tests.

HOWEVER, I still consider interview help to generally be off topic, and may close future threads!

Share this post


Link to post
Share on other sites
Armand, I am profoundly impressed with your coworker! I think that's the best solution ever. Though I don't think I could improve upon its efficiency (without using ++, heh) I do think it can be rewritten a little more artistically...

int add1(int val) { return -~val; }

...Whaddaya think? ;)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
But you were not supposed to use any + or - signs.

Share this post


Link to post
Share on other sites
what is actually happening with this peice of code :S

int add1(int x)
{
return ~x * 0xFFFFFFFF;
}


could someone please explain to me what the ~x * 0xFFFFFFFF is all about its really confused me:S

Share this post


Link to post
Share on other sites
~x * 0xFFFFFFFF;

~x is the same as -(x + 1) or a one's complement operation

so it is -(x + 1) * 0xFFFFFFFF

0xFFFFFFFF = -1

so it is -(x + 1) * -1 which is x + 1

Share this post


Link to post
Share on other sites
wouldnt doing that multiply be more expensive than just using an actual add?
infact all the solutions are probably more expensive
so whats the point of them asking a question like that?
they want programmers who can write obfuscated code or something?
sure, having someone who is intelligent is important to any job, but shouldn't it be a more Useful demonstration of intelligence?
nothing against anyone or the clever answers theyve come up with; but id be a little annoyed at getting asked that kind of question for a job
its like one of those fake situtation word problems they give you in school; where the question is so contrived that its useless outside of that classroom

Share this post


Link to post
Share on other sites
Quote:
Original post by haphazardlynamed
... so whats the point of them asking a question like that? ...


They want to know how familiar you are with the bitwise operations -- that kind of knowledge is important in game programming. I sometimes ask this question in interviews.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
But you were not supposed to use any + or - signs.


Oh my apologies, I forgot about the "no - signs" part, and was only remembering the "no + signs" part.

Oh well, if they ever ask "no +s" but don't mention any lack of -s, then I'd do -~val. Flip the bits, then flip the bits and add one. How cool is that, ne? Fully equivalent to ~val * 0xFFFFFFFF, unless you've got a stupid compiler...

Share this post


Link to post
Share on other sites
Quote:
Original post by tok_junior
Using 0xFFFFFFFF takes 8 bits per byte, and using 32 bits for granted.
How about ~x*~0 ?
That doesn't depend on any specific architecture.

It still depends on the implementation of negative numbers being two's complement, which C and C++ don't guarantee.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
That doesn't depend on any specific architecture.

It still depends on the implementation of negative numbers being two's complement, which C and C++ don't guarantee.[/quote]

Ah, true. Although i've never seen or heard of an architecture that doesn't use two-complement for it. Doesn't mean there aren't any ofcourse.
Having for example 9 bits/byte, or 64bit math is way more common though :)

Share this post


Link to post
Share on other sites

This topic is 4847 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this