wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> CS: Increment without + or -
        
(Message started by: Jonathan the Red on Jul 29^th, 2002, 11:50am)

Title: CS: Increment without + or -
Post by Jonathan the Red on Jul 29^th, 2002, 11:50am

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?

Title: Re: CS: Increment without + or -
Post by -D- on Jul 29^th, 2002, 2:06pm

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-

Title: Re: CS: Increment without + or -
Post by Neil Sedaka on Aug 1^st, 2002, 5:55am

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.

Title: Re: CS: Increment without + or -
Post by -D- on Aug 1^st, 2002, 11:09am

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-

Title: Re: CS: Increment without + or -
Post by ez76 on Aug 4^th, 2002, 7:52pm

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

Title: Re: CS: Increment without + or -
Post by eviljed on Aug 5^th, 2002, 8:35am

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.

Title: Re: CS: Increment without + or -
Post by Neil Sedaka on Aug 5^th, 2002, 8:58am

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.

Title: Re: CS: Increment without + or -
Post by Jonathan_the_Red on Aug 5^th, 2002, 10:32am

on 08/04/02 at 19:52:03, ez76 wrote:

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.

Title: Re: CS: Increment without + or -
Post by -D- on Aug 5^th, 2002, 1:00pm

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-

Title: Re: CS: Increment without + or -
Post by <censored> on Aug 5^th, 2002, 6:11pm

Here is another idea:
struct foo {
char a;
char b;
};

#define INC(i) \
((int) &(((struct foo*) (i))->b))

Title: Re: CS: Increment without + or -
Post by <censored> on Aug 5^th, 2002, 6:20pm

Actually could do it without any struct:
#define INC(i)\
((int)&1[(char *)(i)])

Title: Re: CS: Increment without + or -
Post by -D- on Aug 6^th, 2002, 10:40am

Can you explain your idea please <censored>?

Title: Re: CS: Increment without + or -
Post by Paul Hsieh on Aug 6^th, 2002, 9:10pm

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

Title: Re: CS: Increment without + or -
Post by Paul Hsieh on Aug 6^th, 2002, 9:11pm

Whoops! Sorry, missed your second post <censored>.

Title: Re: CS: Increment without + or -
Post by -D- on Aug 6^th, 2002, 11:55pm

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-

Title: Re: CS: Increment without + or -
Post by pqlier on Aug 7^th, 2002, 10:00am

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

Title: Re: CS: Increment without + or -
Post by <censored> on Aug 7^th, 2002, 2:11pm

on 08/06/02 at 21:10:20, 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.

Title: Re: CS: Increment without + or -
Post by <censored> on Aug 7^th, 2002, 2:19pm

on 08/06/02 at 21:10:20, 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.

Title: Re: CS: Increment without + or -
Post by Paul Hsieh on Aug 7^th, 2002, 2:58pm

on 08/07/02 at 14:19:01, <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.

Title: Re: CS: Increment without + or -
Post by pqlier on Aug 12^th, 2002, 12:40am

Yeah, but that's an overflow condition.

BTW, <censored>, sizeof (char) is 1 by definition. No worries there.

Title: Re: CS: Increment without + or -
Post by Captain_Segfault on Aug 23^rd, 2002, 11:04pm

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

Title: Re: CS: Increment without + or -
Post by Ramanujam on Sep 20^th, 2002, 3:03am

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

Title: Re: CS: Increment without + or -
Post by ubicuteis on Dec 13^th, 2002, 4:14am

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?

Title: Re: CS: Increment without + or -
Post by ubicuteis on Dec 13^th, 2002, 4:16am

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?

Title: Re: CS: Increment without + or -
Post by towr on Dec 15^th, 2002, 8:30am

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) >> 128) * (~n)) which should work up to 128 bits integer..

Title: Solution
Post by greek_genius on Oct 27^th, 2004, 10:08am

The solution is simple:

for 32 bit integers: a+1 = ~a * 0xFFFFFFFF

general solution:

a+1 = ~a * ~0;

Title: Re: Solution
Post by Grimbal on Oct 28^th, 2004, 2:16am

on 10/27/04 at 10:08:44, greek_genius wrote:

a+1 = ~a * ~0;

Cool!

From now on, I'll use it in all my programs ;D

Title: Re: CS: Increment without + or -
Post by towr on Oct 28^th, 2004, 5:41am

I wouldn't mind seeing some proof, as it's not that obvious to me..

Title: Re: CS: Increment without + or -
Post by John_Gaughan on Oct 28^th, 2004, 8:37am

on 10/28/04 at 05:41:32, towr wrote:

I wouldn't mind seeing some proof, as it's not that obvious to me..

This solution looks like multiplying two one's complement numbers, and it is, but try looking at it differently. Think of it as repeated addition of a one's complement number, truncating the overflowed MSBs.

Given a number 1001, adding one gives 1010.
~1001 = 0110
Repeated addition gives
1001 + 1 = 0110 + 1100 + 1000 + 0000 = 1 1010

if x is the number:
~x * ~0 = [smiley=sum.gif] n=0 -> bitlength(x) (~x << n)

The first digit is simply the one's complement and is not added to anything else, so it is simply the inverse of the original. The next digit takes that digit's complement, adds one, and carries from the first digit... kinda like a full adder, huh?

Do this enough times and you turn a typical serial multiplier circuit and turn it into a multi-bit adder because of that one's complement.

Title: Re: CS: Increment without + or -
Post by Barukh on Oct 28^th, 2004, 10:10am

on 10/28/04 at 05:41:32, towr wrote:

I wouldn't mind seeing some proof, as it's not that obvious to me..

Let me also try...

I looked at this as ordinary multiplication. The only thing to observe is that on the n-bit machine, arithmetic operations are performed modulo 2ⁿ. Therefore:

a + ~a = 2ⁿ - 1 [equiv] -1,
~0 = 2ⁿ - 1 [equiv] -1,

and

~a * ~0 [equiv] (-a-1) * (-1) = a+1.

This is a real little gem!

Title: Re: CS: Increment without + or -
Post by towr on Oct 28^th, 2004, 10:21am

on 10/28/04 at 10:10:34, Barukh wrote:

~a * ~0 [equiv] (-a-1) * (-1) = a+1.

Ah yes, of course.. I should have thought of that myself..