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

on
Medium Priority
209 Views
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

## View Solutions Only

Developer

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

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

Commented:
This does not work:

(2^65 + 2^29) And 2^65
Developer

Commented:
What is the context of your code?
Developer

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
Developer

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)

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

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)

Commented:
I need to find out programatically if the power of two is contained in the sum.

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

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

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

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

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
Developer

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

Commented:
How high do you want to go?

Commented:

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

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.

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

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

Roger

Commented:
Well, booleans :D
there are so many ways to write these kind of expressions down, but i tried to keep it simple for  PLavelle.

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

Commented:
I agree..
Developer

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

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

Commented:

thanx for the points!

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.

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