位运算符
例1：找出落单的数。
一个数组中除了某一个数之外，其他的数字都出现了两次，请找出这个数字；
【知识点】相等的数做异或被消掉了（A ^ A ^ B ^ C ^ C=B）；
【思考】遍历依次做异或即可。
例2：如何找数组中唯一成对的数？
1-1001这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间。
【知识点】相等的数做异或被消掉了（A ^ A ^ B ^ C ^ C=B）
【思考】一般情况下考虑定义一个数组，用一个for循环解决，list[arr[i]]++;这道题的特点：1、已知其中的1000个数；2、不用辅助存储空间。可以考虑用异或运算实现；在本数组做异或的基础上再与1-1000做异或，这样要找的数做了三次异或，而其它数只做了两次异或。
import java.util.*；
public class Main{
public static void main(String args[]){
//先构造一个符合题意的数组
int N=1001;
int[] arr=new int[N];
for(int i=0;i<N-1;i++){
arr[i]=i+1;
}
int randNum=new Random().nextInt(N); //生成一个随机数放在最后一位
arr[N-1]=randNum;
int index=new Random().nextInt(N-1); //抽取一个数与最后一个数交换位子
swap(arr,index,N-1);
for(int n:arr)
System.out.print(n+", "); //打印函数用来确认结果是否正确
//设x先做1到N的异或，再与数组中的元素做异或，最后剩下的数（做了奇次异或）被赋给了x；
int x=0;
for(int i=1;i<=N-1;i++)
x=x^i;
for(int j=0;j<N;j++)
x=x^arr[j];
System.out.println();
System.out.println(x);
}
static void swap(int[] arr,int index1,int index2){
int temp=arr[index1];
arr[index1]=arr[index2];
arr[index2]=temp;
}
}
例3：二进制中1的个数
请实现一个函数，输入一个整数，输出该整数二进制表示中1的个数。例：9的二进制表示为1001，有2位是1。
【知识点】1、(N>>>i&1)==1用于判断二进制第i位上是否为“1”；2、N=N&(N-1);可以消掉一个“1”；
【思考】可以遍历依次与1做与运算，数有多少个1；也可以一个一个地消掉1，数要消掉多少个1才能得到0；
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int N=in.nextInt();
System.out.println(Integer.toString(N,2)); //将int类型的N以二进制输出，这里用来检验结果是否正确
//方法1：将N不断右移
int count1=0;
for(int i=0;i<32;i++){ //输入的是int型，所以用的是32
if((N>>>i&1)==1)
count1++;
}
System.out.println(count1);
//方法2：N&（N-1）可以消掉一个“1”
int count2=0;
while(N!=0){
N=N&(N-1);
count2++;
}
System.out.println(count2);
}
}
例4：是不是2的整数次方
用一条语句判断一个整数是不是2的整数次方。
【知识点】N=N&(N-1);可以消掉一个“1”；2的整数次方说明二进制表示中只有一个1。
【思考】那么只要判断1的个数。如果做了一次消除就能得到0，就说明它是2的整数次方。
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int N=in.nextInt();
System.out.println(Integer.toString(N,2));
if((N&(N-1))==0)
System.out.println("是的");
}
}
例5：将整数的奇偶位交换
一个整数用二进制表示，奇偶位交换
【知识点】1、N&(101010...10),N二进制奇数位上的数字得以保留，N&(010101...01),N二进制偶数位上的数字得以保留。2、用十六进制表示数0x...(因为这里用二进制的话要写32位，太不容易了)
【思考】既然要交换，那么保留奇数位的要右移，保留偶数位的要左移，再做异或运算。
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int N=in.nextInt();
System.out.println(Integer.toString(N,2));
int L=N&0x55555555;
int r=N&0xaaaaaaa;
int p=(r>>1)^(L<<1);
System.out.println(Integer.toString(p,2));
}
}
例6：0~1间浮点实数的二进制表示
给定一个介于0和1之间的实数（如0.625），类型为double，打印它的二进制表示（0.101），如果该数字无法精确地用32位以内的二进制表示，则打印"ERROR"
【知识点】1、浮点小数如何转换成二进制：小数部分乘以2，如果大于1，则结果的小数部分下一位是1，否则是0，小数部分一直重复此操作，直到得到0；2、StringBuilder 的常用方法
【思考】这就是将知识点1翻译成代码。
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
double N=in.nextDouble();
StringBuilder sb=new StringBuilder("0.");
boolean flag=false;
for(int i=0;i<32;i++){
N*=2;
if(N>=1){
sb.append("1");
N--;
}
else
sb.append("0");
if(N==0){
flag=true;
break;
}
}
if(flag)
System.out.println(sb.toString());
else
System.out.println("error");
}
}
