劍指offer之二進制位1的個數

1.求一個整數的二進制表示中有幾個1

• 基礎補習：

  左移m<<n,表示m左邊n位直接丢棄,同時在右側補n個0

  右移m>>n,表示右邊n位直接丢棄,負數左側補n個1，正數和無符号數都是左側補n個0

2.右移解法(錯誤的)

不斷把數字右移1位，和1做&運算，判斷最右側一位是否是1
           

int NumberOf1(int n)
{
    int count = 0;
    while(n)
    {
        if(n&1)count ++;
        n = n >> 1; 
    }
    return n;
}
      

當輸入負數時，右移時，每次左側補1，死循環
           

3.左移解法（正确，但不是最優）

int NumberOf1(int n)
{
    int count = 0;
    unsigned int flag = 1;
    while(flag)
    {
        if(n & flag)count ++;
        flag = flag << 1;
    }
    return count;
}
      

從右往左，依次檢測n的每一位是否是1.flag由于是無符号數，當1移到最高位時，仍然有效（flag條件為true）,當越過最高位時，flag全部是0,while循環結束。循環次數取決于整數的二進制位數，如果32位整數，那麼循環32次
           

4.更優解法

• 分析 整數n減去1,如果最後一位是1,那麼最後一位設為0

  如果最後一位不是1，從右向左找，找到第一個1，設為0，然後後續位置取反，想想國小的借位減法。

  比如二進制數1100減去1,從右往左找到第一個1（紅色那個），再把紅色以及後面的位取反，減法後變為1011，然後1100 & 1011 = 1000剛好損失最後一個1

  總結：整數n減去1，找到從右往左第一個位置是1的位，把這個位置以及右側按位取反

  那麼n & (n-1),每次損失最右側的一個1

• 代碼

  int NumberOf1(n)
  {
  int count = 0;
  while(n)
  {
      count ++; //能進入while，至少有個位是1
      n = n & (n-1);//損失最右側一個1位
  }
  return count;
  }
        

  這個數有個位是1,循環幾次

  5.更多應用

• 一條語句判斷一個整數是不是2的整數次方，由于2的整數次方，二進制隻有一個位是1，其他位都是0，n&(n-1)之後結果必定為0
• 兩個整數m,n,求m二進制中多少個位于n不同。二進制位不同，想到異或，先求m和n的異或，mn有幾個位不同,異或值就有幾個位是1，然後數1的個數