Numbser of bits in 1 to n in log(n)

#1

can someone pls explain log(n) approach by taking an example…like 10001001 …
goal is to find number of bits that are set from integers 1 to n in log(n) complexity

#2

@shameek.agarwal
hello shameek,
a) In c++ we have __builtin_popcount(x) this will give number of set bit in log(n)
b) or u can write ur own.
while(number > 0){
count+=(number%2);
number=number/2;
}
here basically i m checking last bit (if it is one then 1 will be added to count otherwise 0 ) and then number/2 will shift all bits to right by one position.

#3

this is for one number
i am saying for all numbers from 1 to n in log(n)
e.g.
6 has ans 9
because 001 010 011 100 101 110 total 9 set bits…

int get(int a)
{
	
	if(a==0)	return 0;
	
	int bits = (int)log2(a) + 1;
	int msb = ( 1 <<  (bits-1) );
	if(msb*2==a+1)
		return bits*msb;

	a = a-msb;
	return (a+1) + get(a) + ((bits-1)*(msb/2));
	
}

this approach is working for me…correct output on gfg…i think its log(n)

#4

@shameek.agarwal
oops my mistakes,
refer this article to know all approaches related to this problem with explanation-> https://www.geeksforgeeks.org/count-total-set-bits-in-all-numbers-from-1-to-n/

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.