Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Geek Culture / Bitwise math conundrum... can anyone help me?

Author
Message
Jeku
Moderator
21
Years of Service
User Offline
Joined: 4th Jul 2003
Location: Vancouver, British Columbia, Canada
Posted: 22nd Apr 2011 20:55 Edited at: 22nd Apr 2011 20:55
(150 << 7) - (150 << 5)

ans = 14400


The statement above takes 150, multiplies it by 2^7, then subtracts 150 multiplied by 2^5. Not really rocket science.

My question is, how can I do the reverse? I.e. get 14400 back to 150? I thought it was as simple as (14400 >> 7) + (14400 >> 5), which is literally 14400 / 2^7 + 14400 / 2^5, but sadly it doesn't work. I know the solution is there somewhere.

Any takers?


Senior Web Developer - Nokia
ionstream
20
Years of Service
User Offline
Joined: 4th Jul 2004
Location: Overweb
Posted: 22nd Apr 2011 21:21
I'm trying to write it in terms of bit shift operators, but for the time being this is equivalent:

14400/(2^7 - 2^5)

or

14400/96

Jeku
Moderator
21
Years of Service
User Offline
Joined: 4th Jul 2003
Location: Vancouver, British Columbia, Canada
Posted: 22nd Apr 2011 21:45
Thanks! Any idea how to do this completely with bitwise operators? I'm trying to eliminate division operations, as it's about 300% slower with AS3.

Thanks!


Senior Web Developer - Nokia
Diggsey
19
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 22nd Apr 2011 22:02 Edited at: 24th Apr 2011 00:44
Depending on the range of values it needs to work for, try one of these:
x = (y*11) >> 10
x = (y*342) >> 15
x = (y*10923) >> 20
x = (y*11184811) >> 30

(more accurate going down but more likely to overflow)

[b]
n008
18
Years of Service
User Offline
Joined: 18th Apr 2007
Location: Chernarus
Posted: 22nd Apr 2011 23:02
x(2^7) - x(2^5) = x(2^7 - 2^5) = x(96)

inverse

y/96

Put into terms of 2^x

y/(2^5 * 3)

Bitshift:

(y >> 5) / 3

I don't think this can be reversed without division.

"I have faith, that I shall win the race, even though I have no legs, and am tied to a tree." ~Mark75
IanM
Retired Moderator
22
Years of Service
User Offline
Joined: 11th Sep 2002
Location: In my moon base
Posted: 24th Apr 2011 00:09
Here's another approximation:
(y >> 6) - (y >> 8) - (y >> 10) - (y >> 12)

There's no chance of overflow there.

Jeku
Moderator
21
Years of Service
User Offline
Joined: 4th Jul 2003
Location: Vancouver, British Columbia, Canada
Posted: 29th Apr 2011 09:02
Thanks guys


Senior Web Developer - Nokia
That Guy John
15
Years of Service
User Offline
Joined: 30th Apr 2010
Location: United States
Posted: 29th Apr 2011 09:10
Whoa..
This whole thread read like Chinese to me lol
All of your heads are going to explode.

FPSC OneSource [DeskTop App] - Bringing everything together into one.
Neuro Fuzzy
17
Years of Service
User Offline
Joined: 11th Jun 2007
Location:
Posted: 29th Apr 2011 15:26 Edited at: 29th Apr 2011 15:53
Quote: "
(y >> 6) - (y >> 8) - (y >> 10) - (y >> 12)"

woh, nifty!

[edit]
I tried my hand at deriving this, using logarithmic/exponential functions. Thats how you did it right?
[edit2]
ahh yeah, so:
1/96=2^(-6) - 2^(-8) - 2^(-10) - 2^(-12) - 2^(-14) - 2^(-16) - 2^(-18)

And, if you evaluate the limit, you can prove that pattern of subtracting two from the exponent repeats forever, so:

x>>6-x>>8-x>>10-x>>12-x>>14-x>>16-x>>18-...-x>>(8+2*n)

Is there any particular reason you stopped at x>>12?


Tell me if there's a broken link to images in a thread I post, and I'll fix 'em.

Login to post a reply

Server time is: 2025-05-21 20:25:37
Your offset time is: 2025-05-21 20:25:37