Are there any Bitwise Operator Laws?

Question

Thinking in terms of Algebraic laws, I was wondering if there are any official guide lines which exist in the realm of bit manipulations, similar to Algebra.

Algebraic Example

a - b =/= b - a

Let a = 7 and b = 5

• a - b = 2
• b - a = -2

Let a = 10 and b = 3

• a - b = 7
• b - a = -7

Thus if a > b, b - a will be the negative equivalent to a - b. Because of this, we can say

|a - b| = |b - a|.

Where |x| denotes the absolute value of x.

Bitwise Example

a | b =/= a + b

      00001010 = 10
  OR  00000101 = 5 
  -----------------
      00001111 = 15

Note the unsigned byte manipulation: 10 | 5 = 15, which is synonymous with 10 + 5 = 15

However, if both a and b equal 5 and we OR them, the result would be 5, because a = b, which means we're just comparing the same exact bits with each other, thus resulting in nothing new.

Likewise, if b = 7, a = 10 and we OR them we'll have 15. This is because

    00001010 = 10
 OR 00000111 = 7
 -----------------
    00001111 = 15

So, we can effectively conclude that a | b =/= a + b.

Answer 1

Bitwise operations that are just a boolean operator applied between corresponding bits of the operands follow laws analogous to the laws of Boolean algebra, for example:

• AND (&) : Commutative, Associative, Identity (0xFF), Annihilator (0x00), Idempotent
• OR (|) : Commutative, Associative, Identity (0x00), Annihilator (0xFF), Idempotent
• XOR (^) : Commutative, Associative, Identity (0x00), Inverse (itself)
• NOT (~) : Inverse (itself)

AND and OR absorb each other:

• a & (a | b) = a
• a | (a & b) = a

There are some pairs of distributive operators, such as:

• AND over OR: a & (b | c) = (a & b) | (a & c)
• AND over XOR: a & (b ^ c) = (a & b) ^ (a & c)
• OR over AND: a | (b & c) = (a | b) & (a | c)

Note however that XOR does not distribute over AND or OR, and neither does OR distribute over XOR.

DeMorgans law applies in its various forms:

• ~(a & b) = ~a | ~b
• ~(a | b) = ~a & ~b

Some laws that relate XOR and AND can be found by reasoning about the field ℤ/2ℤ, in which addition corresponds to XOR and multiplication to AND:

• AND distributes over XOR
• Working out products of sums: (a ^ b) & (c ^ d) = (a & c) ^ (a & d) ^ (b & c) ^ (b & d)

There are some laws that combine arithmetic and bitwise operations:

• Subtract by adding: a - b = ~(~a + b)
• Add carries separately: a + b = (a ^ b) + ((a & b) << 1)
• Turn min into max and vice versa: min(a, b) = ~max(~a, ~b), max(a, b) = ~min(~a, ~b)

Shifts have no inverse because of the "destruction" of bits pushed to the edge

left shift (<<) : Associative, Distributive, Identity (0x00)

right shift (>>) : Associative, Distributive, Identity (0x00)

rotate left (rl) : Associative, Distributive, Identity (0x00), Inverse (rr)

rotate right (rr) : Associative, Distributive, Identity (0x00), Inverse (rl)

While shifts have no inverse, some expressions involving shifts do have inverses as consequence of other laws, for example:

• x + (x << k) has an inverse, because it is effectively a multiplication by an odd number and odd numbers have an modular multiplicative inverse modulo a power of two. For x + (x << 1) = x * 3, the inverse is x * 0xAAAAAAAB (for 32 bits, adjust the constant for other sizes)
• x ^ (x << k) has an inverse for a similar reason, but through the correspondence with carryless multiplication.
• Similarly x ^ (x >> k) (with unsigned right shift) has an inverse, it's just the "mirror image" of the above.