位运算 复习

算法基础课

算法基础课 AcWing 801.二进制中1的个数

#include <iostream>

using namespace std;

int get_1(int x)
{
    int res = 0;
    while (x)
    {
        if (x & 1) res++;
        x >>= 1;
    }
    return res;
}

int main()
{
    int n; cin >> n;
    while (n--)
    {
        int x; cin >> x;
        cout << get_1(x) << ' ';
    }
    return 0;
}

算法竞赛入门经典

算法竞赛入门经典 AcWing 89.a^b

#include <iostream>

using namespace std;

int qmi(int a, int k, int p)
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (long long)res * a % p;
        a = (long long)a * a % p;
        k >>= 1;
    }
    return res;
}

int main()
{
    int a, b, p;

    cin >> a >> b >> p;

    cout << qmi(a, b, p) << endl;

    return 0;
}

算法竞赛入门经典 AcWing 5579.增加模数

算法竞赛入门经典 AcWing 90.64位整数乘法

#include <iostream>

using namespace std;

typedef long long ll;

ll mul(ll a, ll b, ll p)
{
    ll res = 0;
    while (b)
    {
        if (b & 1) res = (res + a) % p;
        a = a * 2 % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    ll a, b, p;

    cin >> a >> b >> p;

    cout << mul(a, b, p) << endl;

    return 0;
}

算法竞赛入门经典 AcWing 91.最短Hamilton路径

算法竞赛入门经典 AcWing 998.起床困难综合症