位运算的基本运用
当出现关于2的整数次幂的运算时，往往可以用位运算解决。
比如对8取余，n&7的写法就比n%8好很多。
(10)00001010&(7)00000111=(2)00000010
奇偶性测试的更好写法
//奇数返回true
boolean odd(int n){
return n&1==1;
}
不用乘法实现5*n的做法
n<<2+n
异或遵循结合律和交换律
a xor b xor a=a xor a xor b=(a xor a)xor b=0 xor b=b
不使用第三个变量交换a，b
a=a^b,b=a^b,a=a^b;
注意一种错误的解法:
a=a+b,b=a-b,a=a-b;
错误在于执行a+b时可能会产生溢出
计算二进制中1的个数
public static void main(String[] args) {
int n=7;
int a=calOne(n);
System.out.print(a);
}
//去除二进制中的最后一位1
public static int removeOne(int sum){
return sum&(sum-1);
}
//计算1的个数
public static int calOne(int sum){
int count=0;
while(sum!=0){
sum=removeOne(sum);
count++;
}
return count;
}
计算结果3
n-1的结果，一定是高位保持不变，最后的1拆成0，后面几位0变1。如00001100减1,00001011
所以n&(n-1)的结果就是最后一位1变0，其他不变，即去除最后一位1。
找数字问题
1.一个整形数组内除了一个数字外其他数字都出现了两次，请找出这个数字。
解题思路:
对数组所有元素进行异或操作，所有出现两次的数字先与自己进行异或操作，结果为0，最后剩下的那个数字就是要找的数字。
public class TestXor {
public static void main(String[] args) {
int[] data={1,1,2,3,3,4,4};
int Xor=0;
for(int i=0;i<data.length;i++){
Xor^=data[i];
}
System.out.print(Xor);
}
}
2.如果数组中只出现一次的数字变成了两个，找出这两个数。
解题思路:
还是先对数组中所有元素进行异或运算，剩下两个要找的数异或运算。异或运算的本质是相同为0，不同为1，因此我们可以找出异或运算结果的第一个1的位置，记为第N位，这意味着第N位这两个数字是不同的。根据这个我们可以把数组分为两个子数组，第一个数组第N位都是0，第二个数组第N位都是1。然后对两个子数组分别进行异或运算。
public class TestXor {
public static void main(String[] args) {
int[] data={1,1,2,3,3,4,4,5};
findNum(data);
}
public static int findNum(int[] data){
int Xor=0;
int num1=0;
int num2=0;
for(int i=0;i<data.length;i++){
Xor^=data[i];
}
int pos=findOne(Xor);
for(int i=0;i<data.length;i++){
if(TestBit(data[i], pos)){
num1^=data[i];
}
else
num2^=data[i];
}
System.out.print(num1+","+num2);
return 0;
}
//找到第一个1的位置
public static int findOne(int Xor){
int pos=0;
while((Xor&1)!=1){
Xor=Xor>>1;
pos++;
}
return pos;
}
//判断第N位是否为0
public static boolean TestBit(int v,int pos){
return ((v>>pos)&1)==0;
}
}
3. 1-1000中少了两个数，找出没有出现的两个数。
解决思路:
创建一个1-1000的数组，与少了两个数的数组相加成一个新数组，然后用题二的方法解决。
import java.util.Random;
public class TestXor2 {
public static void main(String[] args) {
//int[] data={1,2,3,4,6,7,9,10};
//RandomArray(8);
findNum(RandomArray(998));
}
public static int findNum(int[] data){
int Xor=0;
int num1=0;
int num2=0;
int[] data2=new int [1000];
int L=data.length+data2.length;
int[] data3=new int [L];
for(int i=0;i<1000;i++){
data2[i]=i+1;
}
//合并数组
for(int i=0;i<data3.length;i++){
if(i<data.length)
data3[i]=data[i];
else
data3[i]=data2[i-data.length];
}
for(int i=0;i<data3.length;i++){
Xor^=data3[i];
}
int pos=findOne(Xor);
for(int i=0;i<data3.length;i++){
if(TestBit(data3[i], pos)){
num1^=data3[i];
}
else
num2^=data3[i];
}
System.out.println(num1+","+num2);
return 0;
}
//找到第一个1的位置
public static int findOne(int Xor){
int pos=0;
while((Xor&1)!=1){
Xor=Xor>>1;
pos++;
}
return pos;
}
//判断第N位是否为0
public static boolean TestBit(int v,int pos){
return ((v>>pos)&1)==0;
}
//生成随机不重复数组
public static int[] RandomArray(int sum){
int[] data = new int[sum];
int setRadnom = 0; //存放随机数
int count = 0; //已生成的随机数个数
int flag = 0;
while(count<sum){
Random rdm = new Random();
setRadnom = rdm.nextInt(1000)+1;
//判断随机数是否重复
for(int i=0;i<count;i++){
if(data[i]==setRadnom){
flag = 1;
break;
}else{
flag = 0;
}
}
if(flag==0){
data[count] = setRadnom;
count++;
}
}
return data;
}
}
