[数据结构与算法]【算法题】位运算的使用总结 且或非异或左移右移

位运算的奇巧淫技

位运算的四大功能

1. 判断奇偶数

   x&1 = 1 奇数

   x&0 = 0 偶数

2. 获取二进制位是1还是0

   num>>(i-1)&1

3. 交换两个整数变量的值

   一个数与自身进行异或为0，一个数与0异或得到自身

   a=a^b;

   b=a^b;

   a=a^b;

4. 不用判断语句，求整数的绝对值

   int i = n >> 31; //int 为32位，右移31位得到符号位，赋值给i，若为正，则i=0；负，i=-1

   return ((n ^ i) - i); //一个数^{0=原数，数}-1=数的绝对值-1 即 绝对值=负数异或-1再+1

Example1：

1- 1000这1000个数放在含有1001个元素的数组中，只有唯一-的
一个元素值重复，其它均只出现一次。每个数组元素只能访问一
次，设计一个算法，将它找出来;不用辅助存储空间，能否设计一
个算法实现?

利用异或的性质，一个数与自身异或为0，将目标数组与1~1000进行异或，出现两次的数都变为0吗，出现三次的数字异或之后等于自身，最终只剩下重复出现的元素。

	public static void main(String args[]) {
		int N= 1001;
		int[] arr = new int[N];
		for(int i =0;i<arr.length -1;i++) {
			arr[i]=i+1;
		}
		//最后一个数是随机数
		arr[arr.length-1]=new Random().nextInt(N-1)+1;
		int index = new Random().nextInt(N);
		//输出数组，最后一个数是重复出现
		for(int i=0;i<N;i++) {
			System.out.print(arr[i]+" ");
		}
		//开始计算
		int x=0;
		//先从1~1000进行异或
		for(int i=1;i<=N-1;i++) {
			x=(x^i);
		}
		//与目标数组进行异或
		for(int i=0;i<N;i++) {
			x=x^arr[i];
		}
		//输出结果
		System.out.println(x);
	}

Example2：

一个数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现了一次的数字。

直接将数组进行异或，最后剩下只出现过一次的数字。

class Solution {
    public int singleNumber(int[] nums) {
       int x=0;
       for(int i =0;i<nums.length;i++){
           x=x^nums[i];
       }
       return x;
}
}

Example3：

输入一个整数，输出该数二进制表示中1的个数。

对每一位进行0、1判断，count进行计数，得到结果。

public class main {
	public static void main(String args[]) {
	Scanner scan = new Scanner(System.in);
	int a = scan.nextInt();
	int count = 0;
	 for(int i=1;i<32;i++) {		 
		 if(and2(a,i)==1) {
			 count++;
		 }
	 }
	 System.out.println(count);
	}
	
	public static int and2(int num, int i) {
        // 先将数字右移指定第i位，然后再用&与1运算
        return num >> (i-1) & 1;
    }
}

Example4：

用一条语句判断一个整数是不是2的整数次方

题意可以转换为，判断一个整数的2进制表示中是否只含有一个1。2的整数次方的整数例如8（1000）与小一位整数7（0111）正好互补，进行与运算之后必为0.

	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		if((a&(a-1))==0)
			System.out.println("ture");
		else {
			System.out.println("flase");
		}
	}

Example5：

将整数的奇偶位互换

经观察，一位数与1相与结果不变，与0相与全为0 。因此可以利用这一性质，将目标整数与奇数位为0，偶数位为1的二进制整数进行与运算，得到偶数位，同理得到奇数位，最后分别左移，右移一位，相异或得到最终结果。

public static void main(String args[]) {
		Scanner scan= new Scanner(System.in);
		int a = scan.nextInt();
		int ou =a&0b10101010101010101010101010101010;
		int ji =a&0b01010101010101010101010101010101;
		System.out.println((ou>>1)^(ji<<1));
	}

Example6：

给定一个介于0和1之间的师叔，如（0.625），类型为double，打印它的二进制表示（0.101,因为小数点后的二进制分别表示为0.5，0.25，0.125…）。

如果该数字无法精确地用32位以内的二进制表示，则打印“error”