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

[Jonathan Turkanis]

"Method Man" <a@b.c> wrote in message news:Bt************@read1.cgocable.net...

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

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

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Dave Vandervies]

In article <Bt************@read1.cgocable.net>, Method Man <a@b.c> wrote:

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 dj******@csclub.uwaterloo.ca 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]

"Alf P. Steinbach" <al***@start.no> wrote in message
news:41****************@news.individual.net...

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

[Method Man]

"Alf P. Steinbach" <al***@start.no> wrote in message
news:41****************@news.individual.net...

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

[Ron Natalie]

"Method Man" <a@b.c> wrote in message news:Bt************@read1.cgocable.net...

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)

[David Fisher]

Jonathan wrote:

Method Man wrote:

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

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

"Method Man" <a@b.c> wrote in message news:<Bt************@read1.cgocable.net>...

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]

"Justin Dubs" <jt****@eos.ncsu.edu> wrote in message
news:2e**************************@posting.google.c om...

"Method Man" <a@b.c> wrote in message

news:<Bt************@read1.cgocable.net>...

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

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]

"Method Man" <a@b.c> wrote:

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::plus<unsigned>()(x, 1);
}

[Jonathan Turkanis]

"Method Man" <a@b.c> wrote in message news:Bt************@read1.cgocable.net...

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]

"Old Wolf" <ol*****@inspire.net.nz> skrev i en meddelelse
news:84**************************@posting.google.c om...

"Method Man" <a@b.c> wrote:

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::plus<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]

"Method Man" <a@b.c> wrote in message news:Bt************@read1.cgocable.net...

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]

da*********@aol.com (DaKoadMunky) wrote in message news:<20***************************@mb-m16.aol.com>...

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.

[Sharad Kala]

"Peter Koch Larsen" <pk*****@mailme.dk> wrote in message

This is by far the most elegant and efficient solution.

But the least thought provoking too...

[Gernot Frisch]

"Old Wolf" <ol*****@inspire.net.nz> schrieb im Newsbeitrag
news:84**************************@posting.google.c om...

"Method Man" <a@b.c> wrote:

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::plus<unsigned>()(x, 1);
}

Excellent! This one is the cleanest and best.

[Peter Koch Larsen]

"Sharad Kala" <no******************@yahoo.com> skrev i en meddelelse
news:2r*************@uni-berlin.de...

"Peter Koch Larsen" <pk*****@mailme.dk> wrote in message

This is by far the most elegant and efficient solution.

But the least thought provoking too...

Not at all. It is the solution that understand how to take advantage of C++.
Most of the other solutions are simply C bit-fiddling, while some use C++
but in a most inefficient way (Jonathans std::vector).

/Peter

[Dietmar Kuehl]

DaKoadMunky wrote:

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::plus<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.
--
<mailto:di***********@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting

[Alf P. Steinbach]

* Dietmar Kuehl:

* DaKoadMunky:

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

Probably because the question was C/C++ program, not C++ program (but I may be
wrong, just judging by my own response).

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Jyrki Alakuijala]

#include <math.h>

void addOne(unsigned int &a) {
a = log(4 * exp(a));
}

Please, do remember to have sufficient exponent accuracy in
your floating point representation to cover the whole unsigned
int range.

[Jyrki Alakuijala]

Adding without loops:

void addOne(unsigned int &val) {
unsigned int x = ~val;
#define A(y) x &= (x & y) ? y : ~y;
A(0x0000ffff)
A(0x00ff00ff)
A(0x0f0f0f0f)
A(0x33333333)
A(0x55555555)
#undef A
val &= x * ~0;
val |= x;
}

[Matt Hurd]

"Gernot Frisch" <[e-mail]> wrote in message news:<2r*************@uni-berlin.de>...

"Old Wolf" <ol*****@inspire.net.nz> schrieb im Newsbeitrag
news:84**************************@posting.google.c om...

"Method Man" <a@b.c> wrote:

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::plus<unsigned>()(x, 1);
}

Excellent! This one is the cleanest and best.

Given he didn't say which unsigned integer (overly pedantic hat) you
could go for some extra credit ;-)

#include <functional>

template< class T >
T add_one(T x)
{
return std::plus<T>()(x, 1);
}

matt.
www.hurd.com.au

[Gernot Frisch]

"Jyrki Alakuijala" <Jy**************@find.me.via.google> schrieb im
Newsbeitrag news:ci**********@phys-news1.kolumbus.fi...

Adding without loops:

void addOne(unsigned int &val) {
unsigned int x = ~val;
#define A(y) x &= (x & y) ? y : ~y;
A(0x0000ffff)
A(0x00ff00ff)
A(0x0f0f0f0f)
A(0x33333333)
A(0x55555555)
#undef A
val &= x * ~0;
val |= x;
}

This one wins the obsfruscation contest...