Power of two contained in sum

Im trying to determine if a power of two is part of a sum (represented by a double). Using a bitwise And works up to a certain point, but then I get an overflow. How can I get this to work with larger numbers?

This works: (2^29 + 2^30) And 2^30

Overflow: (2^29 + 2^31) And 2^30
PLavelleAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Corey ScheichDeveloperCommented:
Debug.Print(2 ^ 65 + 2 ^ 29)
works for me
Corey ScheichDeveloperCommented:
What type of variable are you assigning it to
are you using a double
PLavelleAuthor Commented:
This does not work:

(2^65 + 2^29) And 2^65
Python 3 Fundamentals

This course will teach participants about installing and configuring Python, syntax, importing, statements, types, strings, booleans, files, lists, tuples, comprehensions, functions, and classes.

Corey ScheichDeveloperCommented:
What is the context of your code?
Corey ScheichDeveloperCommented:
I am sorry for the math you are doing you can go up to
2^62
2^63 and up are not representable by a Long
Corey ScheichDeveloperCommented:
I was able to use higher numbers like so

        Dim D As Double = 2 ^ 65
        Dim d2 As Double = D + 2 ^ 29 + D
        Debug.Print(d2)
PockyMasterCommented:
Well,uhm, I can tell you from my head 2^29 + 2^ 31 will not contain 2 ^ 30 (hint: try to write it down binary )
Corey ScheichDeveloperCommented:
If I went any higher than 1022 it would return infinity
        Dim D As Double = 2 ^ 1022
        Dim d2 As Double = D + 2 ^ 29 + D
        Debug.Print(d2)
PLavelleAuthor Commented:
I need to find out programatically if the power of two is contained in the sum.
PockyMasterCommented:
If (2^29 + 2^31) would contain 2^30 then also 2^0 + 2^2 would contain 2^1

so 0001 + 0100 would contain 0010?
i don't think so!
PockyMasterCommented:
then try to shift the smallest number you are adding log (smallestnumber) \ log (2) to the right
and do that same amount for your bigger number.

and also do that to your compare number
Corey ScheichDeveloperCommented:
Ok I was misreading your intention
Bitwise Operations can only be performed on integral types so if you can't cast a double value to an integer you can't compare it bitwise.
PLavelleAuthor Commented:
The sum of 2^29 + 2^31 contains 2^29 and 2^31, not 2^30
Corey ScheichDeveloperCommented:
       Dim D As Double = 2 ^ 31
        Dim d3 As Double = 2 ^ 29
        Dim d2 As Double = (D + d3)
        Debug.Print((D + d3) And 2 ^ 31)
        'Returns 2147483648

        Dim D As Double = 2 ^ 31
        Dim d3 As Double = 2 ^ 29
        Dim d2 As Double = (D + d3)
        Debug.Print((D + d3) And 2 ^ 29)
        'Returns 536870912

        Dim D As Double = 2 ^ 31
        Dim d3 As Double = 2 ^ 29
        Dim d2 As Double = (D + d3)
        Debug.Print((D + d3) And 2 ^ 30)
        'Returns 0

False = 0 and true = anything non zero

So it works for me Tested in VS 2005
Corey ScheichDeveloperCommented:
I could use upto  (2^62 + 2^61) AND 2^62
but not
(2^62 + 2^62) AND 2^62
Corey ScheichDeveloperCommented:
How high do you want to go?
Mark_FreeSoftwareCommented:

maybey it sounds stupid, but have you tried to convert it to a (binary) string?
7 would be "111"
8 would be "1000"


than you can compare the strings (and you can make it as big as you want)
Mark_FreeSoftwareCommented:

also you can split the value into more pieces:

yourhugenumber \(16^4) = the right 4 digits removed

yourhugenumber and &HFFFF = only the 4 most right digits
PockyMasterCommented:
The only time a sum contains 2^x is when you sum
 2^(x-1) + 2^(x-1)
or when you sum 2^x with any other value
SanclerCommented:
PockyMaster

>>
The only time a sum contains 2^x is when you sum
 2^(x-1) + 2^(x-1)
or when you sum 2^x with any other value
<<

... unless that "other value" itself contains 2^x, I think ;-)

Corey2

You can get it up to (2^63 + 2^62) AND 2^63 by declaring the variables as UInt64 rather than Double.

PLavelle

I appreciate that the real situation may have been simplified for the purpose of the question but if the situation really is

   (2^a + 2^b) AND 2^c

you don't need to be ANDing huge numbers.  The "a" sets just one bit.  The "b" will not interfere with that setting unless it is equal to "a", in which case it will cancel the original bit and set the next higher bit.  If it does not equal to "a" it will set its own bit.  The "c" is asking whether a particular bit is set.  If that is the bit that was set by "a", and not altered by "b", the answer will be TRUE.  If that is the bit that was set by "b" (other than when "b" is equal to "a"), the answer will be TRUE.  If "a" did equal "b" and "c" = "a" + 1 (or "b" + 1) the answer will be TRUE.  Otherwise, the answer will be FALSE.  So you could ignore the "2^" part of the problem and just check the "a", "b" and "c".

As I say, I appreciate that that may be too simplistic for the real problem (and it's really just making PockyMaster's points in another way), but that's my two-pen'orth.

Roger
IThemaCommented:
Consider
  (2^29 + 2^30) And 2^30
being in the form of
  (2^a + 2^b) And 2^c

I can do 2^1023, which gives me a kilobit number. 2^1024 also gives an overflow. This proves that the part of (2^a + 2^b), where (a <= 1023) and (b <= 1022) will never cause an overflow. Nor will the part of 2^c, where c <= 1023

In other words, (2^29 + 2^30) will not cause an overflow, not will 2^30. Also, (2^63 + 2^62) won't cause an overflow.

So, something else must be causing the overflow. All that's left in the expression is the "And" operator. I can't come to any other conclusion that to say that the And operator cannot handle expressions greater than 4 bytes or 32 bits (In Visual Basic that is; it might be 8 bytes or 64 bits in VB.Net).

So I don't believe you can do this by using the And operator. You either need to find another kind of operator, or you need to split the value into separate 32 bits (or 64 bits for .NET) values, as Mark suggested.

I think you're using this kind of binary comparison to check for bit flags, so you don't know the a, b and c values in advance? Otherwise I believe Roger (Sancler) is right by saying that you can use a simple calculation to see wether True or False should be returned.


Cheers,

Luc Derckx

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
EDDYKTCommented:
instead of using and

can you do

Dim D As Double
D = 2 ^ 29 + 2 ^ 30
While D > 1
D = D / 2 ^ 30
Wend
If D = 1 Then MsgBox "it is"
PockyMasterCommented:
Sancler:

That's why I said any OTHER value :D

But I don't know if we are solving a problem here that doesn't exists, simply because binary calculations seem to complicated

Consider the following:

(2^a + 2^b ) AND 2^c

we can apply log 2 to the equation

so, that leaves us with (a + b ) and c

considering that, can't we just do:

public function NumberInSum(ExpA as Integer, ExpB as Integer, ExpC as Integer) as Boolean

'A equals C
    if ExpA = ExpC and not ExpB = ExpC then
      Return true

'B equals C
elseif ExpB = ExpC and not ExpA = ExpC then
Return true
'ExpA = ExpB and both 1 less than ExpC (causing a shift to the left)
elseif ExpA = (ExpC- 1) ANDALSO ExpB = (ExpC -1) then
return true
else
return false
end if


end function

Now call your function like:


dim bResult as boolean = NumberInSum(29,30,30)
or call like :

NumberInSum ( Log(FirstNumber) / Log(2) , Log(SecondNumber)/Log(2), Log(WhatEverNumberYouWantToCompareTo) /Log(2))



SanclerCommented:
PockyMaster

>>
That's why I said any OTHER value :D
<<

4 + 5 ?

5 is an OTHER value than 4.  ;-)

That's what comes of being a lawyer for real and only a hobbyist programmer.  But, in the specific context of 2^x, I'll grant your point.
 
How about

   If a = b then
      return c = a + 1
   else
      return c = a or c = b
   end if

Roger
PockyMasterCommented:
Well, booleans :D
there are so many ways to write these kind of expressions down, but i tried to keep it simple for  PLavelle.
PLavelleAuthor Commented:
Thanks guys. I've been trying to sort through all this to fully understand what is going on. I'll keep you all updated.
IThemaCommented:
Several explanations and workaround have been given. If PLavelle doesn't respond anymore, I suggest a split points between whoever you feel appropriate.

Cheers
IThemaCommented:
Quote:
>Thanks guys. I've been trying to sort through all this to fully understand what is going on. I'll keep you all updated.

No updates given. I may be a bit harsh, but if PLavelle isn't commenting about those workarounds, nothing but pure logic can say wether those given workarounds are acceptable solutions. I feel that PLavelle already worked it out and forgot about us. I think a couple of us, including me, gave a deeper understanding on why his errors occur in the first place, so why delete this question?

I don't know what others think, but I feel that a points split between Mark_FreeSoftware, Sancler, PockyMaster and myself is appropriate here.

Cheers
PockyMasterCommented:
I agree..
Corey ScheichDeveloperCommented:
I definitely learned alot it would be a shame to delete the question
PLavelleAuthor Commented:
I haven't forgot about this question. I'll award points today. Thanks to everyone for your help.
Mark_FreeSoftwareCommented:

thanx for the points!
PLavelleAuthor Commented:
No, thank you and everyone else for the help and patience.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Visual Basic.NET

From novice to tech pro — start learning today.