1. 二进制
Java数值运算过程中都是先将十进制转换为二进制然后再进行运算,再把二进制数据转换为十进制展现给用户。二进制运算规则如下:
对于有符号的而言,最高位为符号位,0表示正数,1表示负数.
假设有一段二进制如下
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
那么通过如上的二进制,我们就可以根据运算得到 2的4次方 加上 2的平方,得到的结果是 16 + 4 = 20.
那么取反就得到如下:
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
2. 二进制的移动(>> 和 <<)
还是参照上方的二进制,我们已经知道了表示的是20. 那么如果我们将 20左移2位会得到什么结果呢? 20 >> 2。 实际上20 左移2位以后,空出来的部分用0补全,即得到以下:
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
通过计算:2的平方 加上1 我们知道: 20 >>2以后得到的数值为5.
同理,我们可以知道 20 << 2 , 就是 2的6次方 加上 2的4次方,得到的结果为:80
3. 逻辑与(&)和逻辑或(|)
如果我们想知道 8&9 和 8|9 分别得到什么结果呢?通过二进制来分析就是 &必须两个都一样,二进制位才能得到1. 而逻辑或(1)是任意一个有1,结果就可以出现1
下面我们使用省略的形式,前面的0都省略,只保留后面实际有意义的二进制。
8的二进制 | 0 | 1 | 0 | 0 | 0 | |
9的二进制 | 0 | 1 | 0 | 0 | 1 | |
8&9(取相同值) | 0 | 1 | 0 | 0 | 0 |
根据结果我们可知, 8&9得到的结果是8 |
8|9(逢1就取1,没1取0) | 0 | 1 | 0 | 0 | 1 | 8|9得到的结果是9 |
4. 异或(^),总结一句话就是:无进位相加。 即2个二进制相加,如果两个都有1的部分,即 1+1 =0,不向高位进1。那么 8^9的结果是什么呢?
8的二进制 | 0 | 1 | 0 | 0 | 0 | |
9的二进制 | 0 | 1 | 0 | 0 | 1 | |
8^9的结果 | 0 | 0 | 0 | 0 | 1 | 计算结果为1 |
题目1:给你一个整数,要求打印出来对应的二进制
其实,就是利用二进制的移动和逻辑与(&)实现
public static int[] print(int a) { int[] arr = new int[32]; for (int i =31; i >= 0; i--) { System.out.print((a & (1 << i)) == 0 ? "0" : "1"); arr[i] = (a & (1 << i)); //另一种写法 //System.out.print(((a >> i) & 1) == 0 ? "0" : "1"); //arr[i] = ((a >> i) & 1); } System.out.println(); return arr; }
题目2:给你一段二进制信息,要求打印出对应的整数
//二进制数组转整形 public static void printInt(int[] arr) { int ans = 0; for (int i = arr.length -1; i >=0; i--) { if (arr[i] != 0){ ans |= 1 << i; } } System.out.println("二进制转化为数字的值为 : "+ ans); }
题目3:假设a=, b =9,不用任何变量,交换这连个变量的值。
此题目考查的是对异或(^)的理解,我们知道异或运算有细化有2大性质,即:
性质1: 0 ^ N = N
性质2: N ^ N = 0
性质概括:异或运算,就是无进位相加
代码实现如下:
a = a ^ b; b = a ^ b; a = a ^ b;
要理解异或运算,我们需要把 a和b都当成对象的引用来理解,也就是a和b分别指向内存中的两个不同的对象。分析思路如下:
a = a ^b
b = a^b, 此时的a是a^b. 因此,此时的 b = a ^b^b. 也就是 b =a;
a = a ^b 此时的a是a^b. 因此,赋值后的 a = a^b^a. 也就是 a=b;
题目4:数组中只有一个数显了奇数次,其他数都出现了偶数次,请找到这个数。 假设数值为{2,3,4,5,6,7,2,3,4,5,6};
int[] arr = {2,3,4,5,6,7,2,3,4,5,6}; int eor = 0; for (int i=0; i<arr.length; i++) { eor = eor ^ arr[i]; } System.out.println("出现奇数次的数字为 :" + eor);
有了题目3的理解,相信理解这一题并不难
题目5:怎么把一个int类型的数,提取出最右侧的1来。此题就是考查二进制的取反加1知识. 我们知道8的二进制就是01000,那么获取到最右侧的1,结果还是1.
9的二进制 | 0 | 1 | 0 | 0 | 1 |
取反 | 1 | 0 | 1 | 1 | 0 |
取反加1 | 1 | 0 | 1 | 1 | 1 |
通过取反加1我们可以得到一个整数的二进制最右侧的1. 如果这个数是a=9, 那么最右侧的1就是 a&((~a) + 1). 因为 (~a) + 1 = -a。 所以最终获得的结果也可以表示位 a&(-a)
题目6:一个数组中有两种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这两种数,假设这个数组位{1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3};
public static List data(int[] arr) { List list = new ArrayList(); int eor = 0; //最终的结果,必然是 a ^ b, a和b分别代表这两个数 for (int i =0; i < arr.length; i++) { eor ^= arr[i]; }
//假设a是9, 二进制是01001
//假设b是15、二进制是01111
//a^b,得到的最终结果就是00110.
//下面代码是取到最右侧的1,也就是00010。这个二进制就可以做到区分a和b的最用。也就是a和b,从右往左,只有一个数第二位为1,另一个数必不为1 int rightOne = (eor & (-eor)); int temp1 = 0; //假设是第一个奇数的数字 for (int i =0; i < arr.length; i++) { //这一步很关键,因为前提是其他数都是出现偶数次, N ^ N =0, 0 ^ N = N, 所以此处的 //temp1必然是其中的一个数 if ((arr[i] & rightOne) != 0) { temp1 ^= arr[i]; } } list.add(temp1); //第一个 list.add(eor ^ temp1); //第二个 return list; }
题目7:一个数组中有一种数出现K次,其他数都出现了M次,M > 1, K < M,设计算法找到出现了K次的数。假设数组位{1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,1,2,3,4}; k =3; m =5;
public static int kTimes (int[] arr, int k, int m) { int[] help = new int[32]; for (int num : arr) {
//题目1,打印一个数的进制知识。此处的亮点是将二进制的每一位进行累加并存入数组 for (int i = help.length - 1; i >=0; i--) { help[i] += (num & (1 << i)); } } int ans = 0; for (int i = help.length - 1; i >=0; i--) {
//此处需要说明一下,因为只有其他数都是出现了m次,因此help[i]%必然为0
//而出现了k此的数,对应的数组必然是{......, 0,0,k,.....}类型的,k小于m. 因此这种出现了k次的数必不为0 if (help[i] % m != 0) {
//题目2,二进制转换为整数的知识 ans |= 1 << i; } } return ans; }
标签:面试题,题目,14,int,arr,二进制,算法,20,运算 From: https://www.cnblogs.com/chen1-kerr/p/17028940.html