【問題描述】[簡單]

請實現(xiàn)一個函數(shù)，輸入一個整數(shù)（無符號數(shù)），輸出該數(shù)二進制表示中 1 的個數(shù)。例如，把 9 表示成二進制是 1001，有 2 位是 1。因此，如果輸入 9，則該函數(shù)輸出 2。示例 1：輸入：00000000000000000000000000001011 輸出：3 解釋：輸入的二進制串 00000000000000000000000000001011 中，共有三位為 '1'。 示例 2：輸入：00000000000000000000000010000000 輸出：1 解釋：輸入的二進制串 00000000000000000000000010000000 中，共有一位為 '1'。 示例 3：輸入：11111111111111111111111111111101 輸出：31 解釋：輸入的二進制串 11111111111111111111111111111101 中，共有 31 位為 '1'。

【解答思路】

1. 逐位判斷

時間復雜度：O(logN) 空間復雜度：O(1)

public int hammingWeight(int n) {int res = 0;while(n != 0) {res += n & 1;n >>>= 1;}return res;}

2. 巧用 n&(n?1)

時間復雜度：O(N) 空間復雜度：O(1)

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

【總結】

1.只能針對正數(shù)

public int hammingWeight(int n) {int num=0;while(n!=0){if(n%2 ==1){num++;}n/=2;}return num;}

2. 位運算

異或運算（^）
運算規(guī)則：0^0=0； 0^1=1； 1^0=1； 1^1=0；
即：參加運算的兩個對象，如果兩個相應位為“異”（值不同），則該位結果為1，否則為0。
5 ^ 1 = 0101 ^ 0001 = 0100 = 4
5 ^ 3 = 0101 ^ 0011 = 0110 = 6
用法
翻轉指定位 對應位異或1
X=10101110，使X低4位翻轉，用X ^0000 1111 = 1010 0001即可得到。
2.兩個數(shù)是否相等 ==0
5 ^ 5 = 0101 ^ 0101 = 0000 = 0

與運算（&）
運算規(guī)則：0&0=0; 0&1=0; 1&0=0; 1&1=1;
即：兩位同時為“1”，結果才為“1”，否則為0
5 & 1 = 0101 & 0001 = 0001 = 1
5 & 2 = 0101 & 0010 = 0000 = 0
用法
取指定位 對應位與1
設X=10101110，
取X的低4位，用 X & 0000 1111 = 00001110 即可得到；

或運算（|）
運算規(guī)則：0|0=0； 0|1=1； 1|0=1； 1|1=1；
即 ：參加運算的兩個對象只要有一個為1，其值為1
用法：
指定位置置1 對應位或1
將X=10100000的低4位置1 ，用X | 0000 1111 = 1010 1111即可得到

取反運算（~）
運算規(guī)則：~1=0； ~0=1；
即：對一個二進制數(shù)按位取反，即將0變1，1變0

帶符號左移運算（<<）
若左移時舍棄的高位不包含1，則每左移一位，相當于該數(shù)乘以2(右邊補0)
3 << 1 = 0011 <<1 = 0110 = 6
帶符號右移運算（>>）
正數(shù)操作數(shù)每右移一位，相當于該數(shù)除以2
(左補0 or 補1得看被移數(shù)是正還是負)
5 >> 1 = 0101 >> 1 = 0010 = 2
5 >> 2 = 0101 >> 2 = 0001 = 1
-14 >> 2 = 11110010 >> 2 = 11111100 = -4
無符號右移運算（>>>）
5 >>> 1 = 0101 >>> 1 = 0010 = 2
-14 >>>2 =11111111 11111111 1111111111110010 >>>2 = 00111111 11111111 1111111111111100 = 1073741820
移位總結

• 正數(shù)的左移與右移，負數(shù)的無符號右移，就是相應的補碼移位所得，在高位補0即可。
• 負數(shù)的右移，就是補碼高位補1,然后按位取反加1即可。

3. 位運算 判相等異或^ 取位與&1 置位 或|1

轉載鏈接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/solution/mian-shi-ti-15-er-jin-zhi-zhong-1de-ge-shu-wei-yun/

總結

以上是生活随笔為你收集整理的[剑指offer][JAVA]面试题第[15]题[二进制中1的个数][位运算]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。