multiplication by Boolean algebra?

Multiplication (multiplication) requires addition (addition), so consider how to achieve addition first, then proceed to multiplication.

The addition of one bit to another is an exclusive OR if you ignore the advance.

• 0 00=0
• 1 00=1
• 0 11=1
• 1 11=0

Then two bits to each other (ignore the third bit).

This requires consideration of the last digit to the top digit.The bit product can be used to determine if a carryover occurs.When a carry occurs, add 1 to the top digit.

Therefore, s=m+n is as follows:The subscripts represent digits.The last digit is set to zero.

• s[0]=m[0] nn[0]
• s[1]=m[1] nn[1]+(m[0]ANDn[0])=m[1] nn[1] ((m[0]ANDn[0])

s[2] Since we do not consider moving forward to , we have changed the addition to exclusive OR.

US>%s[1] Use the left shift to use the result of (m[0]ANDn[0]) to find out.Therefore, the temporary variables x and y can be used to express:

• x=m nn
• y=(mANDn)<<1
• s=x+y=x yy

The question is tagged with a C, so I will write it with a C code.It uses a 0b prefix and must be compiled as a GCC extension or C++.

#include<stdio.h>
# include <assert.h>

unsigned sum2 (unsigned m, unsigned n)
{
    unsigned x=m^n;
    unsignedy=(m&n)<<1;
    return(x^y)&0b11;
}

int main()
{
    for (unsigned m=0; m<=0b11;++m)
    {
        for (unsigned n=0;n<=0b11;++n)
        {
            unsigned s=sum2(m,n);
            printf("%u+%u=%u\n", m, n, s);
            assert(s==(m+n)&0b11);
        }
    }
}

Similarly, more than three bits can be calculated.However, it is a little more complicated as the result of calculating the carryover may result in further carryover.

• x₁=m nn
• y₁=(mANDn)<<1
• s=x₁+y₁
  Now, unlike when it's two bits, expand this addition again to exclusive OR, OR, bit shift.
• x₂=x₁ yy₁
• y₂=(x₁ANDy₁1)<<1
• s=x₂ 2

This is what happens when you write in C code.

#include<stdio.h>
# include <assert.h>

unsigned sum3(unsigned m, unsigned n)
{
    unsigned x1 = m^n;
    unsignedy1 = (m&n)<<1;
    unsigned x2 = x1^y1;
    unsigned y2 = (x1&y1)<<1;
    return(x2^y2)&0b111;
}

int main()
{
    for (unsigned m=0; m<=0b111;++m)
    {
        for (unsigned n=0;n<=0b111;++n)
        {
            unsigned s=sum3(m,n);
            printf("%u+%u=%u\n", m, n, s);
            assert(s==(m+n)&0b111));
        }
    }
}

More than 4 bits can be achieved by extending the 3-bit case.

It's a little deformed because I'm trying to use the code C, but it's called a full adder.

The original total adder is a digital circuit that receives three 1-bit inputs and outputs a 1-bit addition result and a 1-bit carry.The three inputs are due to the two operational targets and the advance from the lower digits.Multiple bits can be added by passing through all adder in order from the lower bits.

Of course, it takes time in proportion to the number of bits.Therefore, there are several acceleration techniques for adding multiple bits (such as calculating a carry separately).

To be honest, m*n can be achieved by adding m n times.

A more efficient way is to multiply by one digit and find the sum.In binary, the single digit multiplication is multiplied by 1 or 0, so it can be achieved with addition and some bit operations.

The following code uses the += operator as the addition has been accomplished.Please forgive me.

#include<stdio.h>
# include <assert.h>

unsigned product (unsigned m, unsigned n)
{
    unsigned result = 0;
    while(n!=0)
    {
        // result+=n&1?m:0;
        result+=(unsigned) -(n&1)&m;
        n>>=1;
        m<<=1;
    }
    return result;
}

int main()
{
    for (unsigned m=0; m<=256;++m)
    {
        for (unsigned n=0;n<=256;++n)
        {
            unsigned s=product(m,n);
            printf("%u*%u=%u\n", m, n, s);
            assert(s==m*n);
        }
    }
}

The following is written in C with the same process as simple strokes. Multiplication between 32-bit unsigned integers.

#include<stdio.h>
# include <stdint.h>
# include <intypes.h>

uint64_tadd(uint64_ta, uint64_tb){
    uint64_t result = 0, carry = 0, mask = 1, x, y;

    while(mask){
        x = a & mask;
        y=b&mask;
        result | = x^y;
        if(carry){
            carry=(x&y)||(result&mask);
            result^=mask;
        } else{
            carry=x&y;
        }
        mask<<=1;
    }
    return result;
}

uint64_tmul(uint32_ta, uint32_tb){
    uint64_t result=0;
    uint64_ttmp=a;

    while(b){
        if(b&1){
            result=add(result, tmp);
        }
        tmp<<=1;
        b>>=1;
    }
    return result;
}

int main(void){
    uint32_tx=123456, y=654321;
    uint64_t result=mul(x,y);

    printf("%"PRIu32"*%"PRIu64"=%"PRIu64"\n", x, y, result);

    return 0;
}