使用按位运算符相乘

我想知道如何使用按位运算符将一系列二进制位相乘。但是，我有兴趣这样做来查找二进制值的十进制小数值。这是我正在尝试做的一个例子：

假设：1010010，

我想使用每个单独的位，以便将其计算为：

1*(2^-1) + 0*(2^-2) + 1*(2^-3) + 0*(2^-4).....

虽然我对在 ARM 汇编中执行此操作感兴趣，但在 C/C++ 中提供示例仍然会有所帮助。

我正在考虑使用计数器执行循环，每次循环迭代时，计数器都会递增，该值将逻辑左移，以便获取第一位，并乘以 2^-计数器。

然而，我并不完全确定如何仅让第一位/MSB 相乘，而且我很困惑如何将该值乘以基数 2 得到某个负幂。

我知道逻辑左移会将其乘以基数 2，但它们通常具有正指数。前任。 LSL r0, 2 表示 r0 中的值将乘以 2^2 = 4。

提前致谢！

仅使用按位运算将两个数字相乘 (AND, OR, XOR, <<, >>）是完全可能的，尽管可能不是很有效。您可能想阅读相关的维基百科文章加法器（电子） http://en.wikipedia.org/wiki/Adder_(electronics) and 二进制乘法器 http://en.wikipedia.org/wiki/Binary_multiplier.

自下而上的乘法方法是首先创建一个二进制加法器。对于最低位（位 0）a半加器 http://en.wikipedia.org/wiki/Adder_%28electronics%29#Half_adder工作正常。 S表示和，C表示进位。

对于其余的部分，您需要全加器 http://en.wikipedia.org/wiki/Adder_%28electronics%29#Full_adder对于每一位。 Cin 的意思是“带入”，Cout 的意思是“执行”：

对几个位求和的最简单的逻辑电路称为纹波进位加法器 http://en.wikipedia.org/wiki/Adder_(electronics)#Ripple-carry_adder:

纹波进位加法器基本上是一系列全加器，进位被传播到全加器计算下一个更高的有效位。确实存在其他更有效的方法，但由于简单的原因，我跳过它们。现在我们有了一个二进制加法器。

二进制乘法器是一个更困难的情况。但由于我认为这更多的是概念证明，而不是两个数字相乘的实用方法，所以让我们走一个更简单的弯路。

假设我们要计算的乘积a and b, a = 100, b = 5. a and b都是 16 位无符号整数（也可以是定点）。我们可以创建一个被加数数组，在其中写入值a (100) b(5) 次，反之亦然。由于 16 位可表示的最高无符号值是 2^16-1 (65535)，因此我们希望创建一个由 65535 个无符号整数组成的数组，并用零填充。然后我们需要仅使用按位运算将数组中的 5 个值设置为 100。

我们可以这样做：首先我们填充一个数组（我们称之为a_array) 的值为a（100）。然后我们想要将一些值归零a_array基于的价值b， 以便b的值a_array保持不变，其余值a_array被归零。为此，我们使用二进制掩码和AND按位运算。

所以我们循环遍历这些位b。对于每一位b我们根据该位的值创建一个二进制掩码b。创建这样的二进制掩码只需要位移位（<<, >>)，按位AND和按位OR.

0 -> 0b0000 0000 0000 0000
1 -> 0b1111 1111 1111 1111
  

所以，现在我们有了一个二进制掩码。但我们如何使用它呢？好吧，位 0b对应数值0或1。位1b对应数值0或2。位2b对应于数值 0 或 4。所以位 nb对应于0或2^n的数值。所以，当我们循环遍历这些位时b并为每个位创建一个二进制掩码，我们AND2^n 个值a_array与相应的二进制掩码。对应的值在a_array要么归零，要么保持不变。在C代码中我使用for循环AND通过a_array，以及递增和递减计数器。增量和减量分别是not一个按位运算。但是for循环不是必需的，它仅用于可读性（从人类的角度来看）。实际上，我首先在 x86-64 程序集中编写了一个 4 位 * 4 位 = 4 位乘法器来尝试这个概念，仅使用and, or, xor, shl（左移位），以及shr（右移一位）和call. call是函数或过程调用，即not按位运算，但您可以内联所有这些函数或过程，从而仅使用AND, OR, XOR, << and >>。所以而不是for循环，对于每一位b， 你可以ANDn (n = 1, 2, 4, 8 ...) 的对应值a_array使用基于相应位的按位掩码b。对于 16 位 * 16 位 = 16 位乘法，需要 65535AND命令（无循环）。计算机对这样的输入没有问题，但人类在阅读这样的代码时往往会遇到问题。由于这个原因for使用循环。

现在我们有a_array洋溢着b的值a，其余为零。剩下的很简单：我们只需将所有值相加a_array使用按位加法器（这是函数my_add在下面的 C 代码中）。

这是 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)
{
    /* extends lowest bit (bit 0) to all bits. */
    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)
{
    /* computes (a + 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;
    /* prepare for bitwise addition by separating
     * each bit of summands a and b using bitwise AND. */
    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;
    /* result: 0000 0000 0000 000x */
    carry = (a0 & b0) << 1;
    add_results.result = add_results.result | (a1 ^ b1 ^ carry);
    /* result: 0000 0000 0000 00xx */
    carry = ((carry & (a1 ^ b1)) | (a1 & b1)) << 1;
    add_results.result = add_results.result | (a2 ^ b2 ^ carry);
    /* result: 0000 0000 0000 0xxx */
    carry = ((carry & (a2 ^ b2)) | (a2 & b2)) << 1;
    add_results.result = add_results.result | (a3 ^ b3 ^ carry);
    /* result: 0000 0000 0000 xxxx */
    carry = ((carry & (a3 ^ b3)) | (a3 & b3)) << 1;
    add_results.result = add_results.result | (a4 ^ b4 ^ carry);
    /* result: 0000 0000 000x xxxx */
    carry = ((carry & (a4 ^ b4)) | (a4 & b4)) << 1;
    add_results.result = add_results.result | (a5 ^ b5 ^ carry);
    /* result: 0000 0000 00xx xxxx */
    carry = ((carry & (a5 ^ b5)) | (a5 & b5)) << 1;
    add_results.result = add_results.result | (a6 ^ b6 ^ carry);
    /* result: 0000 0000 0xxx xxxx */
    carry = ((carry & (a6 ^ b6)) | (a6 & b6)) << 1;
    add_results.result = add_results.result | (a7 ^ b7 ^ carry);
    /* result: 0000 0000 xxxx xxxx */
    carry = ((carry & (a7 ^ b7)) | (a7 & b7)) << 1;
    add_results.result = add_results.result | (a8 ^ b8 ^ carry);
    /* result: 0000 000x xxxx xxxx */
    carry = ((carry & (a8 ^ b8)) | (a8 & b8)) << 1;
    add_results.result = add_results.result | (a9 ^ b9 ^ carry);
    /* result: 0000 00xx xxxx xxxx */
    carry = ((carry & (a9 ^ b9)) | (a9 & b9)) << 1;
    add_results.result = add_results.result | (a10 ^ b10 ^ carry);
    /* result: 0000 0xxx xxxx xxxx */
    carry = ((carry & (a10 ^ b10)) | (a10 & b10)) << 1;
    add_results.result = add_results.result | (a11 ^ b11 ^ carry);
    /* result: 0000 xxxx xxxx xxxx */
    carry = ((carry & (a11 ^ b11)) | (a11 & b11)) << 1;
    add_results.result = add_results.result | (a12 ^ b12 ^ carry);
    /* result: 000x xxxx xxxx xxxx */
    carry = ((carry & (a12 ^ b12)) | (a12 & b12)) << 1;
    add_results.result = add_results.result | (a13 ^ b13 ^ carry);
    /* result: 00xx xxxx xxxx xxxx */
    carry = ((carry & (a13 ^ b13)) | (a13 & b13)) << 1;
    add_results.result = add_results.result | (a14 ^ b14 ^ carry);
    /* result: 0xxx xxxx xxxx xxxx */
    carry = ((carry & (a14 ^ b14)) | (a14 & b14)) << 1;
    add_results.result = add_results.result | (a15 ^ b15 ^ carry);
    /* result: xxxx xxxx xxxx xxxx */
    add_results.carry = ((carry & (a15 ^ b15)) | (a15 & b15)) << 1;
    return add_results;
}

result_struct add_array(void* array, s32 size)
{
    /* adds together all u16 values of the array. */
    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)
{
    /* does a 16-bit memset. size is the number of u16's (words). */
    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)
{
    /* computes (a * 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);   // can be replaced with AND.

    /* mask the summands. can be unrolled to
     * use only bitwise operations. */
    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;
    }
    /* the array of summands is now masked. */

    /* add the values of the array together. */
    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;
}