PLavelle

asked on

# 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

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

Overflow: (2^29 + 2^31) And 2^30

What type of variable are you assigning it to

are you using a double

are you using a double

ASKER

This does not work:

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

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

What is the context of your code?

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

2^62

2^63 and up are not representable by a Long

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)

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 )

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)

Dim D As Double = 2 ^ 1022

Dim d2 As Double = D + 2 ^ 29 + D

Debug.Print(d2)

ASKER

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!

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

and do that same amount for your bigger number.

and also do that to your compare number

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.

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.

ASKER

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

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

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

I could use upto (2^62 + 2^61) AND 2^62

but not

(2^62 + 2^62) AND 2^62

but not

(2^62 + 2^62) AND 2^62

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)

SOLUTION

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds.

**No credit card required.**
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

2^(x-1) + 2^(x-1)

or when you sum 2^x with any other value

SOLUTION

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds.

**No credit card required.**ASKER CERTIFIED SOLUTION

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds.

**No credit card required.**
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"

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"

SOLUTION

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds.

**No credit card required.**
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

>>

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.

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

ASKER

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

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

Cheers

Cheers

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

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

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

ASKER

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

thanx for the points!

ASKER

No, thank you and everyone else for the help and patience.

works for me