欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

位运算 -- 只出现一次的的数字

程序员文章站 2022-07-15 14:28:56
...

异或的两个值’相同为假,不同为真’。

交换两个整数的值时可以不用第三个参数
a = a ^ b ^ a = b
b = b ^ a ^ b = a
一个只出现一次的数字。

一个整型数组里除了一个数字之外,其他的数字都出现了偶数次。请写程序找出这个只出现一次的数字。

public int oneNumsAppearOnce(int [] array ){
    int num = 0;
    if(array.length>0){
        for(int i = 0; i<array.length; i++){
            num ^= array[i];
        }
    }
    return num;
}
两个只出现一次的数字。

一个整型数组里除了两个数字之外,其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。

先举出一个数组:{5,3,2,1,2,5}
最终异或结果:1^3 = 0010 ,第二位是1,则说明两个单独出现的数的第二位不同;
那么我们可以根据这个条件对数组进行分组:第二位为1的为一组,第二位为0的为一组;然后每一组进行异或,
得到的两个结果就是单独出现的俩个数!

//num1,num2分别为长度为1的数组 将num1[0],num2[0]设置为返回结果
public void twoNumsAppearOnce(int [] array,int num1[] , int num2[]) {
    int num = 0;
    if(array.length>0){
        int index = 0 ;
        num1[0] = 0;
        num2[0] = 0;
        for(int i = 0; i<array.length; i++){
            num ^= array[i];
        }
        for(int i = 0; i<32; i++){
            if( ( (num >> i) & 1 ) == 1 ){ //右移 找到第一个为1的位;
                index = i;
                break;
            }
        }
        for(int j = 0; j<array.length; j++){
            if( ((array[j] >> index) & 1 ) == 1){
                num1[0] ^= array[j];
            }else {
                num2[0] ^= array[j];
            }
        }
    }
    System.out.println(""+num1[0] + "+" + num2[0] + "");
}
相关标签: 位运算