Author |
Topic: CS: Increment without + or - (Read 4976 times) |
|
greek_genius
Newbie
Posts: 1
|
 |
Solution
« Reply #25 on: Oct 27th, 2004, 10:08am » |
 Quote  Modify
|
The solution is simple:
for 32 bit integers: a+1 = ~a * 0xFFFFFFFF
general solution:
a+1 = ~a * ~0;
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Solution
« Reply #26 on: Oct 28th, 2004, 2:16am » |
Quote Modify
|
on Oct 27th, 2004, 10:08am, greek_genius wrote:
Cool!
From now on, I'll use it in all my programs 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: CS: Increment without + or -
« Reply #27 on: Oct 28th, 2004, 5:41am » |
Quote Modify
|
I wouldn't mind seeing some proof, as it's not that obvious to me..
|
| « Last Edit: Oct 28th, 2004, 5:47am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender:
Posts: 767
|
|
Re: CS: Increment without + or -
« Reply #28 on: Oct 28th, 2004, 8:37am » |
Quote Modify
|
on Oct 28th, 2004, 5:41am, 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.
|
| « Last Edit: Oct 28th, 2004, 11:19am by John_Gaughan » |
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: CS: Increment without + or -
« Reply #29 on: Oct 28th, 2004, 10:10am » |
Quote Modify
|
on Oct 28th, 2004, 5:41am, 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 2n. Therefore:
a + ~a = 2n - 1 [equiv] -1,
~0 = 2n - 1 [equiv] -1,
and
~a * ~0 [equiv] (-a-1) * (-1) = a+1.
This is a real little gem!
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: CS: Increment without + or -
« Reply #30 on: Oct 28th, 2004, 10:21am » |
Quote Modify
|
on Oct 28th, 2004, 10:10am, Barukh wrote:~a * ~0 [equiv] (-a-1) * (-1) = a+1.
|
|
Ah yes, of course.. I should have thought of that myself..
|
|
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