0x01 位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1<<20;
int h[N+1];
int main(){
	int n;
	for(int i=0;i<=20;i++) h[1<<i] = i;
	while(cin>>n){  //对多次询问进行求解
		while(n>0){
			cout<<h[n&-n]<<" ";
			n-=n&-n;
		}
	}
	cout<<endl;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<algorithm>
using namespace std;
int h[37];
int main(){
    int n;
    for(int i=0;i<36;i++) h[(1ll<<i)%37] = i;
    while(cin>>n){
        while(n>0){
            cout<<h[(n&-n)%37]<<" ";
            n-=n&-n;
        }
        cout<<endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int x ,count;
		cin>>x;
		count = 0;
		while(x){
			if(x&1) count++;
			x=x>>1;
		}
		cout<<count<<" ";
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	while(n--){
		int x,count;
		cin>>x;
		count = 0;
		for(int i=x;i;i-=i&-i) count++;
		cout<<count<<" ";
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a,b,p,sum;
	cin>>a>>b>>p;
	sum = 1%p; //当a,0,p时,当b=0时,
	while(b){
		//先将b的最低位提取出来,如果是1, 就将结束乘a^(b&1)
		if(b&1) sum = 1ll*sum*a%p;   //乘1ll是为了防止溢出int的范围.
		a = 1ll *a*a%p;  //最低位的a是a^1  次最低位 a 是a^2  再次最低位 a 是a^4  依次类推,所以累乘.
		b=b>>1;   //将最低位抹去
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	long long a,b,p,sum;
	cin>>a>>b>>p;
	sum = 0;
	while(b){
		if(b&1) sum = (sum+a)%p;
		a =a*2%p;  //a最大是18位十进制数,而long long最大可以表示19位十进制数,所以不会越界.
		b>>=1;
	}
	cout<<sum<<endl;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	long long a,b,p,sum;
	cin>>a>>b>>p;
	sum = 0;
	a = a%p;b = b%p;
	long long c = (long double) a*b/p;
	sum =a*b-c*p;
	if(sum<0) sum+=p;
	else if(sum>=p) sum-=p;
	cout<<sum<<endl; 
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N =20;
const int M  = 1<<N;
int w[N][N];
int f[M][N];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>w[i][j];
    memset(f,0x3f,sizeof(f));
    f[1][0] =0;  //即只经过点0，目前处于起点0，最短路长度为0
    for(int i=1;i<1<<n;i++)  //n位二进制，有2^n种状态，一次一次遍历
        for(int j=0;j<n;j++)
            if(i>>j&1)  //当i的第j位为1， 即当前走到了j这个点。
                for(int k=0;k<n;k++)
                    if((i^1<<j)>>k&1)  //我们就去掉这个j这个点，然后遍历K，如果K为1，则说明可以从k点到j点，
                        f[i][j] = min(f[i][j],f[i^1<<j][k]+w[k][j]);  //判断是从K点到j点的距离小，还是直接到小，选择一个最小的值。
    cout<<f[(1<<n)-1][n-1]<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <string.h>
const int N = 20;
const int M = 1 << N;
int n;
int w[N][N];
int f[M][N];
int log_2[M >> 1]; // 存 1 到 M / 2 中，所有 2 的整次幂的数以 2 为底的对数

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            scanf("%d", &w[i][j]);

    for (int i = 0; i < 20; i ++ ) // 预处理 log_2
        log_2[1 << i] = i;

    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for (int state = 1; state < 1 << n; state ++ )
        if (state & 1)
            for (int t = state; t; t &= t - 1)     // 只枚举 state 所包含的点集
            {
                int j = log_2[t & -t];             // 将集合 t 中最小的点取出
                for (int u = state ^ t & -t; u; u &= u - 1) // 只枚举 state 中去掉点 j 的点集
                {
                    int k = log_2[u & -u];         // 将集合 u 中最小的点取出
                    if (f[state ^ t & -t][k] + w[k][j] < f[state][j])
                        f[state][j] = f[state ^ t & -t][k] + w[k][j];
                }
            }

    printf("%dn", f[(1 << n) - 1][n - 1]);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<algorithm>
using namespace std;
const int N  =100010;
int n,m;
int t[N];  //用来存储输入的n个数
int op[N]; //用来存储输入的n个数的相应的运算符
char str[4];  //用来暂时存放输入的运算符
int calc(int bit,int now){
    for(int i=0;i<n;i++){
        int x = t[i]>>bit&1;  //题目输入n个数，将每个数右移bit位再与1，提取第bit位， 再让其与这个数的运算符进行操作。
        if(op[i] == 1) now|=x;
        if(op[i] == 2) now^=x;
        if(op[i] == 3) now&=x;
    }
    return now;  //返回结果。
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>str>>t[i];
        if(*str =='O') op[i] = 1;   //当输入OR时表示成1；当输入XOR时表示成2；当输入AND时表示成3。
        if(*str =='X') op[i] =2;
        if(*str =='A') op[i] =3;
    }
    int val =0;  //当第K位填1时，但是构成的结果不能超过m；val就是用来判断是否超过m
    int ans = 0;  //用来存储最大能表示的数值
    for(int bit=29;bit>=0;bit--){  //m 最大是 10 ^ 9，log2(10 ^ 9) = 3log2(10 ^ 3) < 3 * 10 = 30，所以每次 i 从 29 往后枚举就可以了
        int res0 = calc(bit,0);
        int res1 = calc(bit,1);
        if(val+(1<<bit)<=m && res0<res1)  //当第bit位填1不超过m时，而且填1比填0更优时，直接填1。反之填0
            val+=1<<bit,ans+=res1<<bit;
        else ans+=res0<<bit;
        }
    
    cout<<ans<<endl;
    return 0;
}