Extracting the Powers of 2

[ztrumpet]

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!

[Xeda112358]

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

[Runer112]

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.

[calc84maniac]

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

[ztrumpet]

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.

[Runer112]

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.

[ztrumpet]

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.