-->
Extracting the Powers of 2
-->
-->
Welcome,
Guest
. Please
login
or
register
.
Did you miss your
activation email
?
1 Hour
1 Day
1 Week
1 Month
Forever
Login with username, password and session length
-->
Home
About
Team
Rules
Stats
Status
Sitemap
Chat
Downloads
Forum
News
Our Projects
Major Community Projects
Recent Posts
Unread Posts
Replies
Tools
SourceCoder3
Other Things...
Omnimaga Radio
TI-83 Plus ASM File Unsquisher
Z80 Conversion Tools
IES TI File Editor
Free RAM areas
Comprehensive Getkeyr table
URL Shortener
Online Axe Tilemap Editor
Help
Contact Us
Change Request
Report Issue/Bug
Team
Articles
Members
View the memberlist
Search For Members
Buddies
Login
Register
Omnimaga
»
Forum
»
General Discussion
»
Other Discussions
»
Math and Science
»
Extracting the Powers of 2
« previous
next »
Print
Pages: [
1
]
Go Down
Author
Topic: Extracting the Powers of 2 (Read 68140 times)
0 Members and 1 Guest are viewing this topic.
ztrumpet
The Rarely Active One
CoT Emeritus
LV13
Extreme Addict (Next: 9001)
Posts: 5712
Rating: +364/-4
If you see this, send me a PM. Just for fun.
Extracting the Powers of 2
«
on:
November 13, 2011, 07:32:31 pm »
I am trying to set up a compression system for Midnight that should be really simple to do. The problem is I'm missing the math somewhere.
Here's what I would like to know how to do:
Say I have the number 834 (512+256+64+2). How do I check to see if various powers of two are represented by that number? I.E., I want a mathematical equation that tells me if 2^(any number) is in that number.
I hope that explained it well enough. To clarify, 16 is not a number in 834, but 256 is. Likewise, 16 is a number in 1155 (1024+128+2+1), but 2 is. How can I figure this out with a mathematical equation so I don't have to resort to loops?
Thanks in advance for any help I receive!
Logged
If I'm wrong, please correct me!
Unfinished Projects:
Elmgon
14%
Basic
Movement Demo
Homescreen Game Pack
80%
Basic
Latest Release
Cube Droid Saves the Galaxy
65%
Axe
Demo
Detonate
70%
Axe
Completed Projects:
Exodus
|
Midnight
|
Drifter
|
Axe Snake
|
Jump!
|
Factory Theta
|
Spider
|
Plot Drop
|
Papi Jump
|
Numb3rs
|
Nibbler
|
Boost
|
Duel Tile Map Editor
|
Homescreen Map Editor
|
Key Group Check
|
Oasis
Xeda112358
they/them
Moderator
LV12
Extreme Poster (Next: 5000)
Posts: 4705
Rating: +719/-6
Calc-u-lator, do doo doo do do do.
Re: Extracting the Powers of 2
«
Reply #1 on:
November 13, 2011, 07:36:12 pm »
I think the fastest way would be to use loops unless you can use bit-logic
Is this BASIC?
Logged
My pastebin
|
Pokémon Amber
|
Grammer Programming Language
|
BatLib Library
|
Jade Simulator
|
Zeda's Hex Opcodes
|
FileSyst Library
|
CopyProg
|
TPROG
|
GroupRead
|
Lbl Read/Write
|
Z80 Floating Point Routines
(
z80float on GitHub
)|
Z80 Optimized Routines Repository
Runer112
Moderator
LV11
Super Veteran (Next: 3000)
Posts: 2289
Rating: +639/-31
Re: Extracting the Powers of 2
«
Reply #2 on:
November 13, 2011, 07:41:05 pm »
Here's what I came up with:
iPart(fPart(A/2^B/2)*2)
A is the number to examine, and the formula checks if 2^B is a binary component of A. B=0 would check if 1 is a component, B=1 would check if 2 is a component, B=2 would check if 4 is a component, etc.
Logged
+1/-0 karm for this message
calc84maniac
eZ80 Guru
Coder Of Tomorrow
LV11
Super Veteran (Next: 3000)
Posts: 2912
Rating: +471/-17
Re: Extracting the Powers of 2
«
Reply #3 on:
November 13, 2011, 07:42:04 pm »
To extract bit N of a value, do floor(value/2^N)%2
Logged
+1/-0 karm for this message
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman
ztrumpet
The Rarely Active One
CoT Emeritus
LV13
Extreme Addict (Next: 9001)
Posts: 5712
Rating: +364/-4
If you see this, send me a PM. Just for fun.
Re: Extracting the Powers of 2
«
Reply #4 on:
November 13, 2011, 07:56:44 pm »
Thank you, both Calc84 and Runer. That's incredible. I knew it could be done and you guys did it. Now do you mind explaining how it works?
I don't understand the math behind it, though I understand how to use it. Thank you guys so much!
Quote from: Xeda112358 on November 13, 2011, 07:36:12 pm
Is this BASIC?
Yup.
Logged
If I'm wrong, please correct me!
Unfinished Projects:
Elmgon
14%
Basic
Movement Demo
Homescreen Game Pack
80%
Basic
Latest Release
Cube Droid Saves the Galaxy
65%
Axe
Demo
Detonate
70%
Axe
Completed Projects:
Exodus
|
Midnight
|
Drifter
|
Axe Snake
|
Jump!
|
Factory Theta
|
Spider
|
Plot Drop
|
Papi Jump
|
Numb3rs
|
Nibbler
|
Boost
|
Duel Tile Map Editor
|
Homescreen Map Editor
|
Key Group Check
|
Oasis
Runer112
Moderator
LV11
Super Veteran (Next: 3000)
Posts: 2289
Rating: +639/-31
Re: Extracting the Powers of 2
«
Reply #5 on:
November 13, 2011, 08:23:54 pm »
It's actually a lot simpler than it may sound. It's just a bit trickier in TI-BASIC because TI-BASIC has no binary data types. To use your number as an example, if you break down 854 into binary, you get:
512 64 4
| | |
00000011 01010110
| | |
256 16 2
This says that 854 = 512+256+64+16+4+2. And there's your answer, right in there. Each bit tells you whether 2^([bit position from right]) is a binary component of the number. The trick is isolating the bit that you care about. I do this by rotating the number to points where TI-BASIC is able to mask off the bits I don't want. The functions I have to work with are
iPart()
and
fPart()
, which mask on either side of the decimal point, so I have to shift the bit I want immediately next to the decimal point to be able to use these effectively. First I do this by dividing by 2^([bit position]+1), which effectively shifts the binary number right [bit position]+1 places:
00000000 00000001.10101011 0
|
256
Then I can mask off all the bits on the left with
fPart()
(in this case, just the bit representing 512):
00000000 00000000.10101011 0
|
256
I then multiply by 2 to shift the number back one place to the left:
00000000 00000001.01010110
|
256
And finally, I can use
iPart()
to mask off all the bits on the right:
00000000 00000001.00000000
|
256
So I'm left with the bit representing 256 in the one's place of my number and all other digits gone, thus giving me the boolean value 1, which tells me that 256 is a binary component of 854.
«
Last Edit: November 13, 2011, 08:26:58 pm by Runer112
»
Logged
+2/-0 karm for this message
ztrumpet
The Rarely Active One
CoT Emeritus
LV13
Extreme Addict (Next: 9001)
Posts: 5712
Rating: +364/-4
If you see this, send me a PM. Just for fun.
Re: Extracting the Powers of 2
«
Reply #6 on:
November 13, 2011, 08:30:53 pm »
That is awesome, and it all makes sense now. Thank you for the code and the explanation! It's already implemented; be on the lookout for a screenie within a few minutes.
Logged
If I'm wrong, please correct me!
Unfinished Projects:
Elmgon
14%
Basic
Movement Demo
Homescreen Game Pack
80%
Basic
Latest Release
Cube Droid Saves the Galaxy
65%
Axe
Demo
Detonate
70%
Axe
Completed Projects:
Exodus
|
Midnight
|
Drifter
|
Axe Snake
|
Jump!
|
Factory Theta
|
Spider
|
Plot Drop
|
Papi Jump
|
Numb3rs
|
Nibbler
|
Boost
|
Duel Tile Map Editor
|
Homescreen Map Editor
|
Key Group Check
|
Oasis
Print
Pages: [
1
]
Go Up
« previous
next »
Omnimaga
»
Forum
»
General Discussion
»
Other Discussions
»
Math and Science
»
Extracting the Powers of 2
\n\t\t\t\t\t\t\t\t\t
<' + '/div>\n\t\t\t\t\t\t\t\t\t
%body%<' + '/textarea>
\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t
Max characters: 20000; characters remaining:
...<' + '/span><' + '/span>
\n\t\t\t\t\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t\t\t\t<' + '/div>\n\t\t\t\t\t\t\t\t<' + '/div>', sTemplateSubjectEdit: '
', sTemplateBodyNormal: '%body%', sTemplateSubjectNormal: '
%subject%<' + '/a>', sTemplateTopSubject: 'Topic: %subject% (Read 68140 times)', sErrorBorderStyle: '1px solid red' }); aJumpTo[aJumpTo.length] = new JumpTo({ sContainerId: "display_jump_to", sJumpToTemplate: "
Jump to:<" + "/label> %dropdown_list%", iCurBoardId: 144, iCurBoardChildLevel: 1, sCurBoardName: "Math and Science", sBoardChildLevelIndicator: "==", sBoardPrefix: "=> ", sCatSeparator: "-----------------------------", sCatPrefix: "", sGoButtonLabel: "go" }); aIconLists[aIconLists.length] = new IconList({ sBackReference: "aIconLists[" + aIconLists.length + "]", sIconIdPrefix: "msg_icon_", sScriptUrl: smf_scripturl, bShowModify: true, iBoardId: 144, iTopicId: 13988, sSessionId: "8d9eb9af0ac28d5a92c9743a8d2993b6", sSessionVar: "d1d01ce48d", sLabelIconList: "Message Icon", sBoxBackground: "transparent", sBoxBackgroundHover: "#ffffff", iBoxBorderWidthHover: 1, sBoxBorderColorHover: "#adadad" , sContainerBackground: "#ffffff", sContainerBorder: "1px solid #adadad", sItemBorder: "1px solid #ffffff", sItemBorderHover: "1px dotted gray", sItemBackground: "transparent", sItemBackgroundHover: "#e0e0f0" }); } function tick2() { if (typeof(document.forms.quickModForm) != "undefined") { calcCharLeft2(); setTimeout("tick2()", 1000); } else setTimeout("tick2()", 800); } function message_onkeyup() { if (typeof(document.forms.quickModForm) != "undefined" && typeof(document.forms.quickModForm.message) != "undefined") { document.forms.quickModForm.message.onkeyup = function onkeyup(event) { storeCaret(this); calcCharLeft2(); }; } else setTimeout("message_onkeyup()", 800); } message_onkeyup(); function calcCharLeft2() { var maxLength = 20000; var oldEditor = "", currentEditor = document.forms.quickModForm.message.value; if (!document.getElementById("editorLeft2")) return; if (oldEditor != currentEditor) { oldEditor = currentEditor; if (currentEditor.replace(/\r/, "").length > maxLength) document.forms.quickModForm.message.value = currentEditor.replace(/\r/, "").substring(0, maxLength); currentEditor = document.forms.quickModForm.message.value.replace(/\r/, ""); } setInnerHTML(document.getElementById("editorLeft2"), maxLength - currentEditor.length); } // ]]>-->