Author |
Topic: CS: Increment without + or - (Read 4974 times) |
|
Jonathan the Red
Guest
|
The problem states that we need not worry about overflow...
Code:
unsigned Increment(unsigned n)
{
for (unsigned nLoop = 1; n & nLoop; nLoop <<= 1)
{
n &= ~nLoop;
}
n |= nLoop;
return n;
}
|
|
Basic algorithm: starting from the least significant bit, turn off set bits until you encounter the first unset bet, which you turn on.
Can anyone think of a more elegant solution?
|
|
 IP Logged |
|
|
|
-D-
Guest
|
 |
Re: CS: Increment without + or -
« Reply #1 on: Jul 29th, 2002, 2:06pm » |
 Quote  Modify
 Remove
|
That's about as simple as it gets. But the only thing that makes it O(n) is that you don't know the size of the register. If you did, you could do it in constant time.
-D-
|
|
IP Logged |
|
|
|
Neil Sedaka
Guest
|
|
Re: CS: Increment without + or -
« Reply #2 on: Aug 1st, 2002, 5:55am » |
Quote Modify
Remove
|
how about log10(pow10(x) * 10)
I guess you have to copy x into a double first.
maybe more fun with log, exp and an "e" const.
|
|
IP Logged |
|
|
|
-D-
Guest
|
|
Re: CS: Increment without + or -
« Reply #3 on: Aug 1st, 2002, 11:09am » |
Quote Modify
Remove
|
I suppose mathematically that would work, it certainly would be an interesting answer if the question were to be posed along the lines of 24 I/II/III.
But in CS terms, Using a floating point unit in a processor is much slower than the integer unit. That is... if you even HAVE a floating point unit to begin with. Secondly, multiplication unless by powers of two will require adder units (carry propogate adders) for summing intermediate results. Technically not using the +/- operations though.
-D-
|
|
IP Logged |
|
|
|
ez76
Newbie
Posts: 1
|
|
Re: CS: Increment without + or -
« Reply #4 on: Aug 4th, 2002, 7:52pm » |
Quote Modify
|
would this work?
unsigned n, nPlusOne;
nPlusOne = (n%2) ? ~(~n & ~1) : (n | 1);
--
Here's the idea:
If n is even, just bitwise OR with 1.
If n is odd, take the two's complement, clear the one bit there (by bitwise AND with ~1), then take the two's complement of that.
examples (assuming 16 bits but would work for larger ints):
n=1000: n | 1 = 1001
n=1001: ~n = 31767; ~n & ~1 = 31766; ~(~n & ~1) = 1002
|
|
IP Logged |
|
|
|
eviljed
Newbie
Posts: 16
|
|
Re: CS: Increment without + or -
« Reply #5 on: Aug 5th, 2002, 8:35am » |
Quote Modify
|
I'm gonna get a little off subject with this one. I will try to put up some C/C++ code for this later... here is the pseudo:
Assume a base 2 number is input (no constraint on this), and assume that there are infinate zeros at the most significant end of the number (given assumption... no overflow), example would be that 8 would be 0000...0100
1) Start at the least significant bit [for this case, the least significat bit is the rightmost, more significat is to the left].
2) If it is 0, change to 1 and halt.
3) If it is 1, move the read head to the left and go to step 2.
I know for a fact that this solution can be done on a turning machine, so it HAS to be doable in C.
|
|
IP Logged |
|
|
|
Neil Sedaka
Guest
|
|
Re: CS: Increment without + or -
« Reply #6 on: Aug 5th, 2002, 8:58am » |
Quote Modify
Remove
|
Umm, using
Quote:
1) Start at the least significant bit [for this case, the least significat bit is the rightmost, more significat is to the left].
2) If it is 0, change to 1 and halt.
3) If it is 1, move the read head to the left and go to step 2.
|
|
with, for example 3, which is 0000...0011 results in
0000...0111, which is 7, a little more than 3+1.
|
|
IP Logged |
|
|
|
Jonathan_the_Red
Junior Member
Gender: 
Posts: 102
|
|
Re: CS: Increment without + or -
« Reply #7 on: Aug 5th, 2002, 10:32am » |
Quote Modify
|
on Aug 4th, 2002, 7:52pm, ez76 wrote:would this work?
unsigned n, nPlusOne;
nPlusOne = (n%2) ? ~(~n & ~1) : (n | 1);
--
Here's the idea:
If n is even, just bitwise OR with 1.
If n is odd, take the two's complement, clear the one bit there (by bitwise AND with ~1), then take the two's complement of that.
examples (assuming 16 bits but would work for larger ints):
n=1000: n | 1 = 1001
n=1001: ~n = 31767; ~n & ~1 = 31766; ~(~n & ~1) = 1002
|
|
Brilliant!!
Only flaw: The unary ~ operator is bitwise NOT (one's complement) so the formula doesn't work... but unary - does. So this:
inline int Increment(int n) { return (n%2) ? -(-n & ~1) : n|1; }
works just fine on any system that uses two's complement for negative numbers.
Beautiful. My hat is off to you.
|
|
IP Logged |
My arcade cabinet
|
|
|
-D-
Guest
|
|
Re: CS: Increment without + or -
« Reply #8 on: Aug 5th, 2002, 1:00pm » |
Quote Modify
Remove
|
One possible flaw: either, the formula makes use of the '-' operator which is not allowed by the constraints of the riddle or if you wanted a twos complement you'd have to take the 1's complement and add 1 which either uses the + sign or becomes a recursive loop on the problem.
-D-
|
|
IP Logged |
|
|
|
<censored>
Guest
|
|
Re: CS: Increment without + or -
« Reply #9 on: Aug 5th, 2002, 6:11pm » |
Quote Modify
Remove
|
Here is another idea:
struct foo {
char a;
char b;
};
#define INC(i) \
((int) &(((struct foo*) (i))->b))
|
|
IP Logged |
|
|
|
<censored>
Guest
|
|
Re: CS: Increment without + or -
« Reply #10 on: Aug 5th, 2002, 6:20pm » |
Quote Modify
Remove
|
Actually could do it without any struct:
#define INC(i)\
((int)&1[(char *)(i)])
|
|
IP Logged |
|
|
|
-D-
Guest
|
|
Re: CS: Increment without + or -
« Reply #11 on: Aug 6th, 2002, 10:40am » |
Quote Modify
Remove
|
Can you explain your idea please <censored>?
|
|
IP Logged |
|
|
|
Paul Hsieh
Guest
|
|
Re: CS: Increment without + or -
« Reply #12 on: Aug 6th, 2002, 9:10pm » |
Quote Modify
Remove
|
<censored>'s idea is hilarious. He is trying to use the internal arithmetic of the language to build a +1 operator. Unfortunately, since he chose structure offsets, he has presented an implementation defined solution. (Structure members need not be packed, if you compiler/platform doesn't like doing that.)
Here's a much easier way:
#define INC(a) ((int)&(((char *)(a))[1]))
That is so la *CHEESE* ...
Its also implementation defined since the size of (char *) is not necessarily the same size as (int) and in particular may be *smaller* in some theoretical twisted environment.
|
|
IP Logged |
|
|
|
Paul Hsieh
Guest
|
|
Re: CS: Increment without + or -
« Reply #13 on: Aug 6th, 2002, 9:11pm » |
Quote Modify
Remove
|
Whoops! Sorry, missed your second post <censored>.
|
|
IP Logged |
|
|
|
-D-
Guest
|
|
Re: CS: Increment without + or -
« Reply #14 on: Aug 6th, 2002, 11:55pm » |
Quote Modify
Remove
|
yeah, I get that. It was more of an excercise in posting your explainations with your idea. It's not very useful to have a solution without some theory or thought process behind it. (refer to williams BIG CAPS POSTS THAT ARE MADE STICKY).
-D-
|
|
IP Logged |
|
|
|
pqlier
Newbie
Posts: 7
|
|
Re: CS: Increment without + or -
« Reply #15 on: Aug 7th, 2002, 10:00am » |
Quote Modify
|
As Paul points out, <censored>'s second solution
#define INC(i)\
((int)&1[(char *)(i)])
and his own, equivalent solution
#define INC(a) ((int)&(((char *)(a))[1]))
both rely on being able to cast the (assumed int) unsigned argument to a char pointer and back, and pointer-size considerations make that non-portable.
But that looks to me like the kind of overflow issue the riddle says to ignore, and on any modern machine (where pointers are at least as big as ints) it should work really well.
#define INC(x) ((unsigned)&((char *)1)[x])
should work too.
Nice job, <censored>.
|
|
IP Logged |
|
|
|
<censored>
Guest
|
|
Re: CS: Increment without + or -
« Reply #16 on: Aug 7th, 2002, 2:11pm » |
Quote Modify
Remove
|
on Aug 6th, 2002, 9:10pm, Paul Hsieh wrote:
Its also implementation defined since the size of (char *) is not necessarily the same size as (int) and in particular may be *smaller* in some theoretical twisted environment. |
|
IMHO any self-respecting compiler will see what's behind this crap and translate it into a single 'inc' instruction, unless sizeof(char) is not 1; now that is architecture dependant.
|
|
IP Logged |
|
|
|
<censored>
Guest
|
|
Re: CS: Increment without + or -
« Reply #17 on: Aug 7th, 2002, 2:19pm » |
Quote Modify
Remove
|
on Aug 6th, 2002, 9:10pm, Paul Hsieh wrote:
Its also implementation defined since the size of (char *) is not necessarily the same size as (int) and in particular may be *smaller* in some theoretical twisted environment. |
|
IMHO any self-respecting compiler will see what's behind this crap and translate it into a single 'inc' instruction, unless sizeof(char) is not 1; now that is architecture dependant.
|
|
IP Logged |
|
|
|
Paul Hsieh
Guest
|
|
Re: CS: Increment without + or -
« Reply #18 on: Aug 7th, 2002, 2:58pm » |
Quote Modify
Remove
|
on Aug 7th, 2002, 2:19pm, <censored> wrote:
IMHO any self-respecting compiler will see what's behind this crap and translate it into a single 'inc' instruction, unless sizeof(char) is not 1; now that is architecture dependant. |
|
No, that's not the only condition. Imagine a compiler where the sizeof(int) = 4, but sizeof (char *) = 2. I.e., a small mode 16 bit compiler, that decides to implement int's as 32 bit. Such a compiler would be legal but the operation:
(char *)a
itself would *significantly truncate* that value. Its a very unusual situation, and I certainly know of no C compiler that does this, but it *is* legal (and ANSI compliant) to make such a compiler.
|
|
IP Logged |
|
|
|
pqlier
Newbie
Posts: 7
|
|
Re: CS: Increment without + or -
« Reply #19 on: Aug 12th, 2002, 12:40am » |
Quote Modify
|
Yeah, but that's an overflow condition.
BTW, <censored>, sizeof (char) is 1 by definition. No worries there.
|
|
IP Logged |
|
|
|
Captain_Segfault
Newbie
Posts: 2
|
|
Re: CS: Increment without + or -
« Reply #20 on: Aug 23rd, 2002, 11:04pm » |
Quote Modify
|
Heh... this problem was a nice exercise in actually USING those bitwise operators that I had never really used much (me=n00b)
What I ended up with:
int addone(int x)
{
int y=1;
for(;(y&x)==y;y=(y<<1)^1);
return x^y;
}
|
|
IP Logged |
|
|
|
Ramanujam
Guest
|
|
Re: CS: Increment without + or -
« Reply #21 on: Sep 20th, 2002, 3:03am » |
Quote Modify
Remove
|
As simple as this !!
inc(int i)
{
int x = i, z= 1;
while(x & 1)
{
z <<= 1;
z|= 1;
x>>= 1;
}
i ^= z;
return i;
}
Can anyone think of more optimal solution ??
|
|
IP Logged |
|
|
|
ubicuteis
Newbie
Gender:
Posts: 2
|
|
Re: CS: Increment without + or -
« Reply #22 on: Dec 13th, 2002, 4:14am » |
Quote Modify
|
[/color]whoa!
this seems to work fine too
n = -(~n);
am i not considering any condition here? the - is unary negation and is legal fer this problem [color=Red]right?
|
|
IP Logged |
|
|
|
ubicuteis
Newbie
Gender:
Posts: 2
|
|
Re: CS: Increment without + or -
« Reply #23 on: Dec 13th, 2002, 4:16am » |
Quote Modify
|
whoa!
this seems to work fine too
n = -(~n);
am i not considering any condition here? the - is unary negation and is legal fer this problem right?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: CS: Increment without + or -
« Reply #24 on: Dec 15th, 2002, 8:30am » |
Quote Modify
|
It will give the right answer, since -n is ~n+1 (to avoid a -0)
And if you want to avoid using -, I think you could use (((~0) >> 12 * (~n)) which should work up to 128 bits integer..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print