首页 > ACM题库 > 九度OJ > 九度-1151-位操作练习[解题代码]
2013
12-12

九度-1151-位操作练习[解题代码]

题目来源:2010年北京大学计算机研究生机试真题

题目描述:

给出两个不大于65535的非负整数,判断其中一个的16位二进制表示形式,是否能由另一个的16位二进制表示形式经过循环左移若干位而得到。

循环左移和普通左移的区别在于:最左边的那一位经过循环左移一位后就会被移到最右边去。比如:
1011 0000 0000 0001 经过循环左移一位后,变成 0110 0000 0000 0011, 若是循环左移2位,则变成 1100 0000 0000 0110

输入:

第一行是个整数n, 0 < n < 300000,表示后面还有n行数据
后面是n行,每行有两个不大于65535的非负整数

输出:

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

样例输入:
4
2 4
9 18
45057 49158
7 12
样例输出:
YES
YES
YES
NO

cpp 代码如下:
#include <stdio.h>
#include <math.h>
int main() {
	int n;
	int a, b;
	int p = pow(2, 15);
	while (scanf("%d", &n) != EOF) {
		for (int i = 0; i < n; i++) {
			scanf("%d %d", &a, &b);
			int i;
			for (i = 0; i < 16; i++) {
				if (a >= p) {
					a = ((a - p) << 1) + 1;
				} else
					a = a << 1;
				if (a == b)
					break;
			}
			if (i == 16)
				printf("NO\n");
			else
				printf("YES\n");
		}
	}
	return 0;
}

/**************************************************************
	Problem: 1151
	User: coder
	Language: C
	Result: Accepted
	Time:10 ms
	Memory:904 kb
****************************************************************/

java 代码如下:

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		while(s.hasNextInt()){
			int n = s.nextInt();
			for(int i=0; i<n; i++){
				int a = s.nextInt();
				int b = s.nextInt();
				String str1 = Integer.toBinaryString(a);
				String str2 = Integer.toBinaryString(b);
				for(int j=0; j<16-str1.length(); j++)
					str1 = "0" + str1;
				for(int j=0; j<16-str2.length(); j++)
					str2 = "0" + str2;
				str1 = str1+str1;
				if(str1.contains(str2))
					System.out.println("YES");
				else
					System.out.println("NO");
			}
		}
	}

}
/**************************************************************
	Problem: 1151
	User: coder
	Language: Java
	Result: Accepted
	Time:160 ms
	Memory:15988 kb
****************************************************************/


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. 不考虑最后将结果排序的话,快排的时间复杂度是O(N) ,而堆排的是O(N*logK),这样比较看,快排快