# 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.

## 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 on other sites

int add1(int val){	__asm	{		mov eax,val		inc eax		ret	}}

##### Share on other sites
int add1(int x){  int bits_to_change=0;  for(int bit=1;bits_to_change|=bit,x&bit;bit<<=1);  return x^bits_to_change;}

##### Share on other sites
Another way:
int add1(int x){  return x&1?add1((unsigned)x>>1)<<1:x|1;}

##### Share on other sites
int add1(int x) {  for(int b=1; b&&(x&b); b<<=1)    x^=b;  return x|b;}works on negatives too.

##### 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 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 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 on other sites
Alvaro's was readable. The recursion makes it quite easy to read, easier, in fact, than an iterative solution.

##### 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 on other sites
return (int)&((char *) val)[1];

##### Share on other sites
Thread closing! It is off topic to ask for help with job interview questions or tests!

##### 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 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; }

##### Share on other sites
But you were not supposed to use any + or - signs.

##### Share on other sites
what is actually happening with this peice of code :S

{
return ~x * 0xFFFFFFFF;
}

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

##### 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 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 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 on other sites
Quote:
 Original post by O_o......

Cheers :)

##### Share on other sites
Quote:
 Original post by Anonymous PosterBut 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 on other sites
You could also just do this x - (-1); if you can use a -.

##### Share on other sites
Using 0xFFFFFFFF takes 8 bits per byte, and using 32 bits for granted.
That doesn't depend on any specific architecture.

##### Share on other sites
Quote:
 Original post by tok_juniorUsing 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 on other sites
Quote:
 Original post by alvaroThat 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 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.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628698
• Total Posts
2984275

• 20
• 10
• 13
• 13
• 11