位运算+模版测试

P1001 A+B Problem

Matthew192 @ 2022-04-26 15:36:27

试一试今天新写的模版,看看能不能用。大家可以参考使用哦~

#include <bits/stdc++.h>

using namespace std;

inline namespace fastmath{
    typedef long long ll;
    typedef unsigned long long ull;
    typedef __uint128_t L;

    inline ll ABS(ll n);
    inline ll ADD(ll a, ll b);
    inline ll SUB(ll a, ll b);
    inline ll MUL(ll a, ll b);
    inline ll DIV(ll a, ll b);
    inline ll POW(ll a, ll b, ll mod);
    inline ull MOD(ull a, ull b);

    inline ll ABS(ll n){
        return (n ^ (n >> 63)) - (n >> 63);
    }

    inline ll ADD(ll a, ll b){
        if (a < 0 && b < 0){
            return -ADD(-a, -b);
        }
        if (a < 0){
            return SUB(b, -a);
        }
        if (b < 0){
            return SUB(a, -b);
        }
        while (b > 0){
            ll carry = a & b;
            a ^= b;
            b = carry << 1;
        }
        return a;
    }

    inline ll SUB(ll a, ll b){
        if (a < 0 && b < 0){
            return -SUB(-a, -b) + 1;
        }
        if (a < 0){
            return ADD(-a, b);
        }
        if (b < 0){
            return ADD(a, -b);
        }
        while (b != 0){
            ll carry = (~a) & b;
            a = a ^ b;
            b = carry << 1;
        }
        return a;
    }

    inline ll MUL(ll a, ll b){
        ll x = ABS(a), y = ABS(b), res = 0;
        bool neg = false;
        if (min(a, b) < 0 && max(a, b) >= 0){
            neg = true;
        }
        while(y > 0){
            if ((y & 1) == 1){
                res += x;
            }
            y >>= 1; x <<= 1;
        }
        if (neg){
            return (~(res) + 1);
        }
        else{
            return res;
        }
    }

    inline ll DIV(ll a, ll b){
        if (a < 0 && b < 0){
            return DIV(-a, -b);
        }
        if (a < 0){
            return -DIV(-a, b);
        }
        if (b < 0){
            return -DIV(a, -b);
        }
        int tmp = 1, res = 0;
        while (b <= a){
            b <<= 1;
            tmp <<= 1;
        }
        while (tmp > 1){
            b >>= 1;
            tmp >>= 1;
            if (a >= b){
                a -= b;
                res += tmp;
            }
        }
        return res;
    }

    inline ll POW(ll base, ll exponent, ll mod=LLONG_MAX){
        ll x = 1;
        ll y = base;
        while (exponent > 0){
            if (MOD(exponent, 2) == 1){
                x = MOD((x * y), mod);
            }
            y = MOD((y * y), mod);
            exponent >>= 1;
        }
        return MOD(x, mod);
    }

    struct FastMod{
        ull b, m;
        FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
        ull reduce(ull a) {
            ull q = (ull)((L(m) * a) >> 64);
            ull r = a - q * b;
            return r >= b ? r - b : r;
        }
    };

    FastMod F(2);

    inline ull MOD(ull a, ull b){
        F = FastMod(b);
        return F.reduce(a);
    }
}

#include <bits/stdc++.h>

using namespace std;

inline namespace FastIO{
    const int bufferSize = 1 << 15;
    inline namespace FastInput{
        // INPUT
        char inputBuffer[bufferSize]; int iPosition, iLength;

        char next_char(){
            if (iPosition == iLength){
                iPosition = 0; iLength = fread(inputBuffer, 1, bufferSize, stdin);
                if (!iLength) return EOF;
            }
            return inputBuffer[iPosition++];
        }

        void read_string(string &x){
            char ch; while(isspace(ch = next_char())){};
            do {
                x += ch;
            } while(!isspace(ch = next_char()) && ch!= '\n');
        }

        template<class T> void read_int(T &x){ // read int OR long long
            char ch; int sign = 1;
            while (!isdigit(ch = next_char())){
                if (ch == '-') sign *= -1;
            }
            x = ch - '0';
            while (isdigit(ch = next_char())){
                x = x * 10 + (ch - '0');
            }
            x *= sign;
        }

        template<class T, class... Ts> void read_int(T& t, Ts&... ts){
            read_int(t); read_int(ts...);
        }
    }
    inline namespace fastOutput{
        // OUTPUT (call initO() at start)
        char outBuffer[bufferSize], numberBuffer[100]; int outPosition;
        void flushOut(){
            fwrite(outBuffer, 1, outPosition, stdout);
            outPosition = 0;
        }

        void write_char(char c){
            if (outPosition == bufferSize){
                flushOut();
            }
            outBuffer[outPosition++] = c;
        }

        void write_string(string s){
            for (char c : s){
                write_char(c);
            }
        }

        template<class T> void write_int(T x, char after = '\0'){
            if (x < 0){
                write_char('-');
                x = x * -1;
            }
            int length = 0;
            for (; x >= 10; x /= 10){
                numberBuffer[length ++] = '0' + (x % 10);
            }
            write_char('0' + x);
            for (int i = length - 1; i >= 0; i --){
                write_char(numberBuffer[i]);
            }
            if (after){
                write_char(after);
            }
        }

        void initO(){
            assert(atexit(flushOut) == 0);
        }
    }
}

int main(){
    initO();
    int a, b;
    read_int(a, b);
    write_int(ADD(a, b), '\n');
    return 0;
}

by rxjdasiwzl @ 2022-04-26 16:26:28

@Coros_Trusds 但是他只实现了 long long 四则运算和乘方。


by Matthew192 @ 2022-04-26 16:30:24

在此说明一下:

代码是今天新打的,可(一)能(定)有BUG。

ADD(a, b) = a + b

SUB(a, b) = a - b

MUL(a, b) = a * b

DIV(a, b) = a // b

MOD(a, b) = a % b

POW(a, b) = a ^ b

POW(a, b, c) = a ^ b % c

都适用位运算实现的,所以使用负数的时候可能会出问题。

而且,说一下:虽然位运算复杂度也是O(1),但是会比正常所谓的O(1)要快。一秒钟可能只能进行2亿次加法运算,但是使用位运算可以进行约10亿次(不是我测的数据,有问题别找我)。


by Matthew192 @ 2022-04-26 16:31:40

@ud2_ 减法

SUB(a, b) = a - b


by Matthew192 @ 2022-04-26 16:33:21

@rxjdasiwzl 是的,但是普通的乘法(a*b)也是用相似的逻辑实现的,但是位运算版本可能更快。

就比如说用位运算写的的abs要比平时用的abs快12-13%


by ud2_ @ 2022-04-26 17:03:58

@Matthew192

一秒钟可能只能进行 2 亿次加法运算,但是使用位运算可以进行约 10 亿次。

不知道是哪来的数据。

本地测试结果是单次加、减、按位与、按位或、按位异或一样快,单次乘略慢,但这也只能代表一种 CPU。建议自己测试。

就比如说用位运算写的的 abs 要比平时用的 abs 快 12-13%。

同上,建议自己测试。


by rxjdasiwzl @ 2022-04-26 17:05:04

@Matthew192 请问你测试过自己的模板效率吗,你是严格多一个 log 的复杂度。还是你觉得你比写 C++ 的人更强,他们都想不到这样写代码。


by Cerisier @ 2022-04-26 17:13:33

/jy


by Matthew192 @ 2022-04-26 17:14:48

@rxjdasiwzl MOD重点测试过,因为以前在筛查指数的时候经常用到,其他的都仅供参考。


by Matthew192 @ 2022-04-26 17:15:18

@ud2_ 好的,谢谢


by PrincessQi @ 2022-04-26 17:19:18

还是你觉得你比写 C++ 的人更强,他们都想不到这样写代码。

@rxjdasiwzl 其实你这句话也有一定问题,C++ 自带的东西很多比手写慢吧。


上一页 | 下一页