[Facebook] Given an integer, add its binary number by 1 without “+” 整数加一, 不用加号.

一亩三分地上看的,不是我的面试, 写一个吧…感觉不是很难

  public int add(int n) {
        for(int i = 0; i < 32; i++) {
            if (((1 << i) & n) == 0){      //until we find the first 1 bit
                n = n | (1 << i);
                break;
            }
            else
                n = n & ~(1 << i); // clean bits
        }
        return n;
    }

算法思路:

1. i是游标, (1 << i) 就是对n的每个位从右往左扫.
2. if判断的是, 如果这位是 0, 那么就变成1.
3. 如果不是, 那么这位肯定是1, 那么在未来的某次循环需要把0 变成1时, 这位肯定要变成0, 所以如果是1 就是0.
4. 这里用的是clean bits的方法. 先去取反做mask, 再取与(and).