一、位运算的奇巧淫技
先来学习一下位运算
&（与），|（或），^(异或)，~(非/取反)
>>和<<运算符将二进制进行右移或者左移操作
>>>运算符将用0填充高位；>>运算符用符号位填充高位，没有<<<运算符
对于int型，1<<35与1<<3是相同的(int型只有32位)，而左变的操作数是long型时需对右侧操作数模64
一些技巧：
（1）、与：都为1结果为1， 或：有一个为1结果为1， 异或：相同为0、不同为1
（2）、x&1=1 x为奇 ；x&1=0 x为偶 （二进制最低位）
1、唯一成对的数
题目：找出唯一成对的数，1-1000这1000个数放在含有1001个元素的数组中，只有唯一的一个元素值重复，其他均只出现一次。每个数组元素只能访问一次，设计一个算法，将其找出。要求：不用辅助存储空间。
如：int[] ={1,2,3,4,5,3} ---->3
我的思路：我也是第一次开始练算法，拿到题还是一脸懵逼，于是如上面所示，先想着是就6个数吧，也别多了，不然绕不清楚。题目显示不让用辅助存储空间，意思就是我不可以在开辟另一个数组，于是就更陷入沉思了。怎么想怎么和位运算没啥子联系，只是想到最暴力的方法，（以上面那个小数组为例子）2与1比较，不等，把1扔到外面放入单独一个盒子；3与2比较，不等，把2扔到外面放入单独一个盒子；以此类推，直到3和5比较，也不等，扔出去时候发现之前有个3与之相等，便匹配在一起。再深入想了一下，我头尾相比，来个69比较法（独创秘方，直通幼儿园）？好像变得快了一些，尾部不变，从头开始，1与3比较，不等out；2与3比较，不等out，三下出来了答案。但是题目1000个数字，不可能如此侥幸吧，该怎么处理呢，于是乎还是看了视频讲解。
讲解思路：我们想的是把不重复的数消掉，but--->AA=0,B0=B --->AABCC=B--->消除重复，我们该如何处理呢？看个式子（12k.....k1000）（12...1000），卧槽顿时恍然大悟，在（12...1000）取不重复的排法，那么其中必有一个k值，那么根据异或属性，相同为0、不同为1，3个k异或最后只剩下一个k，输出即可。
public class Solution{
public static void main(String[] args) {
//首先创建数组，遍历
int n = 1001;
int[] arr = new int[n];
for(int i=0;i<arr.length;i++) {
arr[i] = i+1;
}
//在这里，最后一个数字我们给它随机数k，因为这里只有唯一一个重复
arr[arr.length-1] = new Random().nextInt(n-1)+1;
//随机下标
int index = new Random().nextInt(n);
//涉及两个方法，需自定义
swap(arr,index,arr.length-1);
print(arr);
int x = 0;
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)
}
public static void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void print(int[] arr) {
System.out.println(Arrays.toString(arr))
}
}
2、找出落单的那个数
题目：一个数组里除了某一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现了一次的数字。
如：int[] arr ={1,2,3,4,5,5,4,3,2} --->输出1
我的思路：出现了两次，那我就学以致用吧，这里用^ ，如上（123455432）,必然最后就输出1了。
public class Solution2 {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,5,4,3,2};
int x = 0;
//遍历数组
for (int i=0;i<arr.length;i++) {
//任何数与 0 异或等于它本身
x = x^arr[i];
}
System.out.println(x);
}
}
3、二进制中1的个数
题目：实现一个函数，输入一个整数，输出该数二进制表示中1的个数
如：9的二进制1001，输出2
我的思路：就是数出1的个数，那么就通过位运算来思考，设该数为x，与上（x<<i）,i为左移的个数，然后与后得到的result>>i，相当于返回，其返回值为1，我这里设一个count，用count++计数即可。
讲解思路：可能我的算是最原始的思路吧，分享一个很神奇的思路，还是以9为例---1001，我们不断消去它最低位的1，那么消了几次就输出多少。实现也很简单，就只用将1001&1000（9-1）--->1000&0111--->0000停止，由此可见，我们只花了两步消去了所有的1，所以返回count=2；总结起来就是，x&（x-1）就是在不断消去其最低位的1。
public class Solution3 {
public static void main(String[] args) {
//这里有需要可以用Scanner方法
int x = 9;
int count = 0;
//不要忘记先转化成二进制
System.out.println(Integer.toBinaryString(x));
//int型有32位
for (int i=0;i<32;i++) {
if (((x&1<<i)>>i)==1) { //还可以写出 (x&1<<i)==(1<<i)
count++;
}
}
System.out.println(count);
/*
写一下那个神奇代码
int count = 0;
while(x!=0) {
x = (x&(x-1));
count++;
}
System.out.println(count);
*/
}
}
4、是不是2的整数次方
题目：用一条语句判断一个整数是不是2的整数次方。（这里只考虑正数）
我的思路：2、4、8、16、32、64、128、256、512、1024 ... 没啥思路啊
讲解思路：转化为二进制，停，好，我先试一下 0010、0100、1000、10000，奇怪咯，这2的整数次方，好像嘿嘿嘿二进制就只有1个1啊，用昨天的神奇代码x&(x-1)瞬间实现。再重复一下x&(x-1)的思路，逐步消去最低位的1，这里我们只要一步到位使x转为0，那么x就是2的整数次方。
public class Solution4 {
public static void main(String[] args) {
Is(1024);
Is(1000);
}
private static void Is(int x) {
//这里我们转为二进制可以观察一下
System.out.println(x+"二进制数为："+Integer.toBinaryString(x));
if (((x&(x-1))==0)) {
System.out.println(x+"是2的整数次方");
}else {
System.out.println(x+"不是2的整数次方");
}
}
}
5、0~1间浮点实数的二进制表示
题目：给定一个介于0~1间的实数，如：0.625，类型为double，打印它的二进制表现形式（0.101），因为小数点后的二进制分别表示为（0.5，0.25,0.125 ...）。如果该数字无法精确地用32位以内的二进制表现，则打印ERROR。
我的思路：赶紧打开IDEA看看double的包装类Double的方法，结果当然大失所望，只存在Double.toHexString() 的方法，即转为16进制，没有转2进制 。那肯定需要我们自己来写一个方法，在想方法时，我还想过要不把这个16进制转为2进制？脑子里仍没有具体思路，看看讲解。
讲解思路：整数转二进制——÷2，取余留商 ； 小数转二进制——×2，每次循环扣掉整数部分，然后继续乘2。例如上述所说0.625×2--->1.25 去掉整数部分--->0.25×2--->0.5×2--->1.0 去掉整数部分--->0.0不在循环-->每次去掉部分得到二进制数0.101。看来是大一学的都还给老师了，这都忘记了emmm，开始撸代码。
public class Solution5 {
public static void main(String[] args) {
double x = 0.625;
//这里需要用到StringBuilder的append方法
StringBuilder sb = new StringBuilder("0.");
while (x>0) {
double d = x*2;
if (d>=1) {
sb.append("1");
x = d-1;
}else {
sb.append("0");
x = d;
}
if (sb.length()>34) {
System.out.println("ERROR");
return;
}
}
//连接打印成二进制数
System.out.println(sb.toString());
}
}
6、出现k次与出现一次
题目： 数组中只有一个数出现了1次，其他的数都出现了K次，请输出只出现了一次的数。
我的思路：本章节的压轴题还是不一样啊，先仔细回想一下前面的知识点，说白了无非就是运用进制和位运算。还是先假设int[] nums={1,2,2,3,3}显然当k=2则输出1。那么接下来就是怎么运用本章所学的知识来解了，首先想的肯定是异或，乍一看，诶运用在上述nums数组，直接输出1，真香。但是，若arr={1,2,2,2,3,3,3}这咋解决，异或也没啥用吧。那就先考虑集合，一个个数数总是可以吧，毕竟活人不能被尿憋死。
import java.util.*;
public class Solution6 {
public static int getTheOne(int[] nums) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i=0;i<nums.length;i++) {
if (map.containsKey(nums[i])) {
int num = map.get(nums[i]);
num++;
map.put(nums[i],num);
}else {
map.put(nums[i],1);
}
}
Iterator<Integer> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
int key = iterator.next();
if (map.get(key)==1) {
return key;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = {1,2,2,2,3,3,3};
System.out.println(getTheOne(nums));
//输出1
}
}
讲解思路：2个相同的2进制数做不进位加法，结果为0；10个相同的10进制做不进位加法，结果为0。--->k个相同的k进制数做不进位加法，结果为0。这个非常人所能发现也。。。然后Java在这里很友好的提供了一个手工取余法，即任意进制转换法---Integer.toString(i,radix)；最后通过不进位加法得到我们所剩的唯一一个k进制，还需要把它转换为10进制。我给个中肯的评价，思想很高级，实现很麻烦，但很适合奇葩进制哈哈。在这里贴出代码，仅供思考与学习吧。暂且我还没有捋顺。
public class Solution7 {
public static void main(String[] args) {
int[] nums = {2,2,2,9,7,7,7,8,8,8,3,3,3,0,0,0};
int len = nums.length;
char[][] kRadix = new char[len][];
int k = 3;
int maxLen = 0;
//转成k进制字符数组
//对每个数字
for (int i=0;i<len;i++) {
//求每个数字的三进制字符串并翻转，然后转为字符数组。
kRadix[i] = new StringBuilder(Integer.toString(nums[i],k)).reverse().toString().toCharArray();
if (kRadix[i].length>maxLen) {
maxLen = kRadix[i].length;
}
}
int[] resNum = new int[maxLen];
for (int i=0;i<len;i++) {
//不进位加法
for (int j=0;j<maxLen;j++) {
if (j>=kRadix[i].length) {
resNum[j] += 0;
}
else {
resNum[j] += (kRadix[i][j]-'0');
}
}
}
int res = 0;
for (int i=0;i<maxLen;i++) {
res +=(resNum[i]%k)*(int)(Math.pow(k,i));
}
System.out.println(res);
//输出9
}
}
第一章【完】