首页 > 代码库 > 用java实现异或操作
用java实现异或操作
最近看了博客园的很多应届生面试bae成功的经历,由衷的佩服和满满的感叹:付出总有回报。于是自己也心痒痒想找几分面试题目做做。无意间看到了这道题目。
一个数组存放了2n+1个整数,其中有n个数出现了2次,1个数出现了1次,找出出现1次的数是多少?
我想了很久没想出来,可见我很笨,百度了下答案,说只要对所有数异或一遍即可。恍然大悟,于是马上想在java上实现一下。不料结果根本不是正确的。一直以为是自己写错代码了,还百度了下异或的符号^到底对不对,符号是对了,可是度娘说java没有二进制类型,唯一跟二进制搭上边的,只有把int转成string来勉强表示二进制数。这可如何是好,对于我这种菜鸟来说,觉得何不自己定义一个Binary类呢?几经波折,终于还是出来啦!
1 package com.test.main; 2 3 public class Binary { 4 5 6 //define a binary instance 7 private String binary; 8 //接收int类型,转换成String; 9 Binary(int a){10 this.binary=Integer.toBinaryString(a);11 }12 //接收String类型的二进制,用于构造Binary对象13 Binary(String s){14 this.binary=s;15 }16 17 public Binary xor(Binary x){18 String anotherBinary=x.binary;19 String thisBinary=this.binary;20 String temp;21 String result;22 int length;23 length=thisBinary.length()-anotherBinary.length();24 // keep thisBianry‘s length is not shorter than anotherBnary;25 if(length<0){26 temp=thisBinary;27 thisBinary=anotherBinary;28 anotherBinary=temp;
length=-length;29 }30 31 //截取较长字符串多出来的那一段32 if(length>0){33 result=thisBinary.substring(0, length);34 }35 else{36 result="";37 }38 for(int i=0;i<anotherBinary.length();i++){39 //如果相同位置数相同,则补0,否则补140 if(thisBinary.charAt(i+length)==anotherBinary.charAt(i))41 result+="1";42 else{43 result+="0";44 }45 }46 //构造Binary对象47 Binary b=new Binary(result);48 49 return b;50 51 }52 }
以上为为定义的二进制class,能实现异或操作,其实其他的与和并操作都可以实现,在此不累赘了。
1 public static void main(String[] args) {2 int[] arr={1,1,2,2,3,3,4,4,4,4,5,5,6,6,7,7,8,8,8};3 Binary sum=new Binary(arr[0]);4 for(int i=1;i<arr.length;i++){5 sum=sum.xor(new Binary(arr[i]));6 }7 System.out.println(sum.binary);8 9 }
上述为我测试的代码,即只要数组含有偶数个整数,而只有一个是奇数个的整数,就能把这个奇数找出来,最后打印出来的是奇数的二进制形式,其实最后我该写的方法,把二进制转换成int的.实现应该比较简单。
最后补充一句,其实这样做效率是很低的,要对每一个string的位操作,其中还有string+“”的语句其实很低效,我只是为了实现而实现罢了,实际还是用hashmap记录每个数出现的次数,把奇数次的拎出来就可以了,再嫌慢的话,直接用c语言哈!
用java实现异或操作
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。