Bit Twiddling

What is bit twiddling

Sometimes you need to do many logical operations at once. For example, consider the problem where you want to find which numbers exist in both of two strings, which are stored in an 2 cells.
`A1:``    12345`
`A2:``    246`

The answer is 24, but how would you do it? You could do something with Search but it would be horrendously complicated. Imagine also if the list was not even sorted,
`A1:``    32451`
`A2:``    426`

Using Search would become even more complex. Using the bit twiddling formulas we will look at here, the formula to solve both problems is the same,
`    =bitAnd(a1:a2)`

You can even sort the list , and remove duplicates,  by using
`bitAnd(a1)`

You can also test if a a list is a subset of another list
`if ( bitand(a1,a2)=a1, "subset","not subset")`
`if ( bitand(a1,a2)=bitand(a1), "subset","not subset")   ' this would be a better test, as it would ensure that a1 was sorted in the right order before comparing them.`

Why would you need it

A couple of examples are above, but if you combine this with array formulas, suddenly very complex operations become possible in a single formula. Naturally if you are working in VBA you can do bit twiddling in your procedure, but exposing bit twiddling capabilities through user defined functions means that you can also do it in your spreadsheet.

How does it work

If you are reading this section you probably know, but here is how.
• First the list is converted into a string of 1 and 0's .. a binary mask.. that represents the string of numbers. Note that these lists are treated as a series of individual digits, not treated as a single number. so 246 is 2,4,6 ; not 246. 246 would be represented as a series of bits, 101010, and 12345 as 11111. By the way, read these binary numbers right to left.
• Perform an AND operation on the result. That means that if either corresponding bit is 0, the result will be 0. Only if both are 1 will the result be 1. So 101010 AND 11111 gives us 1010.
• Convert back into a string, 1010 gives 24.
Thats all there is to it.

User defined functions

There are a few UDFs associated with this capability, but for the moment we will focus on the AND function.
`bitAND(a[,b])`

This function has a few behaviors depending on the nature of the arguments a and (optional) b. In particular it can accept and produce arrays. We'll see more of that later.
• In each case either or both arguments can be a range, a string, or an array.. The result will be a single result or an array, depending on whether argument B is present.
• If only argument A is present, each of the items represented by the range or array A, are ANDed together, and there will be a single result.
• If both A and B are present, and they have the same number items (for example bitAND(A1:A3,B1:B3) ), then each item in A will be ANDed with the corresponding item in B, and the result will be an Array (see array formulas), or a single result if there is only 1 item in each of A and B.
• If both A and B are present, and one of them has only 1 item, the that item will be ANDed with each of the items in the other argument. For example bitAND( C1,A1:A3)., The result will be an array, or a single result if there is only 1 item in each of A and B.
Some examples
`=bitAnd(A65)          ' Sorts and deduplicates the contents of the list in A65`
`=bitAND(A20,A21)      ' ANDS the list in a20 with the one in A21`
`{=bitAND("12",A2:A4)} ' entered as an array formula, will and 12 with each of a2:a4 and return an array with 3 results`
{=afsep("",IF(bitAnd(C64:C72,E66)=C64:C72,B64:B72,""))} ' if any of c64:C72 is a subset of C64, show the corresponding                  value in B64:B72, and use the afsep function to display the resulting array.

Example Usage

While developing a Sudoku Solver and Generator as one of this site's VBA projects to demonstrate recursion, it occurred to me that there must be a formula that could describe the existence of Naked & Hidden sets - a technique in Sudoku for reducing candidates during the solving process Although these bit twiddling functions are not used in the solver (there are more efficient ways to do this in VBA), i reasoned that if i could boil down the rules in terms of a constraint formula, I could develop a more efficient solver. To be able to do that, I first had to write a few UDF to do bit twiddling. The next section will show that formula, to futher explore bit twiddling and in particular , the application  of array formulas.

UDF code

Here is the code you will need to introduce into your sheet to be able to use these functions
Option Explicit

`Function afConc(arr() As Variant) As String`

`    afConc = afSep("|", arr)`
`End Function`

`Function afSep(sep As String, arr() As Variant) As String`
`    Dim i As Long, s As String`
`    s = ""`
`    For i = LBound(arr) To UBound(arr)`
`        If Len((arr(i, 1))) > 0 Then`
`            s = s & arr(i, 1) & sep`
`        End If`
`    Next i`

`    afSep = s`
`End Function`

`Function bitMake(s As String) As Long`
`    Dim i As Long, x As Long`
`    x = 0`
`    For i = 1 To Len(s)`
`        x = (x Or (CLng(2) ^ (CLng(Mid(s, i, 1)) - 1)))`
`    Next i`
`    bitMake = x`

`End Function`
`Function bitunMake(x As Long) As String`
`    Dim i As Long, t As String`

`    If x <> 0 Then`
`        For i = 0 To 30`
`            If ((CLng(2) ^ i) And x) <> 0 Then t = t & CStr(i + 1)`
`        Next i`
`    End If`
`    bitunMake = t`

`End Function`

`Function arConc(rIn As Range) As String`
`    Dim r As Range, s As String`
`    For Each r In rIn.Cells`
`        s = s & CStr(r.Value)`
`    Next r`
`    arConc = s`
`End Function`
`Private Function nArrayDims(ParamArray args()) As Long`
`    Dim n As Long, x As Long`
`    n = 1`
`    `
`    On Error Resume Next`
`    While Err.Number = 0`
`        x = LBound(args, n)`
`        If Err.Number = 0 Then`
`            n = n + 1`
`        Else`
`            nArrayDims = n - 1`
`        End If`
`    Wend`
`End Function`
`Function bitAnd(ParamArray args()) As Variant`
`    Dim narg2 As Long, n As Long, narg1 As Long, narg As Long, lb As Long, ub As Long, ulim As Long`
`    Dim aResult() As String`
`    `
`    ' if there are 2 args, then the first is anded with the second, only 1 or 2 args allowed`
`    narg = UBound(args) - LBound(args) + 1`
`    If narg > 2 Or narg < 1 Then`
`        bitAnd = CVErr(xlErrValue)`
`        Exit Function`
`    End If`
`    lb = LBound(args)`
`    ub = UBound(args)`
`    `
`    If narg = 1 Then`
`        bitAnd = bitGeneralAnd(args(lb))`
`    Else`
`        narg1 = bitArrayCount(args(lb))`
`        narg2 = bitArrayCount(args(ub))`
`        ulim = narg1`
`        If narg2 > ulim Then ulim = narg2`
`        ulim = ulim + lb - 1`
`        `
`        If Not (narg1 = 1 Or narg2 = 1 Or narg1 = narg2) Then`
`            bitAnd = CVErr(xlErrValue)`
`            Exit Function`
`        End If`
`        `
`        ReDim aResult(lb To ulim)`
`        `
`        Select Case narg1`
`            Case 1`
`                Select Case narg2`
`                    Case 1          ' 1-1`
`                        aResult(lb) = bitunMake((bitMake(bittoString(args(lb))) And bitMake(bittoString(args(ub)))))`
`                    `
`                    Case Else     ' 1 arg 1, applied to each of arg2`
`                        For n = lb To ulim`
`                            aResult(n) = bitunMake((bitMake(bittoString(args(lb))) And bitMake(bittoString(args(ub)(n + 1)))))`
`                        Next n`
`                        `
`                End Select`
`            `
`            Case Else`
`                Select Case narg2`
`                    Case 1          ' arg2 applied to each of arg1`
`                        For n = lb To ulim`
`                            aResult(n) = bitunMake((bitMake(bittoString(args(lb)(n + 1))) And bitMake(bittoString(args(ub)))))`
`                        Next n`
`                    `
`                    Case Else      ' each of arg1 applied to each of narg2`
`                        For n = lb To ulim`
`                            aResult(n) = bitunMake((bitMake(bittoString(args(lb)(n + 1))) And bitMake(bittoString(args(ub)(n + 1)))))`
`                        Next n`
`                        `
`                End Select`

`        End Select`
`        bitAnd = Application.WorksheetFunction.Transpose(aResult)`
`    End If`

`End Function`
`Private Function bittoString(arg1 As Variant)`
`    Dim r As Range`
`    `
`    If bitisRange(arg1) Then`
`        Set r = arg1`
`        bittoString = CStr(r.Value)`
`    Else`
`        bittoString = CStr(arg1)`
`    End If`
`    `
`End Function`
`Private Function bitisRange(arg1 As Variant) As Boolean`
`    bitisRange = False`
`    `
`    If IsObject(arg1) Then`
`        If TypeOf arg1 Is Excel.Range Then`
`            bitisRange = True`
`        Else`
`            bitisRange = CVErr(xlErrValue)`
`       End If`
`    End If`
`        `
`End Function`
`Private Function bitArrayCount(arg1 As Variant) As Long`

`    If bitisRange(arg1) Then`
`        bitArrayCount = arg1.Cells.Count`
`        `
`    `
`    ElseIf IsArray(arg1) Then`
`        bitArrayCount = UBound(arg1) - LBound(arg1) + 1`
`    `
`    Else`
`        bitArrayCount = 1`
`    `
`    End If`
`        `
`End Function`
`Private Function bitGeneralAnd(arg As Variant) As String`
`     Dim i As Long, x As Long, t As String, n As Long, r As Range, narg As Long`
`    ' can take a range input`
`     x = &HFFFFFFFF`
`    If bitisRange(arg) Then`

`            For Each r In arg.Cells`
`                x = (bitMake(CStr(r.Value)) And x)`
`            Next r`

`    `
`    ' or an array input`
`    ElseIf IsArray(arg) Then`

`        For i = LBound(arg) To UBound(arg)`
`            x = (bittoString(arg(i)) And x)`
`        Next i`

`    ' or just a list`
`    Else`
`        x = (bitMake(CStr(arg)) And x)`

`    End If`
`    bitGeneralAnd = bitunMake(x)`
`    `
`End Function`

Subpages (1):