Bit Twiddling

Page Content hide
1 What is bit twiddling
2 What is bit twiddling
3 Why would you need it
4 How does it work
5 User defined functions
6 Example Usage

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. 

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:

 

You can also test if a a list is a subset of another list 

bitAnd(a1).

 

 

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.
That’s 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.
 

Subpages