-
Notifications
You must be signed in to change notification settings - Fork 0
multiply_by_n
Mallikarjunarao Kosuri edited this page Jul 14, 2024
·
1 revision
The multiply_by_n
function multiplies an 8-bit unsigned integer x
by another 8-bit unsigned integer n
using bitwise operations and addition, without using the multiplication operator (*
). This method is efficient and often useful in embedded systems where multiplication instructions might be slow or unavailable.
uint8_t multiply_by_n(uint8_t x, uint8_t n)
{
uint8_t result = 0;
uint8_t multiplier = x;
/* Iterate through the bits of n */
for (int i = 0; i < 8; ++i) {
if (n & (1 << i)) {
/* If the i-th bit of n is set, add the current multiplier to the result */
result += multiplier;
}
/* Update the multiplier by left-shifting it by 1 */
multiplier <<= 1;
}
return result;
}
-
Initialize Variables:
-
result
: To store the final product. -
multiplier
: Starts with the value ofx
and will be updated during the iteration.
-
-
Iterate Through the Bits of
n
:- The loop runs from
0
to7
, checking each bit ofn
.
- The loop runs from
-
Check Each Bit:
- If the
i-th
bit ofn
is1
, the current value ofmultiplier
is added toresult
.
- If the
-
Update Multiplier:
- The
multiplier
is left-shifted by1
to prepare for the next bit check.
- The
Let's consider an example where x = 5
and n = 3
.
-
Binary Representation:
-
x = 5
(binary00000101
) -
n = 3
(binary00000011
)
-
-
Step-by-Step Execution:
Initial Values:
x = 5 (binary 00000101)
n = 3 (binary 00000011)
Iterate through the bits of n:
Bit 0: n & (1 << 0) = 1 (bit is set)
result = result + multiplier (0 + 5) = 5
multiplier <<= 1 (5 << 1) = 10
Bit 1: n & (1 << 1) = 1 (bit is set)
result = result + multiplier (5 + 10) = 15
multiplier <<= 1 (10 << 1) = 20
Bit 2: n & (1 << 2) = 0 (bit is not set)
multiplier <<= 1 (20 << 1) = 40
Bit 3: n & (1 << 3) = 0 (bit is not set)
multiplier <<= 1 (40 << 1) = 80
Bit 4: n & (1 << 4) = 0 (bit is not set)
multiplier <<= 1 (80 << 1) = 160
Bit 5: n & (1 << 5) = 0 (bit is not set)
multiplier <<= 1 (160 << 1) = 320
Bit 6: n & (1 << 6) = 0 (bit is not set)
multiplier <<= 1 (320 << 1) = 640
Bit 7: n & (1 << 7) = 0 (bit is not set)
multiplier <<= 1 (640 << 1) = 1280
Final Result:
result = 15 (binary 00001111)
- Lack of Hardware Multiplication: When the embedded processor does not have a hardware multiplier or the multiplication instruction is slow.
- Optimization: To optimize code for speed and size in embedded systems where resources are limited.
- Educational Purposes: To understand and implement multiplication using basic bitwise operations.
- Signal Processing: Efficiently multiplying values in digital filters or signal processing algorithms.
- Control Systems: Multiplying control parameters or sensor data in real-time systems.
- Graphics Processing: Efficiently handling operations in low-power graphics processors or microcontrollers used in display systems.