整數 二進制中1的個數
前兩天遇到這個問題，第一反應就是%2和>>1這兩個操作，
??大概思路：
??正數：%2，拿到原碼(補碼)的最右位，對于一個int型別的數進行32次判斷，這是比較簡單的理解，負數：雖然它的補碼需要原碼取反加一，但是原碼和補碼的共同點最右位是一致的,所以%2其實也是可以拿到補碼的最右位，
??所以這個代碼對于整數而言，都是行得通的，
int num = -1;
int count1 = 0;
for (int i = 0; i < 32;i++) {
if (num % 2 != 0) {
count1++;
}
num = num >> 1;
}
當然，這個思路差不多的方法還有
(((n >> i) & 1) == 1)
??按位與1，通過&1拿到最右位，>>31次，也可以計算出1的個數，
unsigned int n1 = -1;
??將負數通過自動型別的提升賦給一個無符號的整數n1，我們對于正數n1 &2和 >> 操作也一樣可以拿到1的個數 ( 原理：整數在計算機記憶體是以補碼形式存在 )
這些方法整個思路呢都是相似的，針對int型別的整數，對其補碼進行32次回圈操作，
當然，我看到了一個最經典的方法，n & (n-1)，
int n = -1;
int count = 0;
while (n) {
n = n & (n - 1);
count++;
}
printf("%d\n",count2);
剛開始看到這個n&n-1，真的是一臉懵逼，這都是哪跟哪，后面仔細的分析了下，的確也是這么一回事，給你們慢慢分析，逐字決議，
??還是從正數負數分開分析 (32位太長，我們用8位代替)
??正數：以紅色框1為基準，(n-1)操作，補碼從右往左開始，遇到1就停住，減去，也就是紅色框1右邊的0全部變成1，左邊的原封不動，所以n&n-1也就是拿到了1左邊的數，count++,n重新進入回圈判斷，如果不為0，就代表補碼還存在1，重復操作，
(用原碼去理解，正數原碼補碼都一樣）
??負數：我們要知道負數的補碼是原碼取反加一，對于一個(負數-1) & 負數，就很難去理解，所以我也是通過圖片幫助理解，
??首先我們要知道 n-1在計算機底層的操作是n + (-1)，我們通過一個數與32位1，也就是-1的補碼形式，進行相加，溢位之后，就是n-1的效果，這里必須要再次感嘆計算機的創造者，
??n-1：依然以紅色框1為基準，與-1的補碼進行相加，很清楚的可以看到，右邊開始，第一個1，也就是紅色框1變為0，紅色框1左邊的數都原封不動，為什么會這么神奇呢？ 其實可以這樣理解，n與-1相加，對于紅框到最左邊的1，都可以看成紅框數1與-1所對應位置的1相加，產生的進1，與-1前面的所有1相加，溢位，本質上就是紅框數1變0，左邊部分不變，右邊0變1，
??因此，n&（n-1也）是一樣拿到了紅色框1左邊的原封不動的數，和正數也是同樣的原理，
（補碼的形式，-1也用8位代替）
??總結一下，這個方法對于正負數都是一樣的，以補碼右邊開始第一個1位基準,（n-1）保持該1的左邊原封不動，右邊取反，再&按位與運算，count++，新的n進行判斷，n !=0 則代表里面還有1，n==0則代表n里面沒有1,結束回圈，
這個方法對于一個int型別的數，不需要32次回圈執行，補碼里面有幾個1就執行幾次回圈!!!
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257102.html
標籤：其他
上一篇：暢通工程2