算法笔记，

一 位1的个数

 代码：

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

思路: 判断一个数字x二进制下第i位是否为1可以用if(((1<<(i-1))&x)将1左移i-1位，得到的数只有第i位是1，其他位都是0的二进制数，然后与输入的数做与运算，只有当n的第i位为1得到的解果才不为0，这样就可以判断n的第i位是否为1。

 二  扬辉三角 

class Solution {
    public List<List<Integer>> generate(int numRows) {
   
   List<List<Integer>> out=new ArrayList<List<Integer>>();
   for(int i=0;i<numRows;i++) {
	   List<Integer> in=new ArrayList<Integer>();
	   for(int j=0;j<=i;j++) {
		   if(j==0||j==i) {
			   in.add(1);
		   }
		   else {
			   in.add(out.get(i-1).get(j-1)+out.get(i-1).get(j));
		   }
	   }
	   out.add(in);
   }
   return out;
    }
}

 此题中每行左右两个数都是1，第 n行的第 i个数等于第 n−1 行的第 i−1 个数和第 i个数之和

三 只出现一次的数字

class Solution {
    public int singleNumber(int[] nums) {
    int a=0;
    for(int i:nums){
        a^=i;
    }
    return a;
    }
}

思路： 此题运用到异或运算的性质。任何数和 0 做异或运算，结果仍然是原来的数；任何数和其自身做异或运算，结果是 0；异或运算满足交换律和结合律，即a^b^a=b^(a^a)=b^0=b;

所以遍历数组中所有数让它们做异或运算，由于除了一个数其他两个数都出现两次，所以所有数异或得到的结果就是只出现一次的那个数!