Bitwise Aggregation
This is an aggregation of my posts on bitwise functions and the updates thereto, edited for continuity. The original posts were published on December 30, 2006 and January 1, 2007.
Bit-by-Bit
A while back, I was having a discussion with Asher about converting bitwise functions (and, or, not, exclusive or) into simple expressions using simple arithmetic. Here are what we came up with … they all operate on two bits, A and B, whose values are of course 0 or 1:
| Exclusive Or | A ⊕ B ≡ A + B - 2AB |
| And | A ⋀ B ≡ AB |
| Or | A ⋠B ≡ A + B - AB |
| Not | ¬A ≡ 1 - A |
The Bigger Picture
It’s not so easy to operate on a number without exploding it into individual bits and operating on each; I have not found if it is possible to do so at all. That said, the following expression is a crude equivalent to performing A â‹€ B:
where n is the number of bits to flip (i.e. 8 for a byte). The index of the highest set bit is ⎿Log2A⌠+ 1.
In the formulae above, we can substitute this summation for AB and get valid functions that operate on entire integers. Others can be done more gracefully:
| One’s Complement | ¬A ≡ 2n - A - 1 |
| Shift Left | A << B ≡ A * 2B |
| Shift Right | A >> B ≡ ⎿A * 2-B⌠|
Ambiguous And
One thing that would make arithmetic equivalents of the bitwise functions useful is the ability to use algebra to simplify complex calculations such as hashing functions. One could even imagine solving hashing functions for possible inputs…
However, it is not possible to solve A ∧ B = C for an exact value of B, due to the fact that 1 ∧ 0 = 0 ∧ 0 = 0. In other words, if one bit is zero, the other cannot be determined, unlike xor.
That said, here’s a little hack I made in Mathematica to output a “mask mask” - that is, the bits of B that we know for sure, and those that we don’t. As before, n is one less than the number of bits. The output is a string of binary digits, where the digit 2 could be either 0 or 1.
