﻿ Extracting the Powers of 2
19 June, 2013, 22:16:39
 OmnomIRC You must Register, be logged in and have at least 40 posts to use this shout-box! If it still doesn't show up afterward, it might be that OmnomIRC is disabled for your group or under maintenance.Note: You can also use an IRC client like mIRC, X-Chat or Mibbit to connect to an EFnet server and #omnimaga.

 Pages: [1]   Go Down
 Author Topic: Extracting the Powers of 2 -  (Read 532 times) 0 Members and 1 Guest are viewing this topic.
ztrumpet
The Rarely Active One

Offline

Gender:
Last Login: 11 June, 2013, 05:10:51
Date Registered: 08 November, 2009, 21:10:12
Location: Michigan
Posts: 5688

Topic starter
Total Post Ratings: +360

 « on: 14 November, 2011, 02:32:31 » 0

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?

 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
Xombie. I am it.
Coder Of Tomorrow
LV12 Extreme Poster (Next: 5000)

Offline

Date Registered: 31 October, 2010, 08:46:36
Location: Land of Little Cubes and Tea, NY
Posts: 3783

Total Post Ratings: +614

 « Reply #1 on: 14 November, 2011, 02:36:12 » 0

I think the fastest way would be to use loops unless you can use bit-logic Is this BASIC?
 Logged

Latest update (possibly incomplete)
My pastebin
Spoiler for FileSyst:
FileSyst is an application that provides a folder and filesystem for the TI-83+/84+ calculators. It is designed to be easy to access and use in BASIC, and it can be used to access game files and save data, or to create a command prompt, among other things:

Spoiler for Graphiti:
This is a graph explorer for graph theory. It will require lots of work to finish. Currently you can:
Add edges (direction not shown, but they are directed)
Arrange vertices in a circle (in the future, you will be able to define levels of rings and the number of nodes in each)
Create complete graphs quickly

Plans:
Deleting edges
Multiple graphs support
Arrows for directed graphs
Planarity testing
Matrix operations
Weighted edges
Chromatic polynomials
Chromatic numbers

Spoiler for Stats:

Samocal             [o---------]
Virtual Processor   [o---------]
EnG                 [oo--------]
Grammer             [ooo-------]
AsmComp             [ooo-------]
Partex              [oooo------]
BatLib              [oooooooo--]
Grammer82           [----------]
Grammer68000        [----------]

Pseudonyms:  Zeda, Xeda, Thunderbolt
Languages:   English, français
Programming: z80 Assmebly
Grammer
TI-BASIC (83/84/+/SE, 89/89t/92)
Known For:   -Creator of the Grammer programming language
(Winning program of zContest2011)
-BatLib- One of the most feature packed libraries for BASIC programmers available
with over 100 functions and a simple programming language
-Learning to program z80 in hexadecimal before using an assembler (no computer was
available!)
╔═╦╗░╠═╬╣▒║ ║║▓╚═╩╝█

Runer112
LV10 31337 u53r (Next: 2000)

Offline

Gender:
Date Registered: 02 July, 2009, 06:38:05
Posts: 1696

Total Post Ratings: +499

 « Reply #2 on: 14 November, 2011, 02:41:05 » +1

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
calc84maniac
Epic z80 roflpwner
Coder Of Tomorrow
LV11 Super Veteran (Next: 3000)

Offline

Gender:
Date Registered: 28 August, 2008, 05:09:05
Location: Right behind you.
Posts: 2738

Total Post Ratings: +376

 « Reply #3 on: 14 November, 2011, 02:42:04 » +1

To extract bit N of a value, do floor(value/2^N)%2
 Logged

"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman
ztrumpet
The Rarely Active One

Offline

Gender:
Last Login: 11 June, 2013, 05:10:51
Date Registered: 08 November, 2009, 21:10:12
Location: Michigan
Posts: 5688

Topic starter
Total Post Ratings: +360

 « Reply #4 on: 14 November, 2011, 02:56:44 » 0

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!

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
LV10 31337 u53r (Next: 2000)

Offline

Gender:
Date Registered: 02 July, 2009, 06:38:05
Posts: 1696

Total Post Ratings: +499

 « Reply #5 on: 14 November, 2011, 03:23:54 » +2

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: 14 November, 2011, 03:26:58 by Runer112 » Logged
ztrumpet
The Rarely Active One

Offline

Gender:
Last Login: 11 June, 2013, 05:10:51
Date Registered: 08 November, 2009, 21:10:12
Location: Michigan
Posts: 5688

Topic starter
Total Post Ratings: +360

 « Reply #6 on: 14 November, 2011, 03:30:53 » 0

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
 Pages: [1]   Go Up