Java 3ms and 6ms version, easy to understand


  • 0
    M

    6ms:

    public class Solution {
        public int[] countBits(int num) {
            int[] result = new int[num+1];        
            for(int i = 0; i <= num; i++)
            {
                int temp = i;
                temp = temp - ((temp >> 1) & 0x55555555);
                temp = (temp & 0x33333333) + ((temp >> 2) & 0x33333333);
                temp = (((temp + (temp >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
                result[i] = temp;
            }
            return result;
        }
    }
    

    3ms

    public class Solution {
        public int[] countBits(int num) {
            int[] result = new int[num+1];  
            int step = 1, power = 1;
            for(int i = 0; i <= num; i++)
            {
                if(i == 0)
                {
                    result[i] = 0;
                }
                else if(step == 0)
                {
                    result[i] = 1;
                    if(i > 1)
                        power *= 2;
                    step = power;
                }
                else
                {
                    result[i] = 1 + result[i - power];
                }
                step--;
            }
            return result;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.