🌕 🌗 191. 位1的个数

难度: 🌕 🌗

问题描述

---

解法 1

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        // 思路：
        // 循环右移 1 位
        int res = 0;
        while(n != 0) {
            if((n & 1) == 1) {
                res ++;
            }
            n >>>= 1;
        }
        return res;
    }
}

---

输出 1

---

解法 2 - 高级位运算

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        // 思路：
        // 借助 n & (n - 1) 公式
        // 通过这个公式，只要 n != 0 说明必有 1 的存在
        // 那么 n - 1 就可以将最低位出现的 1 变为 0，一直循环，直到 n == 0
        // 因此可以通过进行了几次循环，判断出有多少个 1
        // 例：
        // 01 10 11 00 01
        // 1. n & (n - 1) => 01 10 11 00 00
        // 2. n & (n - 1) => 01 10 10 00 00
        // 3. n & (n - 1) => 01 10 00 00 00
        // 4. n & (n - 1) => 01 00 00 00 00
        // 5. n & (n - 1) => 00 00 00 00 00
        int res = 0;
        while(n != 0) {
            n = n & (n - 1);
            res ++;
        }
        return res;
    }
}

---

输出 2