Part 2: The beauty of bitwise AND (∧ or &)

Exploring and visualizing the many facets of the bitwise AND operation

Bitwise AND: ‘the intersection of ones’

The result of a bitwise AND operation between two bit words b1 and b2 is a bit word containing 1s in slots where both b1 and b2 contain 1s. In the example above, b1 and b2 both have 1s in positions 2 and 3 (from right to left), hence b1 ∧ b2 is 00000110. Simple.

While the result is easily computed and the process easily understood in base 2 (i.e., using the ‘bit strings as language’ lens), the numerical AND function looks in fact non-trivial:

The numeric interpretation of AND — here, b+1 is the bit string length. Source: Wikipedia

You can test by yourself that this functions indeed gives 22 ∧ 78 = 6.

Now, if you find that function dreadful — I am with you. When I first wrote it down, I found it both complicated and unhelpful; after formulating it, my mind was no closer to understanding the kind of pattern the AND function followed, if any.

The pattern behind the AND function: learning by example

Ignoring the complex math formula above, we can still find a number of interesting properties regarding the AND function. Considering the function f : (a, b) → a ∧ b, where ∧ is the AND operation, f has the following (easy to demonstrate) properties:

1. f is symmetrical: f(a, b) = f(b, a)
2. f(a, a) = a
3. f(a, b) produces at most a or b, whichever is smaller: f(a, b) ≤ min(a, b)

This little information is enough to get us started; with some additional calculations, we find the following graph:

AND a pattern emerges.

The horizontal axis is for values of the first operand a; the vertical axis is for values of the second one b; values in cells is the result of f(a,b) = a ∧ b.

This chart has striking features that we did not foresee in our preliminary analysis. Observations:

• There are distinct patterns along rows and columns (01010101… in the first row, 02200220022…in the second row).
• Patterns for rows which are powers of 2 (1, 2, 4, 8, 16) are special, with only zeroes before the bisector and only the row number after we hit the next power of 2.

Finding patterns with pen and paper

• Powers of 2 define what I call tiers, blocks of numbers with distinctive patterns. As an example, everything under row and column 8 (2³) excluding everything under row and column 4 (2²) would be what I call a tier.

Abstracting the pattern

• Each tier is made of 3 square blocks: Tₙ, the block top right of 2ⁿ and contained between a wall of 2ⁿ and zeros; and 2 twin blocks, noted tₙ, respectively to the left of, and below Tₙ. If this sounds complicated, just look at the second sketch — I am simply calling tier 3 the group of blocks T₃ ∪ t₃ ∪ t₃
• The principal block T of tier n is always greater than 2ⁿ; auxiliary blocks t always smaller (easily demonstrated by thinking in bit string notation)
• In fact the principal block Tₙ is exactly tₙ + 2ⁿ. You can verify in the drawings that indeed, T₂ is t₂ + 4, and T₃ is t₃ + 8. Blocks tₙ contain a pattern, and principal blocks Tₙ simply repeat that pattern adding a constant on top.
• … and blocks tₙ are strictly equal to the same-sized blocks immediately under them or to their left. Block t₃ (cols 1–7, rows 9–15) is the same as the block found between cols 1–7 and rows 1–7.

And very naturally, through simple observations and intuitions, we have found a generalized way to draw any arbitrary-sized graph for the AND function:

Initialization: set T1

T1 = 1 2 3
     0 2 2
     1 0 1

Repeat: for any n> 1

• Copy Tₙ₋₁ to the right and to the top (i.e., translate the block by 2ⁿ, horizontally and vertically) to create the two auxiliary blocks tₙ of tier n; insert zeroes in the spaces between the inital block Tₙ₋₁ and the new blocks tₙ
• Add 2ⁿ to one of the auxiliary blocks tₙ to create the values for the principal block Tₙ; insert 2ⁿ in spaces between auxiliary blocks tₙ and principal block Tₙ
• Tier n is now fully defined, repeat all steps for tier n+1

Visualizing better AND graphs

I get that my hand-drawn charts are far from perfect. If you have survived till this section, you deserve to see the better graphs — made this time with d3js.

As before, cells represent f(a,b) = a ∧ b for values of a determined by the horizontal axis; and values of b on the vertical axis; colors are a function of the value (darker is low, brighter is high).

AND graph, 16x16

We easily recognize the features determined above: the linear growth along the bisector, the symmetry, the tiers and blocks, and the mathematical relation between all those blocks.

AND graph, 1024x1024

While this says a lot about the AND function and could be interpreted for many more minutes, I also find this graph simply nice to contemplate. There is a beauty to this AND graph similar to the one I find in Pascal’s triangle. And I hope that beauty has become slightly more visible to you today.

Edits based on the HN discussion: Thanks for the great response! Truly humbled to see your interest for that topic and article. Based on feedback: (i) corrected, f(a, b) ≤ min(a, b) (vs max initially). (ii) The assumption is indeed that we work here with natural integers only; though bit strings for negative integers behave the same way as bit strings for natural ones in bitwise operations, the transcription from base 2 to base 10 for those two groups does not work the same (see 2’s complement). For the sake of simplicity, we assume bit strings as numbers to always be positive integers using the convention that any bit in position i is just worth 2^i.