二進位中1的個數

二進位中1的個數

輸入一個整數，輸出該數二進位表示中1的個數。

常規思路：把數字n與1進行與運算，判斷n的最低位是不是1。

接著把1左移一位，繼續與數字n做與運算，判斷n的次低位是不是1。

參考代碼：

root@gt:/home/git/Code# ./a.out 2root@gt:/home/git/Code# cat num1.c #include <stdio.h>int num1(int num){ int count = 0; unsigned int flag = 1; while(flag) { if(flag & num) { ++count; } flag <<= 1; } return count;}int main(){ int num = 9; int count = 0; count = num1(num); printf("%d
",count); return 0;}

驚喜解法：把一個整數減去1,再和原來的整數做與運算，會把該整數最右邊的1變成0。

不停的對該整數進行這樣的運算，最後該整數將變成0。

驚喜代碼：

root@gt:/home/git/Code# ./a.out 2root@gt:/home/git/Code# cat num1.c #include <stdio.h>int num1(int n){ int count = 0; while(n) { n = (n - 1) & n; count++; } return count;}int main(){ int n = 9; int count = num1(n); printf("%d
",count); return 0;}

擴展：

1.判斷一個整數是不是2的整數次方。

- 一個整數如果是2的整數次方，那麼它的二進位表示中有且只有一位是1。

2.輸入2個整數m和n，計算需要改變m的二進位中的多少位才能得到n。

- 第一步求這2個數的異或，第二步求異或中1的個數。

3.把一個整數減去1之後，再和原來的整數進行位運算，得到的結果相當於把整數的二進位中最右邊的1變成0.很多二進位問題都可以用這個思路求解！！

推薦閱讀：