Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 193
  • Last Modified:

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
0
PLavelle
Asked:
PLavelle
  • 11
  • 7
  • 6
  • +4
4 Solutions
 
Corey ScheichDeveloperCommented:
Debug.Print(2 ^ 65 + 2 ^ 29)
works for me
0
 
Corey ScheichDeveloperCommented:
What type of variable are you assigning it to
are you using a double
0
 
PLavelleAuthor Commented:
This does not work:

(2^65 + 2^29) And 2^65
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
Corey ScheichDeveloperCommented:
What is the context of your code?
0
 
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
0
 
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)
0
 
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 )
0
 
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)
0
 
PLavelleAuthor Commented:
I need to find out programatically if the power of two is contained in the sum.
0
 
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!
0
 
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
0
 
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.
0
 
PLavelleAuthor Commented:
The sum of 2^29 + 2^31 contains 2^29 and 2^31, not 2^30
0
 
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
0
 
Corey ScheichDeveloperCommented:
I could use upto  (2^62 + 2^61) AND 2^62
but not
(2^62 + 2^62) AND 2^62
0
 
Corey ScheichDeveloperCommented:
How high do you want to go?
0
 
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)
0
 
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
0
 
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
0
 
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
0
 
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
0
 
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"
0
 
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))



0
 
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
0
 
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.
0
 
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.
0
 
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
0
 
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
0
 
PockyMasterCommented:
I agree..
0
 
Corey ScheichDeveloperCommented:
I definitely learned alot it would be a shame to delete the question
0
 
PLavelleAuthor Commented:
I haven't forgot about this question. I'll award points today. Thanks to everyone for your help.
0
 
Mark_FreeSoftwareCommented:

thanx for the points!
0
 
PLavelleAuthor Commented:
No, thank you and everyone else for the help and patience.
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 11
  • 7
  • 6
  • +4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now