Examples: Input: 12 Output: 13 Input: 6 Output: 7 We can use bitwise operators to achieve this. Following are different methods to achieve same using bitwise operators. Method 1 To add 1 to a number x (say 0011000111), we need to flip all the bits after the rightmost 0 bit (we get 0011000000). Finally, flip the rightmost 0 bit also (we get 0011001000) and we are done. #includeint addOne(int x) { int m = 1; /* Flip all the set bits until we find a 0 */ while( x & m ) { x = x^m; m <<= 1; } /* flip the rightmost 0 bit */ x = x^m; return x; } /* Driver program to test above functions*/ int main() { printf("%d", addOne(13)); getchar(); return 0; } Method 2 We know that the negative number is represented in 2′s complement form on most of the architectures. We have the following lemma hold for 2′s complement representation of signed numbers. Say, x is numerical value of a number, then ~x = -(x+1) [ ~ is for bitwise complement ] (x + 1) is due to addition of 1 in 2′s complement conversion To get (x + 1) apply negation once again. So, the final expression becomes (-(~x)). int addOne(int x) { return (-(~x)); } /* Driver program to test above functions*/ int main() { printf("%d", addOne(13)); getchar(); return 0; } Example, assume the machine word length is one *nibble* for simplicity. And x = 2 (0010), ~x = ~2 = 1101 (13 numerical) -~x = -1101 Interpreting bits 1101 in 2′s complement form yields numerical value as -(2^4 – 13) = -3. Applying ‘-’ on the result leaves 3. Same analogy holds for decrement. Note that this method works only if the numbers are stored in 2′s complement form.
Wednesday, August 31, 2011
Add 1 to a given number without arithmetic operators
Write a program to add one to a given number. You are not allowed to use operators like ‘+’, ‘-’, ‘*’, ‘/’, ‘++’, ‘–’ …etc.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment