**Problem**

Write a program to add one to a given number. You are not allowed to use operators like ‘+’, ‘-’, ‘*’, ‘/’, ‘++’, ‘–’ …etc.

**Examples**

Input: 12 Output: 13

Input: 6 Output: 7

Solution

We can use bitwise operators to achieve this. Following are different methods to achieve same using bitwise operators.

**Method 1 - Flipping the bits**

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.

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

**Method 2 - using 2's complement**

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

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.

Reference - http://how-to-crack-algorithms.blogspot.in/2011/08/add-1-to-given-number-without.html ,

## 0 comments:

## Post a Comment