剑指Offer:二进制中1的个数

题目描述

输入一个整数,输出该数二进制表示中 1 的个数。

n&(n-1)

该位运算去除 n 的位级表示中最低的那一位。

[v_act]n : 10110100
n-1 : 10110011
n&(n-1) : 10110000[/v_act]

时间复杂度:O(M),其中 M 表示 1 的个数。

public int NumberOf1(int n) {
    int cnt = 0;
    while (n != 0) {
        cnt++;
        n &= (n - 1);
    }
    return cnt;
}

Integer.bitCount()

public int NumberOf1(int n) {
    return Integer.bitCount(n);
}
本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 剑指Offer:二进制中1的个数

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多