一、位运算

用1做&是保留，用0做&是消除

  1. 具体应用
    1. 判断奇偶数
      1. x & 1 == 0为偶， ==1 为奇（偶数最后一位为0，奇数最后为1
    2. 获取某个数x 二进制形式上的第a位是0or1
      1. x>>(a-1) & 1
      2. x & 1<<(a-1)
    3. 交换两个整数变量的值
      1. int a=1,b=2;

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

  1. 异或性质

    1. 交换律
    2. 结合律
    3. 对任何数， x^x = 0 ,x ^0 = x,与自己求异或为0，同0求异或为自己
    4. 自反性 A^B^B = A^0=A

    5. image.png
      1. 思路：直接全部异或上(1^2^…^1000)最后出来的那个数就是重复的x
      2. 理由：x^x^A = A，所以所有的都重复两遍，那么重复的那个就是三遍，就是仍然是本身。
    6. image.png
      1. 思路：和上一题一样，之间再异或两次次，那么某一个数字就是异或三次，其余的都是异或六次变成0.
      2. 理由：x^x^A = A

    7. image.png

      1. 思路：

        1. 直接变成二进制的，然后一个个数到底有多少个

          1. 第一种是挪动1
          2. 第二种是挪动x（忽略符号，高位补0的形式），和1进行比较
            1. //方法1
            2. public int howMany1_1(int x){
            3. int count = 0;
            4. for(int i = 0;i < 32 ; i++ ) {
            5. //eg. 00100和00001，00010...逐个进行比较,看是否== 00001，00010...
            6. if ( (x & (1<<i)) == (1<<i)){
            7. count++;
            8. }
            9. }
            10. return count;
            11. }
            12. //方法2
            13. public int howMany1_2(int x){
            14. int count = 0;
            15. for(int i = 0;i < 32 ; i++ ) {
            16. //eg. 00100变成00010,00001之后和00001逐个进行比较,看是否==
            17. if ( ((x>>>i) & 1) == 1){
            18. count++;
            19. }
            20. }
            21. return count;
            22. }

        2. (x-1) & x 可以将x的低位的1去掉，最终只要看做了几次这样的运算

          1. 举例：x = 10100 , x-1 = 10011,那么 (x-1) & x = 10000,就相当于去掉了一个1.
            1. public int howMany1_3(int x){
            2. int count = 0;
            3. //这里，如果x是0，则无1，若x>0，则一定有1，那么就是从1开始计算，不用考虑无1的情况
            4. while(x != 0){
            5. x = (x-1)&x;
            6. count++;
            7. }
            8. System.println.out(count);
            9. return count;
            10. }

    8. image.png

      1. 思路：找规律，2的整数次方的二进制内只有一个1.再结合第三题。

  2. 一些&的题目

    1. 将整数的奇/偶位互换
      eg：9 ：1001 ，互换后为0110，是6，（指12位换，34位换）
      1. 思路：把奇数位取出来，把偶数位取出来，然后一个偶数往右，奇数往左，一个异或就行
        把奇数位取出的方法：将x 和0101010101做&运算。由&来保留所有的奇/偶数位
        eg: 1001&0101 = 0001,只保留了奇数项，偶数项全为0（保留偶数项同理，将其与1010&)
        1. //代码就很简单了
        2. int ouShu = 0xaaaaaaaa & x;
        3. int jiShu = 0x55555555 & x;
        4. return (ouShu>>1) ^ (jiShu<<1)

  3. image.png

    1. 首先分析整数的变成二进制的方法：不断对2取模，然后/2,往前面放。
      eg：10是1010，先%2余0再/2变成5，然后%2余1再/2变成2，然后%2余0再/2变成1，然后%2余1再/2变成0.最后是从右向左排列。
    2. 然后分析小数的取法：比如0.625，先2变成1.25，取1，再0.252 = 0.5，取0，再0.5*2 = 1，取1，结束
      1. public static void BinaryFloat(double x) {
      2.   StringBuilder s = new StringBuilder("0.");
      3.   //此处条件换成x>0也可。
      4.   while (x != 0) {
      5.       //乘二
      6.       x = x * 2;
      7.       //取整
      8.       if (x >=1){
      9.           x = x-1;
      10.           s.append("1");
      11.       }else s.append("0");
      12.   }
      13.   //如果长度大于32位（加上0.之后就是34位
      14.   if (s.length() > 34) {
      15.       System.out.println("ERROR");
      16.       return;
      17.   }
      18.   System.out.println(s);
      19. }

  4. image.png

    1. 思路：2个相同的二进制做不进位加法，结果为0，10个相同的十进制数做不进位加法结果为0，k个相同的k进制数做不进位加法，结果为0。因此，将所有的数都变成k进制，然后所有的数相加就行。
    2. 方法。Integer.parseInt( String s, int radix )，做不进位加法。方法：所有的数相加之后对k取余，就是不进位的加法的结果。

      二、递归

  5. 汉诺塔问题

    1. 结论：Hn = 2^n - 1（次数）
    2. 思路：一根柱子为辅，另外两个柱子上是目标柱和原始柱。
      1. //help为辅助的柱子（就是在函数调用时一开始为空的柱子
      2. //from为起始
      3. //to为终点
      4. //N为数量
      5. public static void printHanoiTower (int N,String from,String to,String help){
      6. if(N==1){
      7.   System.out.println("将"+N+""从+from+"移动到"+to+"辅助为"+help);
      8. }
      9. else {
      10.   printHanoiTower(N-1 ,from ,help,to);//移到辅助的柱子上
      11.   System.out.println("将"+N+""从+from+"移动到"+to+"辅助为"+help);//最底下那个盘移到目标柱上
      12.   printHanoiTower(N-1 ,help ,to,from);//移到目标上
      13. }
      14. }
      image.png