So let's assume that all of our coefficients are either 0 or 1. The complement of 0 is 1, and vice versa. This is useful in programming, since inverting the bits of a number is basically doing -x-1.
Let's define some operations. Where
x and
y are binary (0 or 1), then
- ~x means the complement of x, and can be rewritten (1-x).
- x|y is bitwise-OR and can be rewritten as x+y-xy.
- x&y is bitwise-AND and can be rewritten as x*y or xy for brevity.
- x^y is bitwise-XOR and can be rewritten as x+y-2xy.
Observe, then, that:
- x~x is always 0.
- x&x=x.
- x~y+y~x = x-xy+y-yx = x+y-2xy = x^y.
So if we want to multiply, say, a 4-bit number by its complement, we have:
z0 = a0~a0=0
z1 = a1~a1=0
z2 = a2~a2=0
z3 = a3~a3=0
z4 = (a0+a1)(~a0+~a1) = a0~a1 + a1~a0 = a0^a1
z5 = (a0+a2)(~a0+~a2) = a0~a2 + a2~a0 = a0^a2
z6 = (a0+a3)(~a0+~a3) = a0~a3 + a3~a0 = a0^a3
z7 = (a1+a2)(~a1+~a2) = a1~a2 + a2~a1 = a1^a2
z8 = (a1+a3)(~a1+~a3) = a1~a3 + a3~a1 = a1^a3
z9 = (a2+a3)(~a2+~a3) = a2~a3 + a3~a2 = a2^a3
f(x)g(x) = (a0+a1x+a2x^2+a3x^3)(~a0+~a1x+~a2x^2+~a3x^3)
=z0 |=0
+x(z4-z0-z1) | +x(a0^a1)
+x^2(z5-z0-z2+z1) | +x^2(a0^a2)
+x^3(z6-z0-z3+z7-z1-z2) | +x^3(a0^a3+a1^a2)
+x^4(z8-z1-z3+z2) | +x^4(a1^a3)
+x^5(z9-z2-z3) | +x^5(a2^a3)
+x^6z3 | +0