MENU

LeetCode191. 位1的个数

July 9, 2018 • Read: 2581 • LeetCode阅读设置

image

思路:

  1. 对一个整数n,比如10,它的二进制是1010
  2. 将10减一变为9,9的二进制是1001
  3. 比较10和9的二进制数,对10减一操作就等于将10的二进制的最低位上的1以及后面的位取反,前面的数不变。

总结:

把一个整数减去1,再和原整数做与运算,会把该整数最右边1一个1变成0。那么一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。从而可以减少比较的次数

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0){
            n = n & (n-1);
            count++;
        }
        return count;
    }
}
Last Modified: May 12, 2021
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment