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


#include
 
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;
}  
 
/* 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.

No comments:

Post a Comment