算法很美--位运算

2019/3/22更新

题目1 : Exam07_TwoSingleNumbers
时间限制:2000ms
单点时限:1000ms
内存限制:256MB

描述

一个整型数组里除了两个数字（互不相同）之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
输入

第一行：数组的长度N(1<n<100000)
第二行：N个整数，空格隔开
输出

只出现了1次的那两个数，小的在前大的在后，空格隔开
样例输入

10
5 5 6 7 9 9 7 3 3 2 

样例输出

2 6

AC代码

#include <iostream>
#include "stdio.h" 
#include <string.h> 
#include <math.h>
using namespace std;
typedef long long LL;
const int MAX=0x3f3f3f3f;
const int maxn = 10001;
int a[maxn], n;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) 
        scanf("%d", &a[i]);
    int t = 0, cnt = 0;
    for(int i = 1; i <= n; i++) //对所有的数进行异或运算
        t ^= a[i];
    int tmp = t;
    while(tmp % 2 == 0) {
        cnt++;
        tmp >>= 1;
    }
    int x = 0, y = 0;
    for(int i = 1; i <= n; i++)     //找出其中异或后为1的数
        if((a[i] >> cnt)%2) x ^= a[i];
    for(int i = 1; i <= n; i++)     //同理
        if((a[i] >> cnt)%2 == 0) y ^= a[i];
    printf("%d %d\n", x, y);
     
    return 0;
}

题目2 : Exam08_ChangeBit
时间限制:2000ms
单点时限:1000ms
内存限制:256MB

描述

给定两个整数A和B，需要改变几个二进制位才能将A转为B。
输入

1行：A和B，空格隔开
输出

需要改变的位数
样例输入

10 8

样例输出

1

AC代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int A,B;
    cin>>A>>B;
    int num = 0;
    for(int i = 0;i < 32;i++)
    {
        if(((A>>i)&1)!=((B>>i)&1))//向右移位同一位如果不一样就要改变
            num++;
    }
    cout<<num;
}

题目3 : Exam09_StrangeDonate
时间限制:1000ms
单点时限:1000ms
内存限制:256MB

描述

地产大亨Q先生临终的遗愿是：拿出100万元给X社区的居民抽奖，以稍慰藉心中愧疚。
麻烦的是，他有个很奇怪的要求：

1. 100万元必须被正好分成若干份（不能剩余）。每份必须是7的若干次方元。比如：1元, 7元，49元，343元，...

2. 相同金额的份数不能超过5份。

3. 在满足上述要求的情况下，分成的份数越多越好！

请你帮忙计算一下，最多可以分为多少份？
输入

固定输入：1000000
输出

最多可以分为多少份
样例输入

1000000

样例输出

无

AC代码

#include <cstdlib>
#include <iostream>
#include <cmath>
using namespace std; 
int count = 0; 
int visit[10] = {0}; 
int num; 
void dfs(int step,int count) { //step代表7的几次方 
    if(visit[step] > 5) { 
    //相同金额的份数不能超过5份 
    return; 
    } 
    if(count > 1000000) {
        return; 
    } 
    else if(count == 1000000){
        num = 0; 
        for(int i = 0; i < 10; i++)
        { 
            num += visit[i]; 
        } 
        cout<< num; 
        exit(0); 
    } 
    count += pow(7,step); 
    visit[step]++;
    dfs(step, count);
    //两种路 visit[step]+1 
    dfs(step+1, count); //visit[step+1]+1 
    visit[step]--; 
    count -= pow(7,step); 
}
int main() {
    dfs(0,0);
    return 0; 
}