Puzzle: Add One Without Using + OR -

[Method Man]

Q:
Write a C/C++ program that takes an unsigned integer and adds 1 to it
without using the plus or minus signs. Don't worry about overflow issues. It
is cheating to use assembly commands, or to write a preprocessor that uses
ASCII codes to insert the plus or minus sign. There are many solutions, some
more elegant than others.














Here's the solution I came up with. I'm wondering if there's a solution that
is more elegant or efficient.


void addOne(unsigned int &i) {
int j = 1;

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

while !(j & 1) {
i <<= 1;
j >>= 1;
}
}

 

[Ron Natalie]

Q:
void addOne(unsigned int &i) {
int j = 1;

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

while !(j & 1) {
i <<= 1;
j >>= 1;

unsigned int bit = 1;
// While we are looking at bits that have value 1, we clear the
// value and shift left to carry the one to the next place.
//
while(i & bit) {
i &= ~bit; // add one
bit <<= 1; // carry;
}
//
// When we get here, the bit is zero, so we can add just by oring 1 to this position.
i |= bit; // don't need to carry (was zero)

 

[Alf P. Steinbach]

* Method Man:

Q:
Write a C/C++ program that takes an unsigned integer and adds 1 to it
without using the plus or minus signs. Don't worry about overflow issues. It
is cheating to use assembly commands, or to write a preprocessor that uses
ASCII codes to insert the plus or minus sign. There are many solutions, some
more elegant than others.

Here's the solution I came up with. I'm wondering if there's a solution that
is more elegant or efficient.


void addOne(unsigned int &i) {
int j = 1;

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

while !(j & 1) {
i <<= 1;
j >>= 1;
}
}

Good attempt, but regarding style, preferentially use a function rather than
an in/out argument, and regarding C++, the above shouldn't compile: always
post code that compiles (except when the point is that it doesn't compile).

At the risk of doing your HOMEWORK for you:

unsigned next( unsigned x )
{
if( x == ~0 ) { return 0; }
unsigned flipmask = ~0;
while( (x | flipmask) == ~0 )
{
flipmask <<= 1;
}
return x ^ ~flipmask;
}

State the assumptions that this solution relies on.

 

[Jonathan Turkanis]

Q:
Write a C/C++ program that takes an unsigned integer and adds 1 to it
without using the plus or minus signs. Don't worry about overflow issues. It
is cheating to use assembly commands, or to write a preprocessor that uses
ASCII codes to insert the plus or minus sign. There are many solutions, some
more elegant than others.

Here's a funny one.

#include <vector>

void addOne(unsigned int &i) {
std::vector<char> v(i);
v.push_back('q');
i = (unsigned int) v.size();
}

Jonathan

 

[Method Man]

* Method Man:

Good attempt, but regarding style, preferentially use a function rather than
an in/out argument, and regarding C++, the above shouldn't compile: always
post code that compiles (except when the point is that it doesn't compile).

Oops. I just posted code that I wrote on a peice of paper without compiling
it.

At the risk of doing your HOMEWORK for you:

Not homework, just an interesting puzzle I came across on the web.

unsigned next( unsigned x )
{
if( x == ~0 ) { return 0; }
unsigned flipmask = ~0;
while( (x | flipmask) == ~0 )
{
flipmask <<= 1;
}
return x ^ ~flipmask;
}

State the assumptions that this solution relies on.

That's clever. I didn't think of using ~0.
I beleive the assumption is that when an overflow occurs, the value should
roll back to 0.

 

[Dave Vandervies]

Q:
Write a C/C++ program that takes an unsigned integer and adds 1 to it
without using the plus or minus signs. Don't worry about overflow issues.

(It's actually easier to treat unsigned overflow the same way the ++
operator does it, by wrapping around, than by treating it as a "Don't
worry about this" special case.)

Here's the solution I came up with. I'm wondering if there's a solution that
is more elegant or efficient.


void addOne(unsigned int &i) {
int j = 1;

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

while !(j & 1) {
i <<= 1;
j >>= 1;
}
}

I have a solution that only uses one loop:
--------
/*Exercises for the reader:
-Find and correct the deliberately introduced bug
(that is, don't hand this in as your homework without thinking about it
first, or you'll fail)
-Explain what effect the bug has and why
-Reconstruct my comments explaining what the code is doing and why
*/
unsigned long inc(unsigned long i)
{
unsigned long j=1;
while(j)
{
i^=j;
if(!(i&j))
return i;
j<<=1;
}
return i;
}
--------


dave

--
Dave Vandervies (e-mail address removed)

Just like C, vi is not incompetent-friendly.

I disagree. I get on just fine with both C and vi.
--Dan Pop and Richard Heathfield in comp.lang.c

 

[Method Man]

* Method Man:

Good attempt, but regarding style, preferentially use a function rather than
an in/out argument, and regarding C++, the above shouldn't compile: always
post code that compiles (except when the point is that it doesn't compile).

Oops, I hand wrote my code without compiling.

At the risk of doing your HOMEWORK for you:

Not homework, just an interesting puzzle I found.

unsigned next( unsigned x )
{
if( x == ~0 ) { return 0; }
unsigned flipmask = ~0;
while( (x | flipmask) == ~0 )
{
flipmask <<= 1;
}
return x ^ ~flipmask;
}

State the assumptions that this solution relies on.

That's clever. I didn't think of using ~0.
I beleive the assumption is that on overflow, the value will roll back to 0.

 

[David Fisher]

....

Here's a funny one.

#include <vector>

void addOne(unsigned int &i) {
std::vector<char> v(i);
v.push_back('q');
i = (unsigned int) v.size();
}

Very cute !

How about:

#include <unistd.h>
#include <ctime>

unsigned int addOne(unsigned int i)
{
time_t t = (time_t) i;
stime(&t); // set the current time
sleep(1);
return time(0);
}

There may be unfortunate side effects, though ... and it may not be all that
portable ... and it might not work sometimes ... but apart from that ...

David Fisher
Sydney, Australia

 

[DaKoadMunky]

I am curious to know if the gurus think that this kind of question has any use
beyond impressing girls at cocktail parties.

Would you actually deny somebody a C++ job if they couldn't answer this
question?

I ask because I consider myself to be an effective C++ developer but I
generally don't do well with this type of question or at the very least I feel
I have to put more thought into it than I think should be necessary.

 

[Justin Dubs]

Q:
Write a C/C++ program that takes an unsigned integer and adds 1 to it
without using the plus or minus signs. Don't worry about overflow issues. It
is cheating to use assembly commands, or to write a preprocessor that uses
ASCII codes to insert the plus or minus sign. There are many solutions, some
more elegant than others.

Here's mine:

unsigned int increment(unsigned int number) {
unsigned int mask = 1;

for (; mask & number; mask <<= 1)
number ^= mask;

return number | mask;
}

From the least-significant-bit up, turn 1's into 0's until you hit a
zero. Turn that one into a one.

Jusitn Dubs

 

[Method Man]

"Method Man" <[email protected]> wrote in message

Here's mine:

unsigned int increment(unsigned int number) {
unsigned int mask = 1;

for (; mask & number; mask <<= 1)
number ^= mask;

return number | mask;
}

From the least-significant-bit up, turn 1's into 0's until you hit a
zero. Turn that one into a one.

Jusitn Dubs

As an aside, is the | operator more efficient than the ^ operator? I would
imagine it is best to try using primitive gates whenever possible. (Then
again, internally everything could just be NAND gates).

 

[Old Wolf]

Q:
Write a C/C++ program that takes an unsigned integer and adds 1 to it
without using the plus or minus signs.

#include <functional>

unsigned addOne(unsigned x)
{
return std:lus<unsigned>()(x, 1);
}

 

[Jonathan Turkanis]

Q:
Write a C/C++ program that takes an unsigned integer and adds 1 to it
without using the plus or minus signs. Don't worry about overflow issues. It
is cheating to use assembly commands, or to write a preprocessor that uses
ASCII codes to insert the plus or minus sign. There are many solutions, some
more elegant than others.

Here's another:

unsigned addOne(unsigned i)
{
switch(i) {
case 0: return 1;
case 1: return 2;
case 2: return 3;
case 3: return 4;
case 4: return 5;
case 5: return 6;
case 6: return 7;
case 7: return 8;
...
...

}
}

Jonathan

 

[Peter Koch Larsen]

#include <functional>

unsigned addOne(unsigned x)
{
return std:lus<unsigned>()(x, 1);
}

This is by far the most elegant and efficient solution.

/Peter

 

[Justin Dubs]

Here's a fun recursive one:

unsigned int increment(unsigned int number) {
if (number & 1)
return inc1(number >> 1) << 1;

return number | 1;
}

And here's a truly evil one that only works if your chars are one-byte.

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

Enjoy...

Justin Dubs

 

[Jonathan Turkanis]

Q:
Write a C/C++ program that takes an unsigned integer and adds 1 to it
without using the plus or minus signs. Don't worry about overflow issues. It
is cheating to use assembly commands, or to write a preprocessor that uses
ASCII codes to insert the plus or minus sign. There are many solutions, some
more elegant than others.

Okay, just one more:

#include <iostream>

unsigned addOne(unsigned i)
{
std::cout << "Please enter the result of adding 1 to " << i << "\n";
unsigned result;
std::cin >> result;
return result;
}

Jonathan

 

[Kid]

I am curious to know if the gurus think that this kind of question has any use
beyond impressing girls at cocktail parties.

Would you actually deny somebody a C++ job if they couldn't answer this
question?

I ask because I consider myself to be an effective C++ developer but I
generally don't do well with this type of question or at the very least I feel
I have to put more thought into it than I think should be necessary.

Not modern C++ but definately C. Incrementing without a '+' token
isn't practical but is a decent test of one's bit twaddling skills.

 

[Dietmar Kuehl]

I am curious to know if the gurus think that this kind of question has any use
beyond impressing girls at cocktail parties.

I doubt that you can impress girls at cocktail parties with this kind
of
stuff. The use of this stuff is not really practical. It is more about
flexibility.

Would you actually deny somebody a C++ job if they couldn't answer this
question?

I wouldn't ask for such a thing but if it became apparent that this
question could not be answered, I would probably indeed deny a C++
job. After all, the simple solution 'std:lus<int>()(n, 1)' should be
obvious to anybody knowing the standard C++ library... Funny that I saw
it mentioned only once before in this thread: this was first solution I
had in mind.

I ask because I consider myself to be an effective C++ developer but I
generally don't do well with this type of question or at the very least I feel
I have to put more thought into it than I think should be necessary.

Well, I could come up with a solution using bit logic but I would also
have to put more thought into it than I would like to spent. Thus, I
tend to come up with solutions which just take advantage of library
facilities.

 

[Sharad Kala]

This is by far the most elegant and efficient solution.

But the least thought provoking too...

 

[Gernot Frisch]

#include <functional>

unsigned addOne(unsigned x)
{
return std:lus<unsigned>()(x, 1);
}

Excellent! This one is the cleanest and best.