We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you a podcast all about Citrix Workspace, moving to the cloud, and analytics & intelligence. Episode 2 coming soon!Listen Now

x

Power of two contained in sum

PLavelle
PLavelle asked
on
Medium Priority
209 Views
Last Modified: 2010-04-23
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
Comment
Watch Question

Corey ScheichDeveloper

Commented:
Debug.Print(2 ^ 65 + 2 ^ 29)
works for me
Corey ScheichDeveloper

Commented:
What type of variable are you assigning it to
are you using a double

Author

Commented:
This does not work:

(2^65 + 2^29) And 2^65
Corey ScheichDeveloper

Commented:
What is the context of your code?
Corey ScheichDeveloper

Commented:
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 ScheichDeveloper

Commented:
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)
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 ScheichDeveloper

Commented:
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)

Author

Commented:
I need to find out programatically if the power of two is contained in the sum.
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!
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 ScheichDeveloper

Commented:
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.

Author

Commented:
The sum of 2^29 + 2^31 contains 2^29 and 2^31, not 2^30
Corey ScheichDeveloper

Commented:
       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 ScheichDeveloper

Commented:
I could use upto  (2^62 + 2^61) AND 2^62
but not
(2^62 + 2^62) AND 2^62
Corey ScheichDeveloper

Commented:
How high do you want to go?

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)

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

Not the solution you were looking for? Getting a personalized solution is easy.

Ask the Experts
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
Commented:
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
Commented:
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

Commented:
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"
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))



Commented:
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
Well, booleans :D
there are so many ways to write these kind of expressions down, but i tried to keep it simple for  PLavelle.

Author

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.

Commented:
Several explanations and workaround have been given. If PLavelle doesn't respond anymore, I suggest a split points between whoever you feel appropriate.

Cheers

Commented:
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
I agree..
Corey ScheichDeveloper

Commented:
I definitely learned alot it would be a shame to delete the question

Author

Commented:
I haven't forgot about this question. I'll award points today. Thanks to everyone for your help.

thanx for the points!

Author

Commented:
No, thank you and everyone else for the help and patience.
Access more of Experts Exchange with a free account
Thanks for using Experts Exchange.

Create a free account to continue.

Limited access with a free account allows you to:

  • View three pieces of content (articles, solutions, posts, and videos)
  • Ask the experts questions (counted toward content limit)
  • Customize your dashboard and profile

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.