使用位运算符(AND,OR,XOR,<<,>>)仅通过位运算来计算两个数字的乘积是完全可行的,尽管可能不是非常高效。您可能想阅读相关的维基百科文章
Adder (electronics)和
Binary multiplier。
一种自下而上的乘法方法是先创建一个二进制加法器。对于最低位(位0),
half adder可以很好地工作。S表示总和,C表示进位。
![Half adder](https://upload.wikimedia.org/wikipedia/commons/d/d9/Half_Adder.svg)
对于剩余的位,每个位都需要一个全加器。Cin表示“进位”,Cout表示“进位输出”:
![Full adder](https://upload.wikimedia.org/wikipedia/commons/thumb/6/69/Full-adder_logic_diagram.svg/400px-Full-adder_logic_diagram.svg.png)
将多个比特位相加的最简单逻辑电路称为串行进位加法器:
![Ripple-carry adder](https://upload.wikimedia.org/wikipedia/commons/thumb/5/5d/4-bit_ripple_carry_adder.svg/500px-4-bit_ripple_carry_adder.svg.png)
Ripple-carry加法器基本上是一系列全加器,进位被传递给计算下一个更高有效位的全加器。虽然存在其他更高效的方法,但由于简单起见,我将跳过它们。现在我们有了一个二进制加法器。
二进制乘法器是一个更难的情况。但是由于我认为这更多是一个概念的证明而不是实际乘两个数字的实用方式,所以让我们走一条更简单的路线。
假设我们想要计算
a
和
b
的乘积,
a = 100
,
b = 5
。
a
和
b
都是16位无符号整数(也可以是定点数)。我们可以创建一个求和数组,在其中写入
a
(100)
b
(5)次的值,或反之亦然。由于在16位中可表示的最高无符号值为2^16-1(65535),我们希望创建一个大小为65535的无符号整数数组,并填充零。然后,我们需要使用位运算将数组的某5个值设置为100。
我们可以这样做:首先,我们用值为100的a填充一个数组(称其为a_array)。然后,我们想要根据b的值将a_array中的一些值清零,使得a_array的b个值保持不变,其余值都被清零。为此,我们使用一个二进制掩码和AND位运算。
所以我们循环遍历b的比特位。对于b的每一位,我们根据b中该位的值创建一个二进制掩码。创建这样的二进制掩码只需要进行位移(<<,>>)位运算,按位AND和按位OR。
0 -> 0b0000 0000 0000 0000
1 -> 0b1111 1111 1111 1111
所以,现在我们有了一个二进制掩码。但是我们如何使用它呢?嗯,
b
的第 0 位对应着数字值 0 或 1。
b
的第 1 位对应着数字值 0 或 2。
b
的第 2 位对应着数字值 0 或 4。因此,
b
的第 n 位对应着数字值 0 或 2^n。所以,当我们遍历
b
的每一位并为每一位创建一个二进制掩码时,我们将
a_array
的 2^n 值与相应的二进制掩码进行
AND
运算。
a_array
中对应的值可能会被清零或不变。在 C 代码中,我使用
for
循环通过递增和递减计数器进行
AND
运算。递增和递减
不是位运算。但是
for
循环并不是必需的,它仅用于可读性(从人类角度来看)。实际上,我首先在 x86-64 汇编语言中编写了一个 4 位 * 4 位 = 4 位乘法器来尝试这个概念,只使用
and
、
or
、
xor
、
shl
(左移位)和
shr
(右移位)以及
call
。
call
是函数或过程调用,也就是说,
不是位运算,但是您可以内联所有这些函数或程序,并使用只有
AND
、
OR
、
XOR
、
<<
和
>>
的方法计算乘积。因此,对于
b
的每一位,您可以使用基于相应的
b
位的位掩码的按位掩码来
AND
n(n = 1、2、4、8...)个对应的
a_array
值。对于一个 16 位 * 16 位 = 16 位乘法,需要 65535 条
AND
命令(没有循环)。计算机处理此类输入没有问题,但人们往往无法阅读此类代码。出于这个原因,使用
for
循环。
现在我们有一个由
b
个
a
值填充而成的
a_array
数组,其余为零。剩下的很简单:我们只需要使用位加器(即下面C代码中的函数
my_add
)将
a_array
的所有值相加。
这是16位* 16位= 16位无符号整数乘法的代码。请注意,函数memset16
假设小端架构。将memset16
转换为大端架构应该很容易。此代码也适用于定点乘法,您只需要在结尾处添加位移。转换为不同的变量大小以及实现溢出检测也应该很容易。任务留给读者。使用GCC编译,在x86-64 Linux上进行了测试。
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#define NUMBER_OF_BITS 16
#define MAX_VALUE 65535
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef struct result_struct{
u16 result;
u16 carry;
} result_struct;
u16 extend_lowest_bit(u16 a)
{
u16 a_extended;
a = (a & 1);
a_extended = a | (a << 1) | (a << 2) | (a << 3) | (a << 4);
a_extended = a_extended | (a << 5) | (a << 6) | (a << 7) | (a << 8);
a_extended = a_extended | (a << 9) | (a << 10) | (a << 11) | (a << 12);
a_extended = a_extended | (a << 13) | (a << 14) | (a << 15);
return a_extended;
}
result_struct my_add(u16 a, u16 b)
{
result_struct add_results;
u16 a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15;
u16 b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13, b14, b15;
u16 carry, result = 0;
a0 = a & 1;
a1 = a & (1 << 1);
a2 = a & (1 << 2);
a3 = a & (1 << 3);
a4 = a & (1 << 4);
a5 = a & (1 << 5);
a6 = a & (1 << 6);
a7 = a & (1 << 7);
a8 = a & (1 << 8);
a9 = a & (1 << 9);
a10 = a & (1 << 10);
a11 = a & (1 << 11);
a12 = a & (1 << 12);
a13 = a & (1 << 13);
a14 = a & (1 << 14);
a15 = a & (1 << 15);
b0 = b & 1;
b1 = b & (1 << 1);
b2 = b & (1 << 2);
b3 = b & (1 << 3);
b4 = b & (1 << 4);
b5 = b & (1 << 5);
b6 = b & (1 << 6);
b7 = b & (1 << 7);
b8 = b & (1 << 8);
b9 = b & (1 << 9);
b10 = b & (1 << 10);
b11 = b & (1 << 11);
b12 = b & (1 << 12);
b13 = b & (1 << 13);
b14 = b & (1 << 14);
b15 = b & (1 << 15);
add_results.result = a0 ^ b0;
carry = (a0 & b0) << 1;
add_results.result = add_results.result | (a1 ^ b1 ^ carry);
carry = ((carry & (a1 ^ b1)) | (a1 & b1)) << 1;
add_results.result = add_results.result | (a2 ^ b2 ^ carry);
carry = ((carry & (a2 ^ b2)) | (a2 & b2)) << 1;
add_results.result = add_results.result | (a3 ^ b3 ^ carry);
carry = ((carry & (a3 ^ b3)) | (a3 & b3)) << 1;
add_results.result = add_results.result | (a4 ^ b4 ^ carry);
carry = ((carry & (a4 ^ b4)) | (a4 & b4)) << 1;
add_results.result = add_results.result | (a5 ^ b5 ^ carry);
carry = ((carry & (a5 ^ b5)) | (a5 & b5)) << 1;
add_results.result = add_results.result | (a6 ^ b6 ^ carry);
carry = ((carry & (a6 ^ b6)) | (a6 & b6)) << 1;
add_results.result = add_results.result | (a7 ^ b7 ^ carry);
carry = ((carry & (a7 ^ b7)) | (a7 & b7)) << 1;
add_results.result = add_results.result | (a8 ^ b8 ^ carry);
carry = ((carry & (a8 ^ b8)) | (a8 & b8)) << 1;
add_results.result = add_results.result | (a9 ^ b9 ^ carry);
carry = ((carry & (a9 ^ b9)) | (a9 & b9)) << 1;
add_results.result = add_results.result | (a10 ^ b10 ^ carry);
carry = ((carry & (a10 ^ b10)) | (a10 & b10)) << 1;
add_results.result = add_results.result | (a11 ^ b11 ^ carry);
carry = ((carry & (a11 ^ b11)) | (a11 & b11)) << 1;
add_results.result = add_results.result | (a12 ^ b12 ^ carry);
carry = ((carry & (a12 ^ b12)) | (a12 & b12)) << 1;
add_results.result = add_results.result | (a13 ^ b13 ^ carry);
carry = ((carry & (a13 ^ b13)) | (a13 & b13)) << 1;
add_results.result = add_results.result | (a14 ^ b14 ^ carry);
carry = ((carry & (a14 ^ b14)) | (a14 & b14)) << 1;
add_results.result = add_results.result | (a15 ^ b15 ^ carry);
add_results.carry = ((carry & (a15 ^ b15)) | (a15 & b15)) << 1;
return add_results;
}
result_struct add_array(void* array, s32 size)
{
result_struct add_results;
u16* i;
u16* top_address;
add_results.result = 0;
add_results.carry = 0;
for (i = array; i < ((u16*)array + size); i++)
{
add_results = my_add(add_results.result, *i);
}
return add_results;
}
void memset16(void* dest, u16 value, s32 size)
{
u8* i;
for (i = (u8*)dest; i < ((u8*)dest+(2*size)); i+=2)
{
memset(i, (int)(value & 0xff), 1);
memset(i+1, (int)(value >> 8), 1);
}
}
result_struct my_mul(u16 a, u16 b)
{
u16 bitmask, a_array[MAX_VALUE];
u32 block_length;
s16 bit_i;
s32 count, size;
u16* i;
void* p_a_array;
p_a_array = a_array;
result_struct mul_results;
mul_results.result = 0;
size = MAX_VALUE;
memset16(p_a_array, a, size);
i = p_a_array;
for (bit_i = 0, block_length = 1; bit_i < NUMBER_OF_BITS; bit_i++)
{
bitmask = extend_lowest_bit(b >> bit_i);
for (count = block_length; count > 0; count--)
{
*i = (*i & bitmask);
i++;
}
block_length <<= 1;
}
mul_results = add_array(p_a_array, MAX_VALUE);
return mul_results;
}
int main(void)
{
int a, b;
result_struct multiply_results;
printf("Enter the 1st unsigned 16-bit integer.\n");
scanf("%d", &a);
printf("Enter the 2nd unsigned 16-bit integer.\n");
scanf("%d", &b);
multiply_results = my_mul((u16)a, (u16)b);
printf("%d * %d = %d\n", a, b, multiply_results.result);
return 0;
}
(float)x / (1 << 7)
吗? - Oliver Charlesworth