Bit Hack implement addition and multiplication with macros and bit operations

Implement addition and multiplication in pure macros.

Addition:

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

#define FULL_ADDER_S(_A,_B,_C) (HALF_ADDER_S(HALF_ADDER_S(_A,_B),_C))
#define FULL_ADDER_C(_A,_B,_C) (HALF_ADDER_S(HALF_ADDER_C(HALF_ADDER_S(_A,_B),_C),HALF_ADDER_C(_A,_B)))

#define __ADDER_1_S(_A,_B,_C) FULL_ADDER_S(_A,_B,_C)
#define __ADDER_1_C(_A,_B,_C) FULL_ADDER_C(_A,_B,_C)

#define __ADDER_2_S(_A,_B,_C) (__ADDER_1_S(_A&1,_B&1,_C)| __ADDER_1_S((_A)>>1,(_B)>>1,__ADDER_1_C(_A&1,_B&1,_C))<<1)
#define __ADDER_2_C(_A,_B,_C) __ADDER_1_C((_A)>>1,(_B)>>1,__ADDER_1_C(_A&1,_B&1,_C))

#define __ADDER_4_S(_A,_B,_C) (__ADDER_2_S(_A&3,_B&3,_C)| __ADDER_2_S((_A)>>2,(_B)>>2,__ADDER_2_C(_A&3,_B&3,_C))<<2)
#define __ADDER_4_C(_A,_B,_C) __ADDER_2_C((_A)>>2,(_B)>>2,__ADDER_2_C(_A&3,_B&3,_C))

#define __ADDER_8_S(_A,_B,_C) (__ADDER_4_S(_A&15,_B&15,_C)| __ADDER_4_S((_A)>>4,(_B)>>4,__ADDER_4_C(_A&15,_B&15,_C))<<4)
#define __ADDER_8_C(_A,_B,_C) __ADDER_4_C((_A)>>4,(_B)>>4,__ADDER_4_C(_A&15,_B&15,_C))

#define __ADDER_16_S(_A,_B,_C) (__ADDER_8_S(_A&255,_B&255,_C)| __ADDER_8_S((_A)>>8,(_B)>>8,__ADDER_8_C(_A&255,_B&255,_C))<<8)
#define __ADDER_16_C(_A,_B,_C) __ADDER_8_C((_A)>>8,(_B)>>8,__ADDER_8_C(_A&255,_B&255,_C))

#define __ADDER_32_S(_A,_B,_C) (__ADDER_16_S(_A&65535,_B&65535,_C)| __ADDER_16_S((_A)>>16,(_B)>>16,__ADDER_16_C(_A&65535,_B&65535,_C))<<16)
#define __ADDER_32_C(_A,_B,_C) __ADDER_16_C((_A)>>16,(_B)>>16,__ADDER_16_C(_A&65535,_B&65535,_C))

#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

    • 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.

Leave a Reply

Your email address will not be published. Required fields are marked *