Part 3: Bitwise OR, AND’s sibling
A review of the bitwise OR function (∨ or |) and of its relation to AND.
The result of a bitwise OR operation between two bit words b1 and b2 is a bit word containing 1s in slots where either b1 or b2 contains 1s. In the example above, b1 has 1s in positions 2, 3, 5 (from right to left), and b2 has 1s in positions 2, 3, 4, 7, so b1 ∨ b2 is a bit string with 1s in positions 2, 3, 4, 5, 7, that is, 01011110. Again, simple.
Just like we did in The beauty of bitwise AND, we will ignore the numeric function, and try to find the pattern of OR, by examining simple properties as well as some of the first values of a ∨ b. Let’s go!
If we note f : (a, b) → a ∨ b, where ∨ is the OR operation, f has the following properties:
- f is symmetrical: f(a, b) = f(b, a)
- f(a, a) = a
- Since OR takes all the positive bits from both operands, a ∨ b is always greater than the greater operand, i.e. f(a, b) ≥ max(a, b)
With these observations and a few manual calculations, we get the following graph:
The pattern is familiar. It shares with that of AND, that it is organized in tiers, with 3, 7, 15 playing key roles in separating those tiers; each tier possesses three square blocks, and all blocks are tied by simple mathematical relationships. (Note: tiers and blocks are defined in the previous post)
However, unlike AND:
- OR tiers are organized around predecessors of powers of 2 (3, 7, 15…), whereas AND tiers are organized around powers of 2 (2, 4, 8, 16..)
- Within tiers, Tₙ blocks are identical, whereas we found that AND tiers were organized around one ‘principal’ and two ‘auxiliary’ blocks.
- Blocks Tₙ of a tier are equal to the same-size blocks to their lower left plus 2ⁿ. You can verify in the OR graph that T3 is equal to the block found between rows and columns 0 to 6, plus the constant 8 (2³).
This is enough information to define an iterative way to draw an OR graph of arbitrary size. Here are the results:
Notice again the symmetry, the tiers and blocks, and the fact that all three blocks of any given tier are identical.
Besides, notice the amount of light (i.e., high values), in those graphs, in sharp contrast with the AND graphs, whose edges were constantly dark. Blocks also seem to follow a pattern, drawing something that resembles an arrow or a bird, but flipped around in the OR graph. Generally, it is almost as though OR mirrored the AND pattern. Close enough.
OR + AND
If we superpose the AND and OR patterns (respectively first and second images from the left), we find a third pattern, made of a simple linear gradient with an angle of direction of 45°. It is the pattern of a sum function, which to any a, b associates a + b. In other words, we have just showed that:
Let’s pause a moment to appreciate the beauty of that expression ❤.
A few observations, in no particular order:
- We could define a OR b numerically as the sum of a and b minus a AND b
- In this context, the symmetry of the notations for the AND or OR operators makes perfect sense. (note: I use the notations found in the Federal Information Processing Standards — FIPS, 180–4)
- You can verify that the expression holds true for the example used through this article and the previous one. To the top, we have 22 ∨ 78 = 94. In my previous post, we showed that 22 ∧ 78 = 6. Using the expression, we can verify that indeed 22 + 78 = (22 ∨ 78) + (22 ∧ 78) = 94 + 6 = 100 (phew).
- Open-ended question: is there a special relationship between the pair (94, 6) and (22, 78)? Is the alternative decomposition of 100 interesting in any capacity? The only intuition I have for (94, 6) is that 6 looks like the carry of a base-2 naive addition while 94 could be some sort of baseline of that addition, jolting down all the 1s as we see them. Not sure if this makes the pair any more useful or special though (note: we’re getting close to the logic of an electronic adder, but are not there yet).
If you have made it so far, thanks a lot, and I hope you have learnt a thing or two about bitwise OR.
