历年上机题-----位操作练习

女爷i 2023-07-25 06:17 16阅读 0赞

## 题目描述 ##

给出两个不大于65535的非负整数，判断其中一个的16位二进制表示形式，是否能由另一个的16位二进制表示形式经过循环左移若干位而得到。 循环左移和普通左移的区别在于：最左边的那一位经过循环左移一位后就会被移到最右边去。比如： 1011 0000 0000 0001 经过循环左移一位后，变成 0110 0000 0000 0011, 若是循环左移2位，则变成 1100 0000 0000 0110

## 输入描述: ##

每行有两个不大于65535的非负整数

## 输出描述: ##

对于每一行的两个整数，输出一行，内容为YES或NO

示例1

## 输入 ##

复制

2 4
    9 18
    45057 49158
    7 12

## 输出 ##

复制

YES
    YES
    YES
    NO

思路：有两种思路吧。

第一，直接进行位运算，进行移位操作。即先左移一位，再进行与运算。

第二，字符串模拟循环移位。

#include <bits/stdc++.h>
    using namespace std;
    string getBit(int x)
    {
        string ans;
        while(x)
        {
            ans.push_back((x%2)+'0');
            x/=2;
        }
        return ans;
    }
    bool check(string a,string b)
    {
        int n=a.size();
        for(int i=0;i<n;i++)
        {
            if(a[i]!=b[i]) return false;
        }
        return true;
    }
    string change(string a)
    {
        string ans;
        char tmp = a[0];
        for(int i=1;i<a.size();i++)
        {
            ans.push_back(a[i]);
        }
        ans.push_back(tmp);
        return ans;
    }
    int main()
    {
        #ifndef ONLINE_JUDGE
            freopen("in.txt","r",stdin);
            freopen("out.txt","w",stdout);
        #endif
        int a,b;
        while(scanf("%d%d",&a,&b)!=EOF)
        {
            string tmp_a = getBit(a);
            string tmp_b = getBit(b);
            int len1=tmp_a.size();
            int len2=tmp_b.size();
            int n=max(len1,len2);
            for(int i=0;i<16;i++)
            {
                if(i>=len1) tmp_a.push_back('0');
                if(i>=len2) tmp_b.push_back('0');
            }
            reverse(tmp_a.begin(),tmp_a.end());
            reverse(tmp_b.begin(),tmp_b.end());
            // cout<<tmp_a<<endl;
            // cout<<tmp_b<<endl;
            // cout<<endl;
            int k=0;
            bool flag=0;
            while(k<16)
            {
                if(check(tmp_a,tmp_b))
                {
                    flag=1;
                    break;
                }
                tmp_a=change(tmp_a);
                // cout<<tmp_a<<endl;
                // cout<<tmp_b<<endl;
                // cout<<endl;
                k++;
            }
            if(flag)
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
            
        }
        return 0;
    }