1-bits in array


  • 0
    W

    How many 1-bits are there in a 2^20 sized array with numbers in sequence from 0 to 2^20 - 1?

    '''
    #this is to get how many one bit in a string
    #use dp method
    public class solution{
    public int solve(){
    int[]dp = new int[20];
    dp[0] = 1;
    for(int i = 1; i < 20; i++){
    dp[i] = (dp[i - 1] << 1) + (1 <<(i));
    }
    return dp[19];
    }
    }
    '''


  • 2
    P

    @wanghanwen

    In case of 2-bit numbers from 0 to 3, totally we have 8 bits out of which 4 bits are set(having 1).
    Similarly for 3-bit numbers from 0 to 7 has total of 24 bits out of which 12 are set.
    Generalizing this gives
    for n bits

    total number of set bits will be (pow(2,n) * n) / 2

    For this case: (pow(2,20) * 20)/ 2 = pow(2,20) * 10

    Correct me if I am wrong


  • 1
    S

    said in 1-bits in array:

    dp[i] = (dp[i - 1] << 1) + (1 <<(i));

    should be

    dp[i] = (dp[i - 1] << 1) + (1 <<(i - 1));

  • 0
    A

    @hamster i think in the end you need to return dp[19]+1 for the last pow of 2 which will be counted for the next power.
    dp[x] is giving number for 1's from 1 to pow(2,x)-1


  • 2

    @PraveenEM no, you are totally right.

    We have the complete range of numbers with 20 bits. Half of the time a bit will be 0 and the other half 1. That gives us an average of 10 bits with 1 over 2^20 numbers. Number of ones = 10 * 2^20.

    The question would be slightly more interesting asking about the number of zeros. For that you will need to know the size of your numbers. Let's assume you use int32. That gives us 12 bits of unused zeroes per number. Number of zeros = 12 * 2^20 + 10 * 2^20.


  • 1
    R

    This is a O(n) brute-force solution in Python:

    def count_1_bits(k):
    	N = 1 << k
    	ans = 0
    	for n in range(N):
    		while n:
    			ans += n & 1
    			n >>= 1
    	return ans
    

    And this is a smarter O(1) implementation that uses the fact that 50% of the bits are 1,
    so we have just to calculate the total number of bits in the sequence and divide by 2:

    def count_1_bits_fast(k):
    	return 2 ** (k - 1) * k
    

    I used the first implementation to prove that the second works ;-)


  • 0
    R

    @PraveenEM You are right, my brute-force implementation proves it.


Log in to reply
 

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