Permutations, factorials and bitwise comparison

Posted on 2006-05-29
Last Modified: 2010-04-30

I'm coding a function in order to test every calculations possible between x numbers.

I found over the net a pretty good algorithm which helped me a lot but it has its
limits... The prb with this code is that at some point it manage a bitwise comparison
(with AND operator) between 2 values, but when it reach very high numbers, it fails with
an overflow error due to the AND bitwise comparison which is limited to long values (32 bits)
in VB.

A simple example of the prb can be viewed just by typing following statement in the
debug/immediate window:  ?  2^32 AND 2^32

So 1st question : how can i use double variables (64 bits) with the AND-bitwise-comparison ?

Or 2nd question : any better idea for achieving my goal ?

As far as i know, bitwise comparison is fast. However, with my current code, checking all possible
calculations for eg 20 amounts gives 1.048.555 possible calculations (((2 ^ (20)) - 1) - 20).
And computing all these calculations already takes a little more than 30 minutes on my PC.

I found an interesting thread on the subject in this site here :

...but could not find out how to apply this for my prb :(

I also found a free dll (Binary Function Library 2.00) which seems very interesting, but as i'm not an
expert with bits, i couldn't sort this out myself either. The library can be found here :

Thanks for the help,

Question by:FioraH
    LVL 13

    Expert Comment


    to use that library, put it in the same folder as your app (or the system32 dir)

    you are interested in this declaration:

    Declare Sub AndQ Lib "BinaryLib" (ByRef ArPattern As Any, ByRef Amount As Any, Optional ByVal ArPatternSize As Long = 8)

    to use it with your example:

    Private Sub Command1_Click()
    Dim dblRet As Double
    dblRet = 2 ^ 32
    AndQ dblRet, 2 ^ 32
    Debug.Print "the operation 2 ^ 32 AND 2 ^ 32 equals " & CStr(dblRet)
    End Sub

    Author Comment

    ok, i understand your statement and it woks with my original example. (thanks for that)

    however, can you tell me why coding the call of AndQ through this function...

    Function MyAnd(Nb1, Nb2)

        AndQ Nb1, Nb2
        MyAnd = Nb1

    End Function

    ...returns eg 2 when i type MyAnd (2,4)

    but typing ? (2 and 4) in the debug window returns 0

    At the end, my goal is to have a similar way of working than with the original AND-bitwise comparison.

    not sure i'm very clear....

    Thanks again for your help


    Author Comment

    and also note that i still got the same result if i declare my variables and the function itself as doubles :

    Function MyAnd(Nb1 As Double, Nb2 As Double) As Double
        AndQ Nb1, Nb2
        MyAnd = Nb1
    End Function
    LVL 13

    Expert Comment


    the error is in the dll,

    try this one, it works:

    Private Function MyAnd(Nb1 As Double, Nb2 As Double) As Double
        AndQ Nb1, CLng(Nb2)       'converting to long does the trick
        MyAnd = Nb1
    End Function
    LVL 13

    Expert Comment


    i think your best bet is to write a dll yourself, or to split a double in two Longs

    see this question for the double longs:

    (especially the accepted answer)

    Author Comment

    do you mean that if i split my 2 doubles into 4 longs, i should then use the AND-bitwise
    operator with my 4 numbers (instead of 2) ?


    instead of : if (x and y) then statements
    i could have : if (x1 and x2 and y1 and Y2) then statements


    and could you also elaborate on how to split a double in two longs ? i read the thread
    but did not get how a 1.1 double is derived into 2 longs (-1717986918 and 1072798105) ?!!?

    forgive me if my questions seems dumb, but as you can guess, i'm new to binaries.....



    Author Comment

    and btw, the dll must be really buggy (??), because even when converting the 2nd operand
    to long as you suggested, it still doesn't work with every case !

    check with MyAnd(3,2) which results into 0 instead of 2 !

    i tried mailing the author of the dll, but got no answer so far :(

    or are we both missing something ????
    LVL 13

    Expert Comment

    >>or are we both missing something ????

    i don't think, cause i know pretty good how the "and" operation works

    what i mean by splitting is this:

    take the ("Big") hexadecimal value FD and the value AB

    now both split them and perform an bitwise and:

    F    D
    A    B

    F and A = A
    D and B = 9

    now join the 2 parts:


    and voila, your "Big" number


    Author Comment

    i got an answer from dll's author who told me that the prb was not with his dll but with the way VB stores doubles variables. He explained me that a work-around to have is dll working was to split my doubles variables into arrays of two longs (just like you suggested).

    But i'm really lost with hexs.... (!) i got your above example, but how am i suppose to split, very big values,
    say 2^40 or 2^64, into two longs ? or into hexs ?

    i'm not familiar with hex/binary notations... i think hexs has to be left-padded with zeroes to reach
    16 chars, that's it ? But how do you represent 2^65 in hex ? or bigger : 2^150 ???

    btw, strangely vb returns 1,84467440737096E+19 (18 446 744 073 709 600 000) for 2^64 when it should be
    18 446 744 073 709 55 616, isn't it ? Do you know why ?

    Thanks again for your answers.
    LVL 13

    Expert Comment


    just to let you know i didnt left this Q:
    i'm a little short on time now, i'll get back here as soon as possible (i think friday)

    Author Comment

    Thanks again, if it can give you more ideas, here is how i use the AndQ function (i had to find a MyHex
    function as the internal VB's Hex function is also limited to longs)

    Function MyHex(ByVal Number)
    Const HexChars = "0123456789ABCDEF"

        Number = CDbl(Number)
        If Number = 0 Then
            MyHex = "&H00000000&H00000000"
            Exit Function
        End If
        While Number > 0
            MyHex = Mid(HexChars, 1 + (Number - 16 * Fix(Number / 16)), 1) & MyHex
            Number = Fix(Number / 16)
        MyHex = "&H" & String(16 - Len(MyHex), "0") & MyHex
        MyHex = Left(MyHex, 10) & "&H" & Right(MyHex, 8)
    End Function

    Then, i also created a MyAnd function, in order to reproduce, through the dll's AndQ function,
    the internal VB's And function behavior :

    Function MyAnd(ByVal Res As Double, ByVal var2 As Double) as Boolean
    'An array of two Longs (1st operand)
    Dim strtmp As String

        strtmp = MyHex(Res)

    Dim lArray(1 To 2) As Long
    lArray(2) = Left(strtmp, 10)
    lArray(1) = Right(strtmp, 10)

        strtmp = MyHex(var2)

    'An array of two Longs (2nd operand)
    Dim l2ndOperand(1 To 2) As Long
    l2ndOperand(2) = Left(strtmp, 10)
    l2ndOperand(1) = Right(strtmp, 10)

        AndQ lArray(1), l2ndOperand(1)

       ' MyAnd will be true only if the result of the bitwise comparison is not 0 (&H0)
        MyAnd = ("&H" & Hex(lArray(2)) & Hex(lArray(1))) <> &H0

    End Function

    But these 2 calls (MyHex+MyAnd) considerably slows down the running time of my code (apparently
    10 times slower than the VB's And)
    In addition, i'm not sure the MyHex function can handle very large numbers (eg > 2^64, >2^100...)

    And i won't copy my whole code which computes any possible calculations, but below is the main part
    including how the And (or MyAnd) is used (i have commented the 2 lines used for MyAnd) :
    (note that T() is an Array which stores all the amounts to be tested)

    y = 2 ^ (intNb - 1) ' intNb is the number of amounts to be tested
    For i = 1 To (2 ^ (intNb)) - 1
      z = y
      j = 0: intN = intNb: strCombi = "" ' j stores number of amounts in current operation
            While z > 0
                ' ******** VBs AND Bitwise comparison Method => limited to Longs :((
                ' strcombi stores the current amount in order to produce (at the end) our operation to be tested
                If (i And z) Then j = j + 1:strCombi = strCombi & T(intN) & "+"
                z = z \ 2: intN = intN - 1 ' backslash used for integer division -> limited to longs
                ' ******** ANDq comparison Method => not limited :))
    '            If MyAnd(i, z) Then j = j + 1:strCombi = strCombi & T(intN) & "+"
    '            z = Int(z / 2): intN = intN - 1
            ' As our goal is to check sums between at least 2 amounts, no need to bother when there's only 1 !
            If j > 1 Then
                ' Let's remove the last '+' from our final operation to be tested
                strCombi = Left(strCombi, Len(strCombi) - 1)
                ' Now let's check operation's result
                ' !!! Warning : the Replace Function is used here when decimal separator in Regional Settings is a comma (,)
                ' !!! Remove the Replace if your decimal separator is the dot (.)
                If Eval(Replace(strCombi, ",", ".")) = 0 Then
                   debug.print strcombi
                intNb = 0: intN = 0: i = 0: j = 0: y = 0: z = 0
                strCombi = ""
                End If
            End If
    Note that i also implemented an exit of the for-next loop as soon as 1 combination=0 is found. This
    way i can re-launch the process with less number of amounts for the next pass (thus will reduce next
    number of possibilities, thus running time)

    Thanks for your help.

    LVL 13

    Accepted Solution


    ok, i haven't forgot about you, here are some functions that you might need:

    '-----------------------------------start cutting here-------------------------------------------
    Private Sub DblToArr(lHugeNumber As Double, ByRef tmpArr() As Long)
    Dim tmpVal As Long, tmpVal2 As Double, n As Long
       'what this sub does, is breaking the value in pieces of 6 hexadecimal digits,
       'so &HFFFFFFF becomes &HF and &HFFFFFF
       Erase tmpArr   'make sure it is empty
       tmpVal2 = lHugeNumber \ 16777216         '&H1000000
       tmpVal = lHugeNumber - tmpVal2 * 16777216
       ReDim tmpArr(0)
       tmpArr(0) = tmpVal
       lHugeNumber = tmpVal2
       n = 1
       While tmpVal2 <> 0
          'tmpVal = CInt(tmpVal2 And andVal)
          tmpVal2 = lHugeNumber \ 16777216
          tmpVal = lHugeNumber - tmpVal2 * 16777216
          ReDim Preserve tmpArr(0 To n)
          tmpArr(n) = tmpVal
          lHugeNumber = tmpVal2
          n = n + 1
    End Sub

    Private Sub ArrToDbl(tmpArr() As Long, ByRef lHugeNumber As Double)
    Dim n As Long
       'this sub does exactly the reverse
    lHugeNumber = 0         'clear the var
    For n = UBound(tmpArr) To LBound(tmpArr) Step -1
       lHugeNumber = lHugeNumber * 16777216 + tmpArr(n)
    End Sub
    '-----------------------------------stop cutting here-------------------------------------------

    example usage:

    '-----------------------------------start cutting here-------------------------------------------
    Private Sub Command1_Click()
    Dim tmp() As Long, dValue As Double
       DblToArr CDbl(268435455), tmp()           '&HFFFFFFF
       ArrToDbl tmp, dValue
          MsgBox CStr(268435455) & " became: " & vbCrLf & dValue
       DblToArr CDbl(268435456), tmp()           '&H10000000
       ArrToDbl tmp, dValue
          MsgBox CStr(268435456) & " became: " & vbCrLf & dValue
    End Sub

    '-----------------------------------stop cutting here-------------------------------------------

    when you perform and operations, be careful:

    the "smallest" part, eg the 6 most right hexadecimal digits are in the first part


    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Highfive Gives IT Their Time Back

    Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

    There are many ways to remove duplicate entries in an SQL or Access database. Most make you temporarily insert an ID field, make a temp table and copy data back and forth, and/or are slow. Here is an easy way in VB6 using ADO to remove duplicate row…
    You can of course define an array to hold data that is of a particular type like an array of Strings to hold customer names or an array of Doubles to hold customer sales, but what do you do if you want to coordinate that data? This article describes…
    Get people started with the process of using Access VBA to control Excel using automation, Microsoft Access can control other applications. An example is the ability to programmatically talk to Excel. Using automation, an Access application can laun…
    This lesson covers basic error handling code in Microsoft Excel using VBA. This is the first lesson in a 3-part series that uses code to loop through an Excel spreadsheet in VBA and then fix errors, taking advantage of error handling code. This l…

    760 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    8 Experts available now in Live!

    Get 1:1 Help Now