How to do adding/subtracting with bitwise operators
Author
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?
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;}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.
A coworker came up with this.
Thanks for the interesting problem.
How long did you have to compleate this?
Armand
int add1(int x){ return ~x * 0xFFFFFFFF;}Thanks for the interesting problem.
How long did you have to compleate this?
Armand
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.
Alvaro's was readable. The recursion makes it quite easy to read, easier, in fact, than an iterative solution.
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. :)
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. :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
