【数算1.1】异或运算练习题目

ゞ浴缸里的玫瑰 2022-10-08 05:51 115阅读 0赞

### 题目一：不用额外的变量去使得两个数交换。 ###

a = a ^ b;  
b = a ^ b;  
a = a ^ b;

### 题目二：一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数 ###

public static void main(String[] args) {
        
            int[] b = {
        1, 8, 9, 3, 1, 8, 9, 3, 9, 6, 6};
            
            System.out.println(findOddNum(b));
        }
    
        public static int findOddNum(int[] arr) {
        
            // 验证数据是否可靠
            if (arr == null || arr.length == 0 ){
        
                return -1;
            }
            int temp = 0;
            for (int ele : arr) {
        
                temp ^= ele;
            }
            return temp;
        }

测试运算结果：  
![在这里插入图片描述][20210620193944296.png]

### 题目三：怎么把一个int类型的数，提取出最右侧的1来 ###

利用算法：N & (~N + 1)

public static void main(String[] args) {
        
            int[] a = {
        1, 2, 4, 3, 5, 6};
            int[] b = {
        1, 8, 9, 3, 0, 6};
    
            int c = 6;
            System.out.println(getLastOne(c));
        }
    
        public static int getLastOne(int num) {
        
            return num & (~num + 1);
        }

### 题目四：一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么 找到并打印这两种数 ###

public static void printOddTimesNum2(int[] arr){
        //只有两个数出现了奇数次
          int eor=0;
          for(int cur:arr){
        
              eor^=cur;
          }
          //eor=a^b
          //eor!=0
          //eor必然有一个位置上是1
          // 0110010000
          // 0000010000 【小算法】
          int rightOne=eor&(~eor+1);//提取出最右的1
          int eorT=0;//eor'
          for(int cur:arr){
        
              if((cur&rightOne)==1){
        
                  eorT^=cur;
              }
          }
          System.out.println(eorT+" "+(eor^eorT));
      }

思路：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70]  
实际例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 1]

### 计算一个二进制数中有几个1？ ###

int count = 0;
    while ( n != 0 ) {
        
    	right = n & ( ~n + 1 );
    	count++;
    	n ^= right; //抹去最右边的1
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 2]

[20210620193944296.png]: /images/20221005/ca8240fda0ce4248a5be987d4e737619.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70]: /images/20221005/c263febfa9a542109fe595314b3a3dcb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 1]: /images/20221005/2d8d5cd0a3d74fea95d80f47898d3f69.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgwMTQxOA_size_16_color_FFFFFF_t_70 2]: /images/20221005/1d79deb76f924c879b347add6c1edfa2.png