通过位操作实现四则运算

BitTigerio

2018-02-13

在最早学习四则运算的过程中，我们其实就已经掌握了进制算法，这一次我将对二进制运用这个进制算法来实现四则运算。

四则运算

math.c

/**
 * 功能：通过位操作实现四则运算
 * 算法：完全参照十进制的进制算法
 *
 * Created with CLion
 * User: zzzz76
 * Date: 2018-02-10
 */

#include <stdio.h>
#include <assert.h>
#include "math.h"

/**
 * 加法：往上递归实现
 *
 * @param a
 * @param b
 * @return
 */
int base_add(int a, int b) {
    /* 值在函数中的传递只能通过参数或者返回操作，所以递归效果无非是体现在参数和返回操作上 */
    if (b == 0) {
        return a;
    }
    int save = a ^b;
    int promote = (a & b) << 1;
    return base_add(save, promote);
}

/**
 * 加法：迭代实现
 *
 * @param a
 * @param b
 * @return
 */
int base_add_re(int a, int b) {
    while (a && b) {
        int promote = (a & b) << 1;
        a = a ^ b;
        b = promote;
    }
    return a ^ b;
}

/**
 * 减法：往上递归实现
 *
 * @param a
 * @param b
 * @return
 */
int base_sub(int a, int b) {
    if (b == 0) {
        return a;
    }
    int save = a ^ b;
    int reduce = ((~a) & b) << 1;
    return base_sub(save, reduce);
}

/**
 * 减法：迭代实现
 *
 * @param a
 * @param b
 * @return
 */
int base_sub_re(int a, int b) {
    while(b) {
        int save = a ^ b;
        b = ((~a) & b) << 1;
        a = save;
    }
    return a;
}

/**
 * 减法：补位实现
 *
 * @param a
 * @param b
 * @return
 */
int base_sub_re_re(int a, int b) {
    return base_add(a, base_add(~b, 1));
}

/**
 * 乘法：递归实现
 *
 * @param a
 * @param b
 * @return
 */
int base_mul(int a, int b) {
    int count = 0;
    if (a == 0) {
        return count;
    }
    if (a & 1) {
        count = base_add(count, b);
    }
    a = (unsigned)a >> 1;
    b <<= 1;
    count = base_add(count, base_mul(a, b));
    return count;
}

/**
 * 乘法：迭代实现
 *
 * @param a
 * @param b
 * @return
 */
int base_mul_re(int a, int b) {
    int count = 0;
    while (a) {
        if (a & 1) {
            count = base_add(count, b);
        }
        a = (unsigned)a >> 1;
        b <<= 1;
    }
    return count;
}

/**
 * 除法：迭代实现
 *
 * @param a
 * @param b
 * @return
 */
int base_div(int a, int b) {
    assert(b);
    int result = 0;
    int bit_num = 31;
    while (bit_num != -1) {
        if (b <= ((unsigned) a >> bit_num)) {
            result = base_add(result, 1 << bit_num);
            a = base_sub(a, b << bit_num);
        }
        bit_num = base_sub(bit_num, 1);
    }
    return result;
}

/**
 * 除法：递归实现
 *
 * @param a
 * @param b
 * @return
 */
int base_div_re(int a, int b) {
    assert(b);
    if (a < (unsigned) b) {
        return 0;
    }
    int bit_num = 0;
    while (b <= (unsigned) a >> 1 >> bit_num) {
        bit_num = base_add(bit_num, 1);
    }
    int result = 1 << bit_num;
    a = base_sub(a, b << bit_num);
    result = base_add(result, base_div_re(a, b));
    return result;
}

math.h

/**
 * Created with CLion
 * User: zzzz76
 * Date: 2018-02-12
 */

#ifndef MATH_H
#define MATH_H

int base_add(int a, int b);
int base_add_re(int a, int b);

int base_sub(int a, int b);
int base_sub_re(int a, int b);
int base_sub_re_re(int a, int b);

int base_mul(int a, int b);
int base_mul_re(int a, int b);

int base_div(int a, int b);
int base_div_re(int a, int b);

#endif //MATH_H

test.c

/**
 * Created with CLion
 * User: zzzz76
 * Date: 2018-02-12
 */

#include "math.h"
#include <stdio.h>

static int main_ret = 0;
static int test_count = 0;
static int test_pass = 0;

#define EXPECT_EQ_BASE(expect, actual, format) \
    do {\
        test_count++;\
        if ((expect) == (actual)) {\
            test_pass++;\
        } else {\
            fprintf(stderr, "%s:%d: expect: " format " actual: " format "\n", __FILE__, __LINE__, expect, actual);\
            main_ret = 1;\
        }\
    } while(0);

#define EXPECT_EQ_INT(expect, actual) EXPECT_EQ_BASE(expect, actual, "%d");

#define TEST_BASE_ADD(expect, a, b) \
    EXPECT_EQ_INT(expect, base_add(a, b));\
    EXPECT_EQ_INT(expect, base_add_re(a, b));
static void test_base_add() {
    TEST_BASE_ADD(2, 1, 1);
    TEST_BASE_ADD(0, -1, 1);
    TEST_BASE_ADD(0, 1, -1);
    TEST_BASE_ADD(-2, -1, -1);
    TEST_BASE_ADD(-2147483648, 2147483647, 1);
}

#define TEST_BASE_SUB(expect, a, b) \
    EXPECT_EQ_INT(expect, base_sub(a, b));\
    EXPECT_EQ_INT(expect, base_sub_re(a, b));\
    EXPECT_EQ_INT(expect, base_sub_re_re(a, b));
static void test_base_sub() {
    TEST_BASE_SUB(0, 1, 1);
    TEST_BASE_SUB(-2, -1, 1);
    TEST_BASE_SUB(2, 1, -1);
    TEST_BASE_SUB(0, -1, -1);
    TEST_BASE_SUB(2147483647, -2147483648, 1);
}

#define TEST_BASE_MUL(expect, a, b) \
    EXPECT_EQ_INT(expect, base_mul(a, b));\
    EXPECT_EQ_INT(expect, base_mul_re(a, b));
static void test_base_mul() {
    TEST_BASE_MUL(9, 3, 3);
    TEST_BASE_MUL(-9, -3, 3);
    TEST_BASE_MUL(-9, 3, -3);
    TEST_BASE_MUL(9, -3, -3);
    TEST_BASE_MUL(0, -2147483648, 2);
    TEST_BASE_MUL(-2, 2147483647, 2);
}

#define TEST_BASE_DIV(expect, a, b) \
    EXPECT_EQ_INT(expect, base_div(a, b));\
    EXPECT_EQ_INT(expect, base_div_re(a, b));
static void test_base_div() {
    TEST_BASE_DIV(2, 2, 1);
    TEST_BASE_DIV(-2, -2, 1);
    TEST_BASE_DIV(0, 2, -1);
    TEST_BASE_DIV(0, -2, -1);
    TEST_BASE_DIV(0, 1, 2);
    TEST_BASE_DIV(0, 1, -2);
    TEST_BASE_DIV(2147483647, -1, 2);
    TEST_BASE_DIV(1, -1, -2);
}

static void test_base() {
    test_base_add();
    test_base_sub();
    test_base_mul();
    test_base_div();
}

int main() {
    test_base();
    printf("%d/%d (%3.2f%%) passed\n", test_pass, test_count, test_pass * 100.0 / test_count);
    return main_ret;
}