位运算

leetcode136 只出现一次的数字

class Solution {
    public int singleNumber(int[] nums) {
        //使用异或运算，异或运算具有以下性质
        //任何数与0异或，结果为本身
        //同一数异或，结果为0
        //异或运算满足结合律和交换律
        int res=0;
        for(int num:nums){
            res ^=num;
        }
        return res;
    }
}

leetcode 137只出现一次的数字 II

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int i=0;i<32;i++){
            int count=0;
            for(int j=0;j<nums.length;j++){
                count+=nums[j]>>i&1;
            }
            if(count%3==1){
                res |= 1<<i;
            }
        }
        return res;
    }
}

leetcode260 只出现一次的数字III

class Solution {
    public int[] singleNumber(int[] nums) {
        //本题关键是将数组分为两组，两个出现一次的元素分别被放在不同组，且相同的元素            在同一组
        int m=0;//m为两个元素的异或结果
        int index=1;
        int a=0,b=0;
        for(int i=0;i<nums.length;i++){
            m^=nums[i];
        }
        while((index&m)==0){
            index<<=1;
        }
        for(int num:nums){
            if((num&index)!=0){
                a^=num;
            }else{
                b^=num;
            }
        }
        return new int[]{a,b};
    }
}

剑指 65 不用加减乘除做加法

class Solution {
    public int add(int a, int b) {
        while(b!=0){
            int temp = (a&b)<<1;//表示进位
            a ^= b;//表示非进位和
            b=temp;
        }
        return a;
    }
}

剑指offer15 二进制中1的个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res=0;
        int index =1;
        for(int i=0;i<32;i++){
            if((n&index)!=0) res++;
            index<<=1;
        }
        return res;       
    }
}