Search code examples
mathbit-manipulationbitwise-operators

Multiplication using bitwise operations

I've been looking around for a way to extended a boolean function in boolean algebra into the classical algebra and I think all I need is Multiplication and Addition to do that so assuming that a,b are two unsigned integers in the range [0, 232 - 1], we know that

a + b = a&b + a|b    / "+" is the ordinary addition in algebra

which is half of what I want, now I need to find what is a*b. I tried the following:

if a = c*d then

cd + b = (cd)&b + (cd)|b
=> cd = (cd)&b + (cd)|b - b

which means that in any multiplication there is third variable I should keep in mind? what I'm looking for is something like this

ab = f(a,b)

where f(x,y) is a boolean function

EDIT: as @DavidGrayson mentioned I should clarify more so, what I'm looking for is a way of describing a * b using a combination of bitwise operators with or without algebraic operators (+,-, ... ) Just like the example of a + b above we can see that we've described the algebraic operation '+' with bitwise operators, so can we do the same with multiplication?

Solution

  • I still have no idea why you are asking this question, but you specified that you are looking for

    a way of describing a * b using a combination of bitwise operators with or without algebraic operators

    You also explicitly said in the comments that * is an algebraic operator we are allowed to use.

    Later, you added that there must be a boolean operator linking a and b.

    So I will answer your question by saying:

    a * b = (a | (0 & (a | b))) * (b | 0)

    This is a formula for a * b that uses bitwise operators so it meets all your conditions.