位运算的简单应用

位运算的简单应用 算法基础课–位运算(day_1) 一、语法

​ （一）、常用位运算解决的问题类型

1、判断奇偶数

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

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

​ tips:

1、所有奇数最后一位为1，偶数为0，x&1=1，为奇数

2、异或作用：连续异或可以消除重复值

二、习题

习题1 找出唯一成对的数

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

思路：

​ 由于每个元素只能访问一次，所以不能使用双重for循环暴力求解，我们这次采取的是位运算。

位运算思想：

A^A=0,B^0=B
A^A^B^c^c=B

在一个序列当中，连续做异或，可以消除重复

(1...k...k...100...9..2)^(1...1000)
 1----------------------->1成一对，则k变成3个，两两相同异或变为0,0^k=k

代码如下：

import java.util.Random;

public class 唯一成对的数 {
    public static void main(String[] args) {
        int N=11;
        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;//确保范围在[0,11），注意是左闭右开
        //随机下标
        int index=new Random().nextInt(N);
        for (int i = 0; i  
第一个for循环将数组中的元素以^的形式排列起来
 
arr={1 2 3 4 5 6 7 8 9 10 7 }
第一个for循环结束后x等价于0^1^2^3^4^5^6^7^8^9^10^7 
 
第二个for循环相当于把x中相同的数字消去 且每个数字只消去一次 最终只留下多余的一个数
 
0^1^2^3^4^5^6^7^8^9^10^7   ^1  == 0^2^3^4^5^6^7^8^9^10^7 (1与1相同消掉了)
0^2^3^4^5^6^7^8^9^10^7     ^2  ==  0^3^4^5^6^7^8^9^10^7  (2与2相同消掉了)
0^3^4^5^6^7^8^9^10^7       ^3  ==  0^4^5^6^7^8^9^10^7    (3与3相同消掉了)
0^4^5^6^7^8^9^10^7         ^4  ==  0^5^6^7^8^9^10^7		 (4与4相同消掉了)
0^5^6^7^8^9^10^7           ^5  ==  0^6^7^8^9^10^7        (5与5相同消掉了)
0^6^7^8^9^10^7             ^6  ==  0^7^8^9^10^7			 (6与6相同消掉了)
0^7^8^9^10^7               ^7  ==  0^8^9^10^7			 (7与7相同消掉了)(为了方便对比，第一次我没有去掉7)
0^8^9^10^7                 ^8  ==  0^9^10^7				 (8与8相同消掉了)
0^9^10^7                   ^9  ==  0^10^7				 (9与9相同消掉了)
0^10^7                     ^10 ==  0^7					 (10与10相同消掉了)
0^7 == 7
 
​ tips
 
1、rand.nextInt（）随机数取值范围
 
​ 左闭右闭 [a,b]：rand.nextInt(b-a+1)+a
 
​ 左闭右开 [a,b)：rand.nextInt(b-a)+a
 
2、rand.nextInt（）为java.util.Random类中的方法
 
​ Math.random()为java.lang.Math类中的静态方法
 
习题2 找出落单的那个数
 
**题目：**请问在一个数组里除了某一个数字之外，其他的数字都出现了两次。如何找出落单的那个数？
 
​ 思路：
 
对数组进行连续异或，重复的都会被消除，最后剩下的就是落单的数
 
public class 落单的数 {
    public static void main(String[] args) {
        int N=11;
        int[] arr=new int[N];

        //以回文数的形式给数组赋值(为了该数字出现两次）
        for (int i = 0; i <(N/2) ; i++) {
           arr[i] =i;
           arr[N-i-1]=i;
        }
        arr[N/2]=N/2;
        //异或运算
        int x1=0;
        for (int i = 0; i  
第一个for为了以回文数的形式给数组赋值(为了该数字出现两次）
 
第一个for循环结束后arr={1,2,3,4,5,6,5,4,3,2,1}
 
第二个for循环将数组中的元素以^的形式排列起来,并消除重复值
 
0^1^2^3^4^5^6^5^4^3^2^1
0^6=6
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5717223.html