剑指offer - 二进制中1的个数(Java实现)

题目链接：https://www.acwing.com/activity/content/introduction/31/group_buy/1815/

  思路一：当 n 为整数的时候我们直接对 2 取模就可以得到二进制中 1 的个数。对于负数来说，由于在计算机中负数是用其补码来存储的，所以我们在对 2 取模的过程中无法得到其补码。所以处理负数的时候我选择对这个负数取反，那么取反之后的值其二进制中 0 的个数即是这个负数的二进制的 1 的个数。

public class Solution {
    public int NumberOf1(int n) {
        int ans = n < 0 ? 32 : 0;
        boolean flag = n < 0 ? false : true;
        if(n < 0) n = ~n;
        while(n > 0) {
            if(n % 2 == 1) {
                if(flag) ++ ans;
                else -- ans;
            }
            n /= 2;
        }
        return ans;
    }
}

  思路二：二进制移位，我们可以让 x = 1 不断的左移来和目标值进行 & 操作，当 x = 0 时，此时说明已经比较了 32 和二进制位，此时就可以结束比较。

• 正数右移：高位补 0，低位丢弃
• 正数左移：高位丢弃，低位补 0
• 负数左移：高位丢弃，低位补 0
• 负数右移：高位补 1，低位丢弃，一直右移最后变成 -1

  public class Solution {
    public int NumberOf1(int n) {
      int ans = 0;
      int x = 1;
      while (x != 0) {
          if ((x & n) != 0) ++ans;
          x <<= 1;
      }
      return ans;
    }
  }

    思路三：思维，技巧， x & (x - 1) 可以将 x 的二进制中从低位开始的第一个出现的 1 置 0。我们可以这么想，如果是一个 的整数，那么我们在进行减一操作之后再和 x 进行 & 操作，此时的结果必然为 0。此时就可以想象出来我们在操作任意一个数字的时候，从低位开始出现的第一个 1，我们在进行减一操作之后在进行 & 操作，那么就可以把这一位置为 0 了。

  public class Solution {
    public int NumberOf1(int n) {
        int ans = 0;
        while(n != 0) {
            ++ ans;
            n = n & (n - 1);
        }
        return ans;
    }
  }