首页 > 试题广场 >

位操作练习

[编程题]位操作练习
  • 热度指数:8750 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
给出两个不大于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<stdio.h>
#include<math.h>
int main (void){
    int a,c;
    while(scanf("%d %d",&a,&c)!=EOF){
        int flag=0;
        int * conversion(int a);
        int *b;
        int *d;
        b=conversion(a);
    //一共可以进行16次循环左移,每次循环判断左右两数能否相等
        for(int k=0;k<16;k++){
            int temp=b[15];
            //接下来开始进行一次的左移
            for(int i=0;i<16;i++){
                *(b+15-i)=*(b+15-1-i);
            }
            b[0]=temp;
            //这个用来看转换为的二进制
//             for(int i=0;i<16;i++){
//                 printf("%d ",*(b+i));
//             }printf("\n");
            //计算移位后的值
            int out=jisuan(b);
//             printf("%d ",out);
//             printf("\n");
            if (out==c){
                flag=1;
            }
       }
//         printf("\n");
        d=conversion(c);
    //一共可以进行16次循环左移,每次循环判断左右两数能否相等
        for(int k=0;k<16;k++){
            int temp=d[15];
            //接下来开始进行一次的左移
            for(int i=0;i<16;i++){
                *(d+15-i)=*(d+15-1-i);
            }
            d[0]=temp;
        //     //这个用来看转换为的二进制
        //     for(int i=0;i<16;i++){
        //         printf("%d ",*(b+i));
        //     }printf("\n");
            //计算移位后的值
            int out=jisuan(d);
//             printf("%d ",out);
            if (out==a){
                flag=1;
            }
       }
        
        if(flag==1){
           printf("YES\n");  
        }
        else{
            printf("NO\n");
        }
       
    }
    

    return 0;
}
//这个函数用来转换进制
int * conversion(int a){
    int jishu=0;
    int cunchu[100];
    int n=0;
    while(a!=1){
        n=a%2;
        a=a/2;
        cunchu[jishu]=n;
        jishu+=1;
    }
    cunchu[jishu]=1;
    
    int zong=jishu+1;
    int se[zong];
    for(int j=0;j<zong;j++){
        se[j]=cunchu[jishu-j];
    }
    //补全16位
    int se17[17];
    for(int i=0;i<zong;i++){
        se17[i]=se[i];
    }
    for(int i=zong;i<16;i++){
        se17[i]=0;
    }
    se17[16]=9;
    int *r=se17;

    return r; 
}
int jisuan(int a[16]){
    int sum=0;
    for(int i=0;i<16;i++){
        sum+=a[15-i]*pow(2,i);
    }
    return sum;
}

发表于 2022-02-27 16:57:29 回复(0)
#include<iostream>
#include<cstring>
using namespace std;

int main()
{
    int a,b;
    while(cin >> a >> b)
    {
        int i;
        for(i = 1;i <= 16;i++)
        {
            if(a & (1 << 15))
            {
                a = ((a << 1) | 1) & 65535;
            }
            else
            {
                a = (a << 1) & 65535;
            }
            if(a == b)
            {
                cout << "YES" << endl;
                break;
            }
        }
        if(i == 17)
            cout << "NO" << endl;
    }
    return 0;
}

发表于 2021-02-14 23:16:06 回复(0)
#include<stdio.h>//1.数字转换成16位二进制
#define N 16//2.循环左移最多16次如果相同key=1;
int main()
{
    int m,n,a[N]={0},b[N]={0},i,j,t,key,num;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        num=N-1;//1.数字转数组
        while(m)
        {a[num--]=m%2;m/=2;}
        num=N-1;
        while(n)
        {b[num--]=n%2;n/=2;}
        //2.循环左移
        for(i=0;i<N;i++)//最多左移16次返回原来的位置
        {
            key=1;
            t=a[0];//2.1循环迁移一次
            for(j=0;j<N-1;j++)
                {a[j]=a[j+1];}
            a[N-1]=t;
            for(j=0;j<N;j++)//2.2判断是否相等
                if(a[j]!=b[j])
                { key=0;break;}
            if(key==1)//相等了不用再前移了结束循环
            {printf("YES\n");break;}
        }
        if(key==0) printf("NO\n");
    }
}

编辑于 2020-04-01 22:09:35 回复(0)
/*化为二进制,2倍的a串里找b串*/
#include <bits/stdc++.h>
using namespace std;
string to2( int x ){
	string t = "" ;
	while( x ){
		t += (char)( x % 2 + '0' ) ;
		x /= 2 ; 
	}
	for( int i = t.size() ; i < 16 ; i++ ){
		t += "0" ;
	}
	reverse( t.begin() , t.end() ) ; 
	return t ; 
}
int main() {
	int x , y ; 
	while( ~scanf("%d%d",&x,&y) ){
		string a = to2(x);
		a += a ; 
		string b = to2(y);
		int res = a.find(b) ;
		if( res >= 0 && res < a.size() ){
			printf("YES\n");
		}else printf("NO\n");
	}
	return 0 ;
}

发表于 2020-03-11 16:32:51 回复(0)
测试用例有误,还以为4是输入4对整数,调试了好久,气死了。
#include <stdio.h>

void bin(int a,int t[])
{
    memset(t,0,sizeof(int)*16);
    int c,i=15;
    while(a)
    {
        t[i--]=a%2;
        a/=2;
    }
}
int main()
{
    int a,b;
    while (scanf("%d%d",&a,&b)!=EOF)
    {
        int t1[16],t2[16],i,j,r,count=0;
        bin(a,t1);
        bin(b,t2);
        for(i=0;i<16;i++)
        {
            if(count==16)break;
            r=i,j=0,count=0;
            while(t1[r]==t2[j])
            {
                r=(r+1)%16;
                j=j+1;
                count++;
                if(count==16)
                {
                    printf("YES\n");
                    break;
                }
            }
        }
        if(count!=16)printf("NO\n");
    }
}


编辑于 2020-02-12 19:08:49 回复(0)

我好菜啊

#include<string>
using namespace std;

//int a_bin[16], b_bin[16];

void dec2bin(int a, int a_bin[]){
    fill(a_bin, a_bin + 16, 0);
    for(int i = 0; i < 16; i++){
        a_bin[i] = a % 2;
        a /= 2;
    }
}

bool cmp(int a_bin[], int b_bin[]){
    for(int i = 0; i < 16; i++){
        if(a_bin[i] != b_bin[i])
            return false;
    }
    return true;
}

void rcl(int a_bin[]){
    int temp = a_bin[0];
    for(int i = 0; i < 15; i++){
        a_bin[i] = a_bin[i + 1];
    }
    a_bin[15] = temp;
}

int main(){
    int a, b;
    while(cin >> a >> b){
        int a_bin[16], b_bin[16];
        bool flag = false;
        dec2bin(a, a_bin);
        dec2bin(b, b_bin);
        for(int i = 0; i < 16; i++){
            rcl(a_bin);
            if(cmp(a_bin, b_bin)){
                flag = true;
                break;
            }
        }
        if(flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}
发表于 2019-03-13 17:40:13 回复(1)
感觉比较啰嗦,而且没有充分利用空间,开的空间略大,本来应该用char来存可能性能上更好一点,而且应该直接有按位左移的操作的,这里用int数组还是考虑不太周全
#include<iostream>
using namespace std;
int main() {
    int a[16];
    int b[16];
    int a1, b1;
    while (cin >> a1 >> b1) {
        for (int i = 0; i<16; i++)
            a[i] = b[i] = 0;
        int temp1 = 0;
        while (a1>0) {
            a[temp1++] = a1 % 2;
            a1 /= 2;
        }
        temp1 = 0;
        while (b1>0) {
            b[temp1++] = b1 % 2;
            b1 /= 2;
        }
        bool judge = 0;
        for (int i = 0; i<16; i++) {
            int temp2 = a[15];
            for (int j = 15; j>0; j--)
                a[j] = a[j-1];
            a[0] = temp2;
            for (int j = 0; j<16; j++) {
                if (a[j] != b[j])
                    break;
                else {
                    if (j == 15) {
                        judge = 1;
                        break;
                    }
                }
            }
        }
        if (judge == 1)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

}

发表于 2019-02-08 14:55:52 回复(1)
#include<stdio.h>
#include<vector>
#include<string>
using namespace std;

string getBitString(int n){
    string s;
    while(n>0){
        s+=(n%2+'0');
        n/=2;
    }
    string result;
    for(int i=s.size()-1;i>=0;i--){
        result+=s.at(i);
    }
    int length=16-result.size();
	string prefix;
	for(int i=0;i<length;i++){
		prefix+='0';
	}
	result.insert(0,prefix);
    return result;
}

bool canChange(string str1,string str2){
    for(int i=0;i<str1.size();i++){
		string first=str1.substr(0,i);
		string second=str1.substr(i,str1.size());
		first.insert(0,second);
		if(first.compare(str2)==0){
			return true;
		}
    }
	return false;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
            int first,second;
            scanf("%d",&first);
            scanf("%d",&second);
            string str1=getBitString(first);
            string str2=getBitString(second);
            bool flag=canChange(str1,str2);
            if(flag){
                printf("%s\n","YES");
            }else{
                printf("%s\n","NO");
            }
    }
    return 0;
}

发表于 2016-10-26 11:12:45 回复(0)
#include<iostream>
using namespace std;
int main()
{
    unsigned short M,N;
    while(cin>>M>>N)
    {
        for(int i=0;i<16;i++)
        {
            if(M==N)
            {
                cout<<"YES"<<endl;
                break;
            }
            else if(i==15)
                cout<<"NO"<<endl;
            else
                M=M<<1|(M>>15&1);
        }
    }
}

发表于 2018-08-09 11:15:15 回复(6)
//循环移位可以通过左移右移相或实现
//比如循环右移i位等于((a << (N - i)) & 0xffff) | (a >> i)
#include<iostream>
using namespace std;

const int N = 16;
bool solve(unsigned int a, unsigned int b) {
	for (int i = 0;i<N;i++) {
		if ((((a << (N - i)) & 0xffff) | (a >> i)) == b)
			return true;
	}
	return false;
}

int main() {
	unsigned int n, a, b;
	while (cin >> n) {
		for (int i = 0;i<n;i++) {
			cin >> a >> b;
			cout << (solve(a, b) ? "YES" : "NO") << endl;
		}
	}
}

发表于 2017-07-06 15:48:44 回复(2)
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
    unsigned short m,n;
    while(cin>>m>>n){
        int i;
        for(i=0;i<15;i++){
            if(m==n) break;
            else m=(m<<1)|(m>>15);    //左移 m左移1位后或上m右移15位即为循环移动一位
        }
        i<15 ?cout<<"YES"<<endl : cout<<"NO"<<endl;
    }
}

编辑于 2020-03-13 11:56:03 回复(1)
可以不用转化成二进制, 直接用位操作即可,但是需要注意整数的位操作默认是32位的,题目中要求是16位二进制,所以左移的结果要与上低16位都为1 ,高16位都为0 的数(65535)。循环左移可以用左移n位 与上 右移16-n位  
#include<stdio.h>
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        int flag = 0;
        for(int i = 0; i <= 16; i++){
            if(n == (((m << i)&65535)|(m >> (16-i)))){
                printf("YES\n");
                flag = 1;
                break;
            }
        }
        if(flag == 0){
            printf("NO\n");
        }
    }
    return 0;
}


发表于 2019-08-16 22:40:30 回复(1)

位操作练习题目总结:

法一:              循环右移:((a << (N - i)) & 0xffff) | (a >> i)

                                   循环左移:((a <<  i) & 0xffff) | (a >> (N-i))

注意:整数的位操作默认是32位的,题目中要求是16位二进制,所以左移的结果要&上低16位都为1 ,高16位都为0 的数(65535)。循环左移可以用左移i&上 右移16-i位 (循环左移)

规律:必须是左移时&0xffff

 

法二:                         一个一个右移:M=M>>1|(M<<15&0xf000);

                                   一个一个左移:M=M<<1|(M>>15&1);

易错点:一个一个右移时可声明为unsigned int或者unsigned short

一个一个左移时只能声明为unsigned short。若为unsigned int,则会出错。

初步猜想:是&后面的数导致的,若&1,则不确定有多少位,变为默认的32位,所以出错。但&0xf000则必是16

 ps:花了我一下午总结的。。。

#include<iostream>
using namespace std;
int main()
{
    unsigned int M,N;//unsigned short不会报错。但改为M=M<<1|(M>>15&1);仍用unsigned int则会出错 
    while(cin>>M>>N)
    {
        for(int i=0;i<16;i++)
        {
            if(M==N)
            {
                cout<<"YES"<<endl;
                break;
            }
            else if(i==15)
                cout<<"NO"<<endl;
            else
                M=M>>1|(M<<15&0xf000);
        }
    }
}

发表于 2020-03-09 20:55:12 回复(0)
#include<bits/stdc++.h>
int main(){
    unsigned short m,n;
    while(scanf("%hu %hu",&m,&n)!=EOF){
        int i;
        for(i=0;i<16;i++){
            if(m==n){
                printf("YES\n");
                break;
            }
            unsigned short s=m&1;
            s=s<<15;
            m>>=1;
            m|=s;
        }
        if(i==16)
            printf("NO\n");
    }
}
发表于 2019-03-07 15:30:21 回复(0)

python solution

使用了deque,因为里面有rotate函数,不用再造轮子了~~


from collections import deque
a = int(input())
for i in range(a):
    a, b = map(lambda c: bin(c).replace("0b", "").rjust(16, "0"), map(int, input().split()))
    hasSolution = False
    for i in range(16):
        rotateDeque = deque(a)
        rotateDeque.rotate(-i)
        if rotateDeque == deque(b):
            hasSolution = True
            break
    print("YES" if hasSolution else "NO")

也可以使用移位操作,比这个更简单。。

编辑于 2017-10-16 16:59:40 回复(0)
#include<iostream>
#include<cstdio>
using namespace std;

int main()
{
    int n;
    int flag = 0;
    unsigned short x1, x2;
    cin >> n;
    while(n--)
    {
        cin >> x1 >> x2;
        flag = 0;
        // 移位 16 次判断,再移位就恢复了原来的 x1
        for(int i = 0; i < 16; ++i)
        {
            if(x1 == x2)
            {
                flag = 1;
                break;
            }

            if(x1 & (1<<15))
            {
                x1 <<= 1;
                ++x1;
            }
            else
            {
                x1 <<= 1;
            }
        }
        // 输出
        if(flag == 1)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }

    return 0;
}


发表于 2016-08-09 14:49:26 回复(0)
感觉大伙想太多了,虽然本质上是二进制,但是完全没必要换成二进制折磨自己,左移一位就是乘以2,循环左移也就是结果要对2^16-1取余,左移16次后还不对那就说明NO呗。
#include <iostream>
#include <cmath>

using namespace std;

int main(){
    int a, b;
    while (cin >> a >> b) {
        int val = pow(2, 16)-1;
        int flag = 0;
        for (int i = 0; i < 16; ++i) {
            if(a == b) {
                flag++;
                cout << "YES" << endl;
                break;
            }
            else{
                a = (a * 2) % val;
            }
        }
        if(flag == 0)
            cout << "NO" << endl;
    }
}


编辑于 2024-03-25 15:32:16 回复(0)
import java.util.Scanner;
import java.util.LinkedList;
import java.util.List;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
        //String str = sc.nextLine();
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();
        String s1 = Integer.toBinaryString(num1);
        String s2 = Integer.toBinaryString(num2);
       // System.out.println(num1+" "+num2);

        //System.out.println(s1+" "+s2);
        //System.out.println(str);
        char[] shuzu1 = s1.toCharArray();
        char[] shuzu2 = s2.toCharArray();
//        System.out.println(shuzu1);
//        System.out.println(shuzu2);
        LinkedList<Character> list1 = new LinkedList<>();
        LinkedList<Character> list2 = new LinkedList<>();
        for (int i = 0; i < shuzu1.length; i++) {
            list1.addLast(shuzu1[i]);
        }
        for (int i = 0; i < shuzu2.length; i++) {
            list2.addLast(shuzu2[i]);
        }
        while (true){
            if(list1.size()<16){
                list1.addFirst('0');
            }
            if(list2.size()<16){
                list2.addFirst('0');
            }
            if(list2.size() == 16 && list1.size()==16){
                break;
            }

        }

        int min = Math.min(shuzu2.length,shuzu1.length);
        boolean flag = false;
        int i = 0;
        while(i<min){
            for(int j = 0;j<min;j++){
                if(list1.get(j) != list2.get(j)){
                    break;
                }
                if(j == min-1 && list1.get(j) == list2.get(j)){
                    flag = true;
                    System.out.println("YES");
                }
            }
            if(flag) break;
            list1.addLast(list1.getFirst());
            list1.removeFirst();
            i++;
        }
        if(!flag) System.out.println("NO");

    }
}

编辑于 2024-03-09 15:04:43 回复(0)
Brute Force,蛮力出奇迹
1、将输入的数字 A, B转换为二进制(conversion(num, oldBase, newBase))
2、    binaryA = conversion(A, 10, 2)
          binaryA = conversion(A, 10, 2)
    然后将 binaryA 依次循环左移,一一比较判断(最多移位16次)

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

string conversion(string s, int oldBase, int newBase) {
	string rc = "";	// Return Code
	
	int n = s.length();
	for (int i = 0; i < n; ) {
		int carry = 0; // 是否有进位
		for (int j = i; j < n; j++) {
			int value = carry * oldBase + s[j] - '0';
			s[j]  = value / newBase + '0';
			carry = value % newBase; 
		}
		rc.push_back(carry + '0');
		while (s[i] == '0') {
			i++;
		}
	}
	
	// 高位补零
	while (rc.length() != 16) {
		rc.push_back('0');
	}
	reverse(rc.begin(), rc.end());
	
	return rc;
}

void leftShift(string& s) {
	char front = s[0];
	s.erase(s.begin());
	s.push_back(front);
}

int main() {
//	freopen("D:\\DeskTop\\in.txt", "r", stdin);
	
	string A, B;
	while (cin >> A >> B) { // 注意 while 处理多个 case
		string binaryA = conversion(A, 10, 2);
		string binaryB = conversion(B, 10, 2);
		
//		cout << "DEBUG: binary A" << binaryA << endl;
//		cout << "DEBUG: binary B" << binaryB << endl;
		
		bool res = false;
		for (int i = 0; i < 16; i++) {
			leftShift(binaryA);
			if (binaryA == binaryB) {
				res = true;
				break;
			}
		}
		if (res)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
}


发表于 2023-05-01 10:51:17 回复(0)
#include <stdio.h>

int main() {
    unsigned short a, b;
    while (scanf("%hu%hu", &a, &b) == 2) {
        int flag = 0;
        for (int i = 0; i < 16; i++) {
            if (a == b) {  // 找到了匹配的情况
                flag = 1;
                break;
            }
            a = ((a << 1) | (a >> 15));  // 循环左移1位
        }
        printf("%s\n", flag ? "YES" : "NO");
    }
    return 0;
}
//如果二进制各个位置都相等,那原数也一定相等

发表于 2023-03-14 16:11:31 回复(0)