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): Sudoku constraints