HNFMS一个初二蒟蒻OIerの实验室

说说C++中的位运算与四则运算

C++中的位运算符

  1. 位逻辑运算符:
    &(位 “与”)可写成and

^(位 “异或”)
|(位 “或”)可写成or
~(位 “取反”)

  1. 移位运算符:
    <<(左移)

>>(右移)

用位运算实现四则运算

加法

0111 ^ 0101 = 0010; //结果的每一位等于对应位相加模二,刚好是不带进位的加法结果
0111 & 0101 = 0101; //结果的1表示对应位相加为2,0表示对应位相加小于二,刚好是进位标识

于是有代码

int add(int a, int b)
{
    return (b == 0) ? a : add(a^b, (a&b) << 1);
}

减法

减法其实就是加上这个数的相反数,这个数原来是用正数的补码表示的,现在变成负数的补码形式了,所以只需要将这个数每一位取反再末尾加一就行了:

int subtraction(int a, int b)
{
    b = add(~b, 1);
    return add(a, b);
}

乘法

对于a * b,每次只需要将a左移一位乘上b的对应位,然后同上一次的结果做加法即可。
当b的对应位为1时,对a左移一位然后同上一次的结果做加法;如果b的对应位为0,只对a左移一位。

int getsign(int n)
{
    return n >> 31;
}

int positive(int n)
{
    return (getsign(n) & 1) ? add(~n,1): n;
}

int multiply(int a, int b)
{
    bool flag = (getsign(a) ^ getsign(b)) ? 1 : 0;
    a = positive(a);
    b = positive(b);

    int res = 0;
    while (b) {
        if (b & 1)
            res = add(res, a);   //只有当前b末尾为1时才运算
        a = a << 1;  
        b = b >> 1;
    }
    if (flag)
        add(~res, 1);

    return res;
}

除法

int add(int a, int b)
{
    return (b == 0) ? a : add(a^b, (a&b) << 1);
}

int subtraction(int a, int b)
{
    b = add(~b, 1);
    return add(a, b);
}

int getsign(int n)
{
    return n >> 31;
}

int positive(int n)
{
    return (getsign(n) & 1) ? add(~n,1): n;
}

int multiply(int a, int b)
{
    bool flag = (getsign(a) ^ getsign(b)) ? 1 : 0;
    a = positive(a);
    b = positive(b);

    int res = 0;
    while (b) {
        if (b & 1)
            res = add(res, a);   //只有当前b末尾为1时才运算
        a = a << 1;  
        b = b >> 1;
    }
    if (flag)
        add(~res, 1);

    return res;
}

int divide(int a, int b)
{
    if (b == 0)
        throw runtime_error("DIVIDED CANNOT BE 0");

    bool flag = (getsign(a) ^ getsign(b)) ? 1 : 0;
    a = positive(a);
    b = positive(b);

    int res = 0;
    while (a >= b)
    {
        res = add(res, 1);
        a = subtraction(a, b);
    }
    return flag ? add(~res, 1) : res;
}

本文转自http://www.mamicode.com/info-detail-2495269.html,因为做题需要了解位运算,所以就顺便转了...

标签: 位运算

Title - Artist
0:00