Bit Hack implement addition and multiplication with macros and bit operations

Implement addition and multiplication in pure macros.

#define HALF_ADDER_S(_N,_M) ((_N)^(_M))

#define ADD(_A,_B) __ADDER_32_S(_A,_B,0)

Multiplication:

As for calculation $$a*b$$, we can decompose it as follow:

$$a*b$$

$$=a*(b_0*2^0+b_1*2^1+b_2*2^2+…+b_{n-1}*2^{n-1})$$

$$=a*(b_0*2^0+…+b_{\frac{n}{2} -1}*2^{\frac{n}{2}-1 }+b_{\frac{n}{2}}*2^{\frac{n}{2}}+…+b_{n-1}*2^{n-1})$$

$$=a*(b_0*2^0+…+b_{\frac{n}{2} -1}*2^{\frac{n}{2}-1 })+a*(b_{\frac{n}{2}}*2^0+…+b_{n-1}*2^{\frac{n}{2}-1 })*2^{\frac{n}{2} }$$

$$=a*\underline{b} +a*\bar{b}*2^{\frac{n}{2} }$$

(here $$b_i$$ is the digital of $$b$$ in binary, $$\bar{b}$$ is the higher digital part of $$b$$ and $$\underline{b}$$ is the lower part of $$b$$)

Recursively decompose it as above till $$\underline{b}$$ and $$\bar{b}$$ is singular digital. Then we decompose a multiplication to a trivial case:

$$a*\tilde{b} =\left\{\begin{matrix} a \qquad (if \quad \tilde{b}=1)\\0 \qquad (if \quad\tilde{b}=0)\end{matrix}\right.$$

In the code,we use shift operation implement secondary power. However, in macros, it’s quite hard to employ if-branch struct, as for the case above, there is a bit hack solution:

$$a*\tilde{b}=a\wedge ((\tilde{b}\oplus 1)-1)$$

If $$\tilde{b}$$ equal 0, then $$\tilde{b}\oplus 1$$ is 1, and $$a\wedge ((\tilde{b}\oplus 1)-1)$$ is 0. What matter is the case that $$\tilde{b}$$ equal 1, if $$\tilde{b}$$ equal 1, then  $$\tilde{b}\oplus 1$$ is 0, and $$(\tilde{b}\oplus 1)-1$$ is $$(111…111)_2$$ (in binary) due to complement notation, and then $$a\wedge ((\tilde{b}\oplus 1)-1)$$ equal $$a$$, which is what we expect.

And,the complete code:

#define GET_BIT(_N,_POS) (((_N)&(1<<(_POS-1)))>>(_POS-1))
#define SET_MARK(_N) (((_N)^1)-1)
#define _BIT_MUL(_N,_M,_POS) ((_N)&SET_MARK(GET_BIT(_M,_POS)))

#define _MUL1(_N,_M) _BIT_MUL(_N,_M,1)
#define _MUL2(_N,_M) (_MUL1(_N,_M)+(_MUL1(_N,(_M)>>1)<<1))
#define _MUL4(_N,_M) (_MUL2(_N,_M)+(_MUL2(_N,(_M)>>2)<<2))
#define _MUL8(_N,_M) (_MUL4(_N,_M)+(_MUL4(_N,(_M)>>4)<<4))
#define _MUL16(_N,_M) (_MUL8(_N,_M)+(_MUL8(_N,(_M)>>8)<<8))
#define _MUL32(_N,_M) (_MUL16(_N,_M)+(_MUL16(_N,(_M)>>16)<<16))

#define MUL(_N,_M) _MUL32(_N,_M)

3 thoughts on “Bit Hack implement addition and multiplication with macros and bit operations”

1. Fantastic

2. Would it be better if it is implemented in the fashion of templates rather than macros?

• Of course, in TMP, it’s very easy to use if-branch struct and recursion.By contrast, there is no way but to unfold the function call list to implement recursion in macros.