取一个数字二进制中1的个数

解

1. 二进制中1的个数

    
   int countBits(int n) {
       int count=0 ;
       while (n>0)  {
           count++ ;
           n &= (n - 1) ;
       }
       return count ;
   }
    复杂度: < log2n

2. 方案二

    
   /**
    * Returns the number of one-bits in the two's complement binary
    * representation of the specified {@code int} value.  This function is
    * sometimes referred to as the <i>population count</i>.
    *
    * @param i the value whose bits are to be counted
    * @return the number of one-bits in the two's complement binary
    *     representation of the specified {@code int} value.
    * @since 1.5
    */
   public static int bitCount(int i) {
       // HD, Figure 5-2
       i = i - ((i >>> 1) & 0x55555555);
       i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
       i = (i + (i >>> 4)) & 0x0f0f0f0f;
       i = i + (i >>> 8);
       i = i + (i >>> 16);
       return i & 0x3f;
   }
    复杂度: 1

3. 方案三

    
   public static int countBit1(int n) {
       int count=0 ;
       int temp=1;
       while (temp<=n)  {
           if((temp&n)>0){
               count++ ;
           }
           temp<<=1;
       }
       return count ;
   }

扩展

1. 给定一个数字n计算从1到n每一个数字的二进制中包含1的个数

        
public static int[] countBits(int num) {
        int[] ret = new int[num + 1];

        for (int i = 0; i <= num; i++) {
            int div = i / 2;
            int mod = i % 2;

            if (mod == 1) {
                ret[i] = ret[div] + 1;
            } else {
                ret[i] = ret[div];
            }
        }
        return ret;
    }