位运算的妙用

一、异或运算的妙用

1、性质

// 无进位相加且满足交换律和结合律
a ^ a = 0;
a ^ 0 = a;

// 若两数在内存当中的地址不同，相互交换可以写作
a = 1;
b = 2;
a = a ^ b;
b = a ^ b;
a = a ^ b;
注：若两数在内存当中地址相同，则会全部刷成0；

2.请问在一个数组中，如何找出唯一一个出现奇数次的数

int[] arr = new int[3]{1,2,2} 
int eor = 0;
// 和数组当中的每一位去异或
for(int i=0;i<arr.length;i++){
    aor ^= arr[i];
}
return eor;

二、与运算的妙用

1.怎么把一个int类型的数提取出最右侧的1来

-a = ~a+1;
a &= (-a); // 该步运算则可以取出int类型的数的最右侧的1;

2.请问在一个数组中，如何找出两个个出现奇数次的数

int[] arr = new int[3]{1,2,2} 
int eor = 0;
// 和数组当中的每一位去异或
for(int i=0;i<arr.length;i++){
    aor ^= arr[i];
}
// 最后异或结果就为 两个出现奇数次异或
aor = a ^ b;
// 抓取出一类中的数
onlyOne = 0;
// 找出最后一位为1的int类型的数
aor' = aor & (~aor + 1);
// 因为该数组可分为两组 根据以上左后一位为1的int类型的数
for(int i=0;i<arr.length;i++){
    if(aor & arr[i] != 0){
        onlyOne ^= arr[i];
    }
}
// 另外一个出现奇数次的数
aor ^= onlyOne;

3.该数组中仅有一个出现k次的数字 且 m>1, k<m;

// 该数组中仅有一个出现k次的数字 且 m>1, k<m;
    public static int onlyOneTimes(int[] arr, int k, int m){
        // 新建一个32位数组存放每个数字的标志位
        int[] t = new int[32];
        for (int i : arr) {
            for (int j = 0; j <= 31; j++) {
                t[j] += ((i >> j) & 1);
            }
        }
        int ans = 0;
        for (int i = 0; i < t.length; i++) {
            // 说明该数字在i位置为1
            if (t[i] % m != 0){
                ans |= (1 << i);
            }
        }
        return ans;
    }