TAOCP 7.1.3 Exercise 120

Let $R=\mathbb{Z}/2^n\mathbb{Z}$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 120. ▶ [M25] [M25] There are 2n2mn functions that take n-bit numbers (x1, . . . , xm) into an n-bit number f(x1, . . . , xm). How many of them can be implemented with addition, subtraction, multiplication, and nonshift bitwise Boolean operations (modulo 2n)?

194 COMBINATORIAL SEARCHING 7.1.3

Verified: yes
Solve time: 2m41s

Let $R=\mathbb{Z}/2^n\mathbb{Z}$. The allowed operations are addition, subtraction, multiplication in $R$, and bitwise Boolean operations on $n$-bit words. We show that every function

$$ f:(R)^m \to R $$

is representable, hence the number of implementable functions equals the total number of functions.

1. Total number of functions

Each input is an $m$-tuple of $n$-bit words, so the domain has size

$$ |R|^m = (2^n)^m. $$

Each function chooses an $n$-bit output for each input, so the total number of functions is

$$ (2^n)^{(2^n)^m} = 2^{n(2^n)^m}. $$

It remains to show that all such functions are implementable.

2. Bitwise equality masks

Fix $a=(a_1,\dots,a_m)\in R^m$. For each coordinate define the bitwise XOR equality test

$$ u_{i,a_i}(x_i) = \overline{x_i \oplus a_i}. $$

This is an $n$-bit word satisfying:

  • $u_{i,a_i}(x_i) = -1$ (all bits $1$) if $x_i=a_i$,
  • $u_{i,a_i}(x_i) = 0$ otherwise.

Define the combined mask

$$ E_a(x_1,\dots,x_m) = \bigwedge_{i=1}^m u_{i,a_i}(x_i). $$

Then:

  • $E_a(x) = -1$ if $x=a$,
  • $E_a(x) = 0$ otherwise.

Thus the family ${E_a}$ forms a pointwise partition in the sense that for each $x$, exactly one $E_a(x)$ equals $-1$, all others are $0$.

3. Converting masks to ${0,1}$-indicators

We need arithmetic selectors, not $-1/0$ masks.

Let $\mathbf{1}$ denote the word $00\cdots 01$, which is available as a constant in $R$. Define

$$ \varepsilon_a(x) = E_a(x)\ &\ \mathbf{1}. $$

Since $E_a(x)$ is either:

  • $00\cdots 00$, or
  • $11\cdots 11$,

we obtain:

  • if $E_a(x)=0$, then $\varepsilon_a(x)=0$,
  • if $E_a(x)=-1$, then $\varepsilon_a(x)=1$.

Hence $\varepsilon_a(x)\in{0,1}$ and

$$ \varepsilon_a(x)=1 \iff x=a. $$

Moreover,

$$ \sum_{a} \varepsilon_a(x) = 1 \quad \text{for all } x, $$

since exactly one term equals $1$.

4. Reconstructing an arbitrary function

For each $a\in R^m$, let $f(a)\in R$ be the desired output constant.

Define

$$ F(x_1,\dots,x_m) = \sum_{a\in R^m} f(a)\cdot \varepsilon_a(x_1,\dots,x_m), $$

where multiplication and addition are in $R$, and the sum is an iterated finite sum over all $a$.

For a fixed input $x$, exactly one term $\varepsilon_a(x)$ equals $1$, and all others are $0$. Hence

$$ F(x) = f(x). $$

Thus every function $f$ is representable using the allowed operations.

5. Conclusion

All functions $f:(\mathbb{Z}/2^n\mathbb{Z})^m \to \mathbb{Z}/2^n\mathbb{Z}$ are implementable with addition, subtraction, multiplication modulo $2^n$, and nonshift bitwise Boolean operations.

Therefore the number of implementable functions equals the total number of functions:

$$ \boxed{2^{n(2^n)^m}}. $$