首页 > 编程语言 >算法14_位运算及经典面试题

算法14_位运算及经典面试题

时间:2023-01-05 23:23:02浏览次数:49  
标签:面试题 题目 14 int arr 二进制 算法 20 运算

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

相关文章