论位运算优化加法是否有用

Louis_lxy · 2024-07-02 17:34:06 · 算法·理论

众所众知，位运算速度较快，那么位运算优化加法有用吗？

事实上，位运算并没有比加法多几个逻辑门，因此不一定快。但是我们还是实践出真理。

编译选项：-std=c++17 -O1 -O2 -O3。

先上数据生成器：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    freopen("1.in", "w", stdout);
    srand(time(0));
    int n;
    scanf("%d", &n);
    printf("%d\n", n);
    while (n--) printf("%lld %lld\n", 1ll * rand() * rand() * rand() * rand() * rand(), 1ll * rand() * rand() * rand() * rand() * rand());
    return 0;
}

我生成了大概 10^6 的数据，用于测试。

接下来是代码：

1、普通做法

#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(a) ((a) > 0 ? (a) : -(a))
#define swap(a, b) (a ^= b ^= a ^= b)
using namespace std;

namespace fastio
{
    char buf[1048576], *p1, *p2;
    #define getchar() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1048576, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
    inline long long read() { long long x = 0, f = 1; char c = getchar();  while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();  while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c & 15), c = getchar();  return f * x;}
    char obuf[1048576], *p3 = obuf;
    #define putchar(x) (p3 - obuf < 1048576) ? (*p3 ++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3 ++ = x)
    inline void write(long long x) { if (!x) { putchar('0'); return; }  long long len = 0, k1 = x, c[40];  if (k1 < 0)  k1 = -k1, putchar('-');  while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10;  while (len--) putchar(c[len]); }
    inline void putstring(string a) { for (char i : a) putchar(i); }
    inline void output() {fwrite(obuf, p3 - obuf, 1, stdout); p3 = obuf; }
}
using namespace fastio;

int main()
{
    int t;
    long long a, b;
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    t = read();
    while (t--)
    {
        a = read(), b = read();
        write(a + b), putchar(10);
    }
    output();
}

2、位运算优化

#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(a) ((a) > 0 ? (a) : -(a))
#define swap(a, b) (a ^= b ^= a ^= b)
using namespace std;

namespace fastio
{
    char buf[1048576], *p1, *p2;
    #define getchar() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1048576, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
    inline long long read() { long long x = 0, f = 1; char c = getchar();  while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();  while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c & 15), c = getchar();  return f * x;}
    char obuf[1048576], *p3 = obuf;
    #define putchar(x) (p3 - obuf < 1048576) ? (*p3 ++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3 ++ = x)
    inline void write(long long x) { if (!x) { putchar('0'); return; }  long long len = 0, k1 = x, c[40];  if (k1 < 0)  k1 = -k1, putchar('-');  while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10;  while (len--) putchar(c[len]); }
    inline void putstring(string a) { for (char i : a) putchar(i); }
    inline void output() {fwrite(obuf, p3 - obuf, 1, stdout); p3 = obuf; }
}
using namespace fastio;

int main()
{
    int t;
    long long a, b;
    freopen("1.in", "r", stdin);
    freopen("2.out", "w", stdout);
    t = read();
    while (t--)
    {
        a = read(), b = read();
        while (b) tie(a, b) = make_tuple(a ^ b, (a & b) << 1);
        write(a), putchar(10);
    }
    output();
}

接下来是三次测试的结果（每次间隔 1 min 保证 CPU 处于较良好的运行状态）。 |编号|普通|位运算| |-|-|-| |1|0.9341|0.982| |2|0.7488|0.7172| |3|0.7393|0.7189|

可以看到，差别并不明显，于是我们加大数据强度，让数据组数达到 2\times10^6，光是构造数据就要有 10s+ 时长。

下面是运行结果。 |编号|普通|位运算| |-|-|-| |1|1.392|1.372| |2|1.399|1.354| |3|1.414|1.412|

现在我们还是看不出结果的差异，主要是时间差距确实少。不妨位运算换个写法，不用 stl。

#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(a) ((a) > 0 ? (a) : -(a))
#define swap(a, b) (a ^= b ^= a ^= b)
using namespace std;

namespace fastio
{
    char buf[1048576], *p1, *p2;
    #define getchar() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1048576, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
    inline long long read() { long long x = 0, f = 1; char c = getchar();  while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();  while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c & 15), c = getchar();  return f * x;}
    char obuf[1048576], *p3 = obuf;
    #define putchar(x) (p3 - obuf < 1048576) ? (*p3 ++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3 ++ = x)
    inline void write(long long x) { if (!x) { putchar('0'); return; }  long long len = 0, k1 = x, c[40];  if (k1 < 0)  k1 = -k1, putchar('-');  while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10;  while (len--) putchar(c[len]); }
    inline void putstring(string a) { for (char i : a) putchar(i); }
    inline void output() {fwrite(obuf, p3 - obuf, 1, stdout); p3 = obuf; }
}
using namespace fastio;

int main()
{
    int t;
    long long a, b, x;
    freopen("1.in", "r", stdin);
    t = read();
    while (t--)
    {
        a = read(), b = read();
        while (b)
        {
            x = a;
            a = (a ^ b), b = (x & b) << 1;
        }
        write(a), putchar(10);
    }
}

结果这种做法速度并没有快。

总结，至少在我们有可能遇到的数据范围下，他们的时间差距不大，接下来是重头戏了。

我们将数据范围直接提升到 10^7，看看结果如何。这玩意输出都费劲。另外，为了得到更精准的数据，我们使用文件输出。

下面是测试结果。 |编号|普通|位运算 1|位运算 2| |-|-|-|-| |1|6.947|6.689|6.817| |2|6.883|6.678|6.663| |3|6.877|6.693|6.722|

这下我们就可以发现了，位运算确实快一点，我们再次升高数据范围，达到 10^8 进行测试。

下面是测试结果。 |编号|普通|位运算 1|位运算 2| |-|-|-|-| |1|68.89|66.41|66.86| |2|68.35|66.65|66.92| |3|68.32|66.03|66.72|

从上述测试中可以看出，确实位运算优化加法会快一点点。

总结：事实上，在 OI 中，我们是不会遇到如此大的数据量的，所以直接用普通加法即可。

接下来，我们试着卡卡这种做法，显然，如果想让循环次数尽可能得多，我们让 a=2^{60}-1，b=1 试试。

以下是数据生成器。

#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(a) ((a) > 0 ? (a) : -(a))
#define swap(a, b) (a ^= b ^= a ^= b)
using namespace std;

namespace fastio
{
    char buf[1048576], *p1, *p2;
    #define getchar() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1048576, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
    inline long long read() { long long x = 0, f = 1; char c = getchar();  while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();  while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c & 15), c = getchar();  return f * x;}
    char obuf[1048576], *p3 = obuf;
    #define putchar(x) (p3 - obuf < 1048576) ? (*p3 ++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3 ++ = x)
    inline void write(long long x) { if (!x) { putchar('0'); return; }  long long len = 0, k1 = x, c[40];  if (k1 < 0)  k1 = -k1, putchar('-');  while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10;  while (len--) putchar(c[len]); }
    inline void putstring(string a) { for (char i : a) putchar(i); }
    inline void output() {fwrite(obuf, p3 - obuf, 1, stdout); p3 = obuf; }
}
using namespace fastio;

int main()
{
    freopen("1.in", "w", stdout);
    srand(time(0));
    int n;
    scanf("%d", &n);
    printf("%d\n", n);
    while (n--) write((1ll << 60) - 1), putchar(32), write(1ll), putchar(10);
    output();
    return 0;
}

以下是测试结果。 |编号|普通|位运算 1|位运算 2| |-|-|-|-| |1|55.8|74.04|74.12| |2|56.8|71.98|72.2| |3|55.6|71.68|72.45|

显然，如果我们这样构造，会加快普通加法，减慢位运算优化后的。

再次总结：位运算优化后的加法在随机数据下比较快，在构造数据下可以被卡的很慢。

有人说可能是 O1 O2 O3 优化的锅？那我们就试试不开的结果。

编译选项：-std=c++17。

测试结果就不放了，普通加法吊打位运算优化，用 stl 位运算优化几分钟都没跑出来，不用的也比普通加法慢一点。感觉有可能是 stl 的锅。

下面是不用 stl 的另一种版本。

#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define abs(a) ((a) > 0 ? (a) : -(a))
#define swap(a, b) (a ^= b ^= a ^= b)
using namespace std;

namespace fastio
{
    char buf[1048576], *p1, *p2;
    #define getchar() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1048576, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
    inline long long read() { long long x = 0, f = 1; char c = getchar();  while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();  while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c & 15), c = getchar();  return f * x;}
    char obuf[1048576], *p3 = obuf;
    #define putchar(x) (p3 - obuf < 1048576) ? (*p3 ++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3 ++ = x)
    inline void write(long long x) { if (!x) { putchar('0'); return; }  long long len = 0, k1 = x, c[40];  if (k1 < 0)  k1 = -k1, putchar('-');  while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10;  while (len--) putchar(c[len]); }
    inline void putstring(string a) { for (char i : a) putchar(i); }
    inline void output() {fwrite(obuf, p3 - obuf, 1, stdout); p3 = obuf; }
}
using namespace fastio;

struct k { long long a, b; } x;

int main()
{
    int t;
    freopen("1.in", "r", stdin);
    freopen("2.out", "w", stdout);
    t = read();
    while (t--)
    {
        x.a = read(), x.b = read();
        while (x.b) x = k {x.a ^ x.b, (x.a & x.b) << 1};
        write(x.a), putchar(10);
    }
    output();
}

但是实测后与另一种不用 stl 的差距不大。

最后总结：位运算优化加法并没有什么用处。