剑指offer-11-二进制1的个数 试读

思路

• 十进制转换为二进制，进制转换：取模倒排法（高中数学），这里是%2,然后原数除以2
• 位运算，除2可以转换为右移1，n&1二进制最低位的数字
• lowbit函数，在树状数组结构中有一个函数名为lowbit函数 i&(i-1),，将最低位的1变成0；，比如 110变成100，由6变成4，4是小于6的最大的2的幂
  显然： 思路3>2>1
  再看看，Integer类的方法，lowesrOneBit()和highestOneBit() 分别是获得最小和最大的2个幂次的分量权重。
  比如6的二进制是110，分解为4+2+0，lowesrOneBit(6)=2，highestOneBit(6)=4；

代码

lowbit函数

public class Solution {
    public int NumberOf1(int n) {
        int cnt=0;
        while(n!=0){
            cnt++;
            n=n&(n-1); //n=n-Integer.lowestOneBit(n);  
        }
        return cnt;
    }
}