Multiplication using bitwise operations

Question

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, 2³² - 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?

`*` is a special character in markdown syntax with causes italic text. Try escaping it with a slash to fix the formatting: `\*` — David Grayson, Jun 16 '22 at 00:33
Does this answer your question? [Multiplication of two integers using bitwise operators](https://stackoverflow.com/questions/4456442/multiplication-of-two-integers-using-bitwise-operators) — Eduardo Thales, Jun 16 '22 at 00:33
@EduardoThales no, because I want to find an algebric equation like the one for (a+b) not an algorithm that based on a while loop — Taha Khabouss, Jun 16 '22 at 00:37
If you are allowed to use `+` in the equation for `a + b`, can we use `*` in the equation for `a * b`? — David Grayson, Jun 16 '22 at 00:42
I’m not sure I understand what you’re asking here. What specifically is special about the identity `a + b = (a & b) + (a | b)` that you’re trying to generalize to multiplication? — templatetypedef, Jun 16 '22 at 00:45
Yeah, a rigorous definition of what you mean by "boolean function" is needed, because your use of that phrase doesn't match what people normally mean: https://en.wikipedia.org/wiki/Boolean_function — David Grayson, Jun 16 '22 at 00:47
@DavidGrayson yes ofcourse, as I mentioned ab = f(a,b) , f can have any operation — Taha Khabouss, Jun 16 '22 at 00:51
@templatetypedef I'm tryin to find a bridge bitween boolean algebra and classic algebra — Taha Khabouss, Jun 16 '22 at 00:51
Then I'll post an answer where I define `f` with `f(a, b) = a * b` and you'll really accept it? — David Grayson, Jun 16 '22 at 00:52
@TahaKhabouss Can you elaborate on what you mean by that? I’m not sure I get what a “bridge” means in this context. — templatetypedef, Jun 16 '22 at 00:52
@templatetypedef a way of describing boolean operators using algebra (*,-,+...) — Taha Khabouss, Jun 16 '22 at 00:54
You need to specify very precisely what kind of answer you are looking for or else this will get closed. It sounds like you are looking for a function `f` that takes two arguments and yields the product of them, so why can't I just answer your question with `f(a, b) = a * b` and thus solve your problem? — David Grayson, Jun 16 '22 at 00:55
`a + b = a&b + a|b` doesn't really accomplish anything. You are "simplifying" addition by replacing it with some bitwise operations and... another addition. Why not "simplify" to `a + b = (a|a) + (b|b)`? — Raymond Chen, Jun 16 '22 at 01:45
@RaymondChen that's what i'm trying to do, I'm trying to replace addition with bitwise operations that could link a and b with bitwise operator — Taha Khabouss, Jun 16 '22 at 01:51
I’m sorry, I still don’t understand what you’re asking for here. The original equality you’re mentioning with addition doesn’t replace addition with a simpler operation, and is just an identity that involves addition in two different contexts. What specific insights does that provide that you’d like to replicate with multiplication? — templatetypedef, Jun 16 '22 at 02:33
start with 1bit*1bit , then 2bit*2bit ... using Karnaugh maps to get boolean algebra result only ... however for 32bit * 32bit the stuff will be very complicated ... that is not how its done in real HW ... usually boolean algebra is combined with arithmetic addition in a sequencial automat like Shift and Add or binary long multiplication ... as mentioned before defining operator with the same operator is nonsense ... and would lead to stack overflow if coded like that ... — Spektre, Jun 16 '22 at 16:50

David Grayson · Accepted Answer · 2022-06-16T01:15:23.387

1

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.

edited Jun 16 '22 at 01:15

answered Jun 16 '22 at 01:05

David Grayson

84,103
24
152
189

in this sense we could also say that a + b = (a | 0) + (b | 0) instead of a + b = a&b + a|b maybe I couldn't clarifying my question enough but (a|0) is just (a), also there is not boolean operator linking a and b somehow instead it's just the algebraic operator * – Taha Khabouss Jun 16 '22 at 01:10
1

You keep changing the goal posts. – David Grayson Jun 16 '22 at 01:11
I modified my answer so it includes `a | b`. I could similarly modify it to include `a OP b` for any binary operator you want. Please click the checkmark. – David Grayson Jun 16 '22 at 01:13
my goal is to find something like this a * b = a&b + .. + a|b .. what you're doing is just adding and subtracting like a = a + b - b you're equation is reversible to it's original form just a step ahead – Taha Khabouss Jun 16 '22 at 01:15
that "0" in you're equation doesn't match my conditions – Taha Khabouss Jun 16 '22 at 01:16
If you're changing the goalposts yet again then I can replace `0` with `a & ~a` but that seems pointless, you'll just make up another rule after I do that. – David Grayson Jun 16 '22 at 01:58
I think you're trying to look for a function that has the same aesthetics as `(a | b) + (a & b)` but aesthetics are opinion-based and not suitable for StackOverflow. Maybe try on a Math reddit group or something. – David Grayson Jun 16 '22 at 02:00
yes you're right, will do. thank you ^^ – Taha Khabouss Jun 16 '22 at 02:03

Multiplication using bitwise operations

1 Answers1