Thursday, April 07, 2005

increment problem....

oh! This one is a beauty...
The question is simple: Write a piece of C code that increments the value in an unsigned integer without using + or -. You don't have to be worried about overflows.

6 Comments:

Anonymous Anonymous said...

int increment (int number)
{
int toggle_bit = 0x1;
int temp_var1 = ~(0x0);
int temp_var2 = 0;
do {
if (number & toggle_bit) {
temp_var2 = temp_var1 ^ toggle_bit;
number = number & temp_var2;
} else {
number = number | toggle_bit;
break;
}
} while (toggle_bit << 1)

return number;
}

2:24 PM  
Blogger Manikam said...

Yep....
Thats as simple as it gets.
I must also have clarified that its
an unsigned integer.

You'd have an undefined shift if I were to give the input UINT_MAX. But nevertheless your logic is correct. No worries about the nitty gritty.

Thats the first solution I got too...

int increment(unsigned int n)
{
unsigned int j = 1;
while (j) {
if (n & j) {
n = n & ~j;
} else {
n |= j;
break;
}
j <<= 1;
}
return n;
}


can you think of anything else? You
should see how creative some folks are!
Doesn't matter even if some solutions
are wrong, their approaches too solving
it were pretty striking. Any intresting ways you'd persue to tackle this?
Any other ideas?

3:17 PM  
Blogger Manikam said...

Hey Ashok,
Actually there is no undefined shift
in your code either. Silly me.

Regards,
Manikam.

12:50 PM  
Blogger Manikam said...

I saw this solution posted at the same place where I got the question:

unsigned int increment (unsigned int n)
{
return &((char *)n)[1]
}

Now how about that? Its wrong though. Any ideas why?

2:06 PM  
Anonymous Anonymous said...

This is what I came up with first :)

unsigned int incr (unsigned int i)
{
unsigned int j,k;

j= ~1; k = 0x01;

while ((i & k)) {
i &= j;
k <<= 1; j <<= 1;
}
i |= k;

return i;
}

Leter this...

unsigned int incr (unsigned int i)
{
unsigned int k = 1;
while (i & k) {
i &= ~k;
k = k << 1;
}
i |= k;
return i;
}

-Guhan

7:20 PM  
Anonymous Anonymous said...

Guys ... this one happens to be my first *real* program after 5 years (alright you got it .. I didn't do anything in HCL :)

You call this function with the bit position of the first 0 (for increment) or the first 1 (for decrement) from the LSbit.

char reverseallbitsfromgivenbitposition(char x, int no_of_bits_from_lsb)
{
return (x^(~(~0<< no_of_bits_from_lsb)));
}

Thanks,
GS

7:22 PM  

Post a Comment

<< Home