cassemblybit-manipulationdivisionmultiplication# How can I multiply and divide using only bit shifting and adding?

How can I multiply and divide using only bit shifting and adding?

Solution

To multiply in terms of adding and shifting you want to decompose one of the numbers by powers of two, like so:

```
21 * 5 = 10101_2 * 101_2 (Initial step)
= 10101_2 * (1 * 2^2 + 0 * 2^1 + 1 * 2^0)
= 10101_2 * 2^2 + 10101_2 * 2^0
= 10101_2 << 2 + 10101_2 << 0 (Decomposed)
= 10101_2 * 4 + 10101_2 * 1
= 10101_2 * 5
= 21 * 5 (Same as initial expression)
```

(`_2`

means base 2)

As you can see, multiplication can be decomposed into adding and shifting and back again. This is also why multiplication takes longer than bit shifts or adding - it's O(n^2) rather than O(n) in the number of bits. Real computer systems (as opposed to theoretical computer systems) have a finite number of bits, so multiplication takes a constant multiple of time compared to addition and shifting. If I recall correctly, modern processors, if pipelined properly, can do multiplication just about as fast as addition, by messing with the utilization of the ALUs (arithmetic units) in the processor.

- Passing the function *cmp(const *void, const *void) as a parameter in C and using it to create a queue?
- Is it safe to use `strstr` to search for multibyte UTF-8 characters in a string?
- Why am I getting a heap-use-after-free error?
- Catch and compute overflow during multiplication of two large integers
- Access a global static variable from another file in C
- "this" pointer in C (not C++)
- Unknown Output of C code
- Yocto- gcc cannot find shared library
- Artifact in one of the triangles in basic OpenGL texture quadrilateral
- How to check if a pointer is valid?
- cJSON Key-Value Parsing
- hi, I am emplementing LZW here and it work great, the problem is that I cant scan and encode a string if it have a (space)
- pthread clean up int/array/struct type variables using pthread_cleanup_push
- Standard way of getting a bit pattern of all ones
- Why doesn't the use of strictly conforming programs and conforming implementations ensure absolute portability?
- Checking emptiness of X macros
- Is it possible to run WebAssembly code async?
- C suddenly messing up values in 2d array
- Socket opening macOS assembly
- GDB outputs arm mnemonics
- What kind of optimization does const offer in C/C++?
- wcstombs segmentation fault
- Fast implementation of complementary error function with 5-digit accuracy
- Ascii to binary calculation is flawed
- what stops GCC __restrict__ qualifier from working
- Why my sig_int() function can't prevent my function from exit in c?
- Allocating user space memory in Linux Kernel
- Determining realloc() behaviour before calling it
- Is it legal to cast a struct to an integer if it has no padding?
- C macro, something weird