Leetcode/ number of 1 in the first n digit binary

package com.xcrj;

import java.util.Arrays;

/** *  The finger of the sword  Offer II 003.  front  n  A number in binary  1  The number of  *  Given a nonnegative integer  n , Please calculate  0  To  n  In the binary representation of each number between  1  The number of , And output an array . * <p> *  Examination site ： *  Found that regular （ Dynamic programming ） * r&1 Parity property ：r Is an odd number, and the result is 1,r Is an even number, and the result is 0 * r>>1 Parity property ：r For odd or even numbers, the result is equal , The result is divided by 2 integer  */
public class Solution3 {
    
    //  Both memory and time consuming 
    // % / Operator 
    public int[] countBits(int n) {
    
        int[] result = new int[n + 1];

        // t In charge of calculation ,r Index 
        for (int r = 0; r < n + 1; r++) {
    
            int t = r;
            while (true) {
    
                int remainder = t % 2;
                if (1 == remainder) result[r]++;
                int quotient = t / 2;
                if (1 == quotient) {
    
                    result[r]++;
                }
                if (quotient < 2) {
    
                    break;
                }
                t = quotient;
            }
        }

        return result;
    }

    //  Both memory and time consuming 
    // >>  Operator 
    public int[] countBits2(int n) {
    
        int[] result = new int[n + 1];

        // t In charge of calculation ,r Index 
        for (int r = 0; r < n + 1; r++) {
    
            int t = r;
            while (true) {
    
                int remainder = t % 2;
                if (1 == remainder) result[r]++;
                int quotient = t >> 1;
                if (1 == quotient) {
    
                    result[r]++;
                }
                if (quotient < 2) {
    
                    break;
                }
                t = quotient;
            }
        }

        return result;
    }

    //  Both memory and time consuming 
    // &  Bitwise AND  <<  Move left 
    public int[] countBits3(int n) {
    
        int[] result = new int[n + 1];

        // t In charge of calculation ,r Index 
        for (int r = 0; r < n + 1; r++) {
    
            int t = r;
            for (int i = 0; i < 32; i++) {
    
                if (0 != (t & 1 << i)) {
    
                    result[r]++;
                }
            }
        }
        return result;
    }

    /** *  Dynamic programming + An operation  * dp[2n+1]-1=dp[2n]： Odd numbers must be better than the previous number （ even numbers ） many 1, Binary represents the end of 1 * dp[2n]=dp[n]： An even number must be half smaller than this even number ,1 There are as many as there are .2n It's even ,2n/2=n It's even , Even binary represents the last 1 All places are 0, except 2 It's equivalent to moving right 1 position  */
    public int[] countBits4(int n) {
    
        int[] result = new int[n + 1];
        result[0] = 0;
        for (int r = 1; r < n + 1; r++) {
    
            //  even numbers 
            if (0 == r % 2) {
    
                result[r] = result[r >> 1];
            } else {
    
                /** * r In an odd number of  * result[r] = result[r - 1] + 1; * r-1 Even numbers  * result[r - 1]=result[(r - 1)>>1] * (r - 1)>>1 be equal to r>>1 * result[(r - 1)>>1]=result[r>>1] *  therefore  * result[r] = result[r >>1]+1 */
                result[r] = result[r >> 1] + 1;
            }
        }
        return result;
    }

    /** *  Dynamic programming + An operation  * dp[2n+1]-1=dp[2n]： Odd numbers must be better than the previous number （ even numbers ） many 1, Binary represents the end of 1 * dp[2n]=dp[n]： An even number must be half smaller than this even number ,1 There are as many as there are .2n It's even ,2n/2=n It's even , Even binary represents the last 1 All places are 0, except 2 It's equivalent to moving right 1 position  */
    public int[] countBits5(int n) {
    
        int[] result = new int[n + 1];
        result[0] = 0;
        for (int r = 1; r < n + 1; r++) {
    
            /** *  Unified  result[r >> 1] and result[r - 1] * * r In an odd number of  * result[r] = result[r - 1] + 1; * r-1 Even numbers  * result[r - 1]=result[(r - 1)>>1] * (r - 1)>>1 be equal to r>>1 * result[(r - 1)>>1]=result[r>>1] *  therefore  * result[r] = result[r >>1]+1 */
// if (0 == r % 2) {
    
// result[r] = result[r >> 1];
// } else {
    
// result[r] = result[r >> 1] + 1;
// }

            /** *  Remove parity judgment  *  When r It's even , No +1 *  When r Is odd , want +1 * * r When it's even ,r&1=0 * r It's an odd number ,r&1=1 */
            result[r] = result[r >> 1] + (r & 1);
        }
        return result;
    }

    public static void main(String[] args) {
    
        Solution3 solution3 = new Solution3();
        System.out.println(Arrays.toString(solution3.countBits5(5)));
    }
}