Write an algorithm to find F(n) the number of bits set to 1, in all numbers from 1 to n for any given value of n.
Complexity should be O(log n)
For example:
1: 001
2: 010
3: 011
4: 100
5: 101
6: 110
So
F(1) = 1,
F(2) = F(1) + 1 = 2,
F(3) = F(2) + 2 = 4,
F(4) = F(3) + 1 = 5,
etc.
I can only design an O(n) algorithm.
The way to solve these sorts of problems is to write out the first few values, and look for a pattern
Number binary # bits set F(n) 1 0001 1 1 2 0010 1 2 3 0011 2 4 4 0100 1 5 5 0101 2 7 6 0110 2 9 7 0111 3 12 8 1000 1 13 9 1001 2 15 10 1010 2 17 11 1011 3 20 12 1100 2 22 13 1101 3 25 14 1110 3 28 15 1111 4 32
It takes a bit of staring at, but with some thought you notice that the binary-representations of the first 8 and the last 8 numbers are exactly the same, except the first 8 have a 0 in the MSB (most significant bit), while the last 8 have a 1. Thus, for example to calculate F(12), we can just take F(7) and add to it the number of set bits in 8, 9, 10, 11 and 12. But that's the same as the number of set-bits in 0, 1, 2, 3, and 4 (ie. F(4)), plus one more for each number!
# binary 0 0 000 1 0 001 2 0 010 3 0 011 4 0 100 5 0 101 6 0 110 7 0 111 8 1 000 <--Notice that rightmost-bits repeat themselves 9 1 001 except now we have an extra '1' in every number! 10 1 010 11 1 011 12 1 100
Thus, for 8 <= n <= 15, F(n) = F(7) + F(n-8) + (n-7). Similarly, we could note that for 4 <= n <= 7, F(n) = F(3) + F(n-4) + (n-3); and for 2 <= n <= 3, F(n) = F(1) + F(n-2) + (n-1). In general, if we set a = 2^(floor(log(n))), then F(n) = F(a-1) + F(n-a) + (n-a+1)
This doesn't quite give us an O(log n) algorithm; however, doing so is easy. If a = 2^x, then note in the table above that for a-1, the first bit is set exactly a/2 times, the second bit is set exactly a/2 times, the third bit... all the way to the x'th bit. Thus, F(a-1) = x*a/2 = x*2^(x-1). In the above equation, this gives us
F(n) = x*2x-1 + F(n-2x) + (n-2x+1)
Where x = floor(log(n)). Each iteration of calculating F will essentially remove the MSB; thus, this is an O(log(n)) algorithm.
consider the below:
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
If you want to find total number of set bits from 1 to say 14 (1110) Few Observations:
0th bit (LSB) 1 bit appears once every two bit (see vertically) so number of set bits = n/2 +(1 if n's 0th bit is 1 else 0)1st bit position = (n/4 *2) + 1 (since 1st bit is a set, else 0)2nd bit: 4 consecutive 1s appear every 8 bits ( this one is a bit tricky)
number of set bits in 2nd position = (n/8*4 )+ 1( since 2nd bit is set, else 0) + ((n%8)%(8/2))
The last term is to include the number of 1s that were outside first (n/8) group of bits (14/8 =1 considers only 1 group ie. 4 set bits in 8 bits. we need to include 1s found in last 14-8 = 6 bits)3rd bit: 8 consecutive 1s appear every 16 bits (similar to above)
number of set bits in 3rd position = (n/16*8)+1(since 3rd bit is set, else 0)+ ((n%16)%(16/2))so we do O(1) calculation for each bit of a number n.
a number contains log2(n) bits. so when we iterate the above for all positions of n and add all the set bits at each step, we get the answer in O(logn) steps
If n= 2^k-1, then F(n)=k*(n+1)/2
For a general n, let m be the largest number such that m = 2^k-1 and m<=n. F(n) = F(m) + F(n-m-1) + (n-m).
Corner condition: F(0)=0 and F(-1)=0.
A quick search for the values of the sequence F lead to this integer sequence http://oeis.org/A000788
There I spotted a formula: a(0) = 0, a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n+1 (a is the same as F since I just copy the formula from oeis)
which could be used to compute a(n) in log(n).
Here's my sample C++ code:
memset(cache, -1, sizeof(cache))
cache[0] = 0
int f(int n)
if cache[n] != -1 return cache[n];
cache[n] = n % 2 ? (2 * f(n / 2) + n / 2 + 1) : (f(n / 2) + f(n / 2 - 1) + n / 2)
This question can be solved using DP with Bitmasking.
The basic intuition behind bottom-up approach is that we are going to directly access number of set bits in the number having value current_number/2 and we are also going to check whether last bit is set in this current_number or not by just doing and operation with 1.
current_number/2 or current_number>>1 basically removes the last bit of this current_number so to include that bit in our count we have to manually check the last bit of this number using & operation.
This would be expression for computing number of set bits in a number i dp[i]=dp[i>>1]+(i&1)
If you still get stuck while solving this question then you can refer to the following video for a better explanation:-
Video Link: https://youtu.be/fCvfud4p6No
Here is my solution to this. Time complexity : O (Log n)
public int countSetBits(int n){
int count=0;
while(n>0){
int i= (int)(Math.log10(n)/Math.log10(2));
count+= Math.pow(2, i-1)*i;
count+= n-Math.pow(2, i)+1;
n-= Math.pow(2, i);
}
return count;
}
Let k be the number of bits needed for n.
for 0,...,2^(k-1)-1 each bit is up exactly for half of the numbers, so we have (k-1)*2^(k-1)/2 = (k-1)*2^(k-2) bits up so far. We only need to check what's up with the numbers that are bigger then 2^(k-1)-1
We also have for those n-2^(k-1)-1 bits "up" for the MSB.
So we can derive to the recursive function:
f(n) = (k-1)*2^(k-2) + n-(2^(k-1)-1) + f(n-(2^(k-1)))
^ ^ ^
first MSBs recursive call for
2^(k-1)-1 n-2^(k-1) highest numbers
numbers
Where base is f(0) = 0 and f(2^k) = k*2^(k-1) + 1 [as we seen before, we know exactly how much bits are up for 2^(k-1)-1, and we just need to add 1 - for the MSB of 2^k]
Since the value sent to f is reduced by by at least half at every iteration, we get total of O(logn)
short and sweet!
public static int countbits(int num){
int count=0, n;
while(num > 0){
n=0;
while(num >= 1<<(n+1))
n++;
num -= 1<<n;
count += (num + 1 + (1<<(n-1))*n);
}
return count;
}//countbis
Here is the java function
private static int[] findx(int i) {
//find the biggest power of two number that is smaller than i
int c = 0;
int pow2 = 1;
while((pow2<< 1) <= i) {
c++;
pow2 = pow2 << 1;
}
return new int[] {c, pow2};
}
public static int TotalBits2(int number) {
if(number == 0) {
return 0;
}
int[] xAndPow = findx(number);
int x = xAndPow[0];
return x*(xAndPow[1] >> 1) + TotalBits2(number - xAndPow[1]) + number - xAndPow[1] + 1;
}
this is coded in java...
logic: say number is 34, binary equal-ant is 10010, which can be written as 10000 + 10.
10000 has 4 zeros, so count of all 1's before this number is 2^4(reason below). so count is 2^4 + 2^1 + 1(number it self). so answer is 35.
*for binary number 10000. total combinations of filling 4 places is 2*2*2*2x2(one or zero). So total combinations of ones is 2*2*2*2.
public static int getOnesCount(int number) {
String binary = Integer.toBinaryString(number);
return getOnesCount(binary);
}
private static int getOnesCount(String binary) {
int i = binary.length();
if (i>0 && binary.charAt(0) == '1') {
return gePowerof2(i) + getOnesCount(binary.substring(1));
}else if(i==0)
return 1;
else
return getOnesCount(binary.substring(1));
}
//can be replaced with any default power function
private static int gePowerof2(int i){
int count = 1;
while(i>1){
count*=2;
i--;
}
return count;
}
By the way, this question can also be done by the method of lookup table. Precompute the number of set bits from 0-255 and store it. Post that, we can calculate the number of set bits in any number by breaking a given number into two parts of 8 bits each. For each part, we can lookup in the count array formed in the first step. For example, if there is a 16 bit number like,
x = 1100110001011100, here, the number of set bits = number of set bits in the first byte + number of set bits in the second byte. Therefore, for obtaining, first byte,
y = (x & 0xff)
z = (x >> 8) & (0xff)
total set bits = count[y] + count[z]
This method will run in O(n) as well.
Not sure if its late to reply, but here are my findings.
Tried solving the problem with following approach, for number N every bitno ( from LSB to MSB, say LSB starts with bitno 1 and incrementing with next bit value) number of bits set can be calculated as , (N/(2 topower bitno) * (2 topower bitno-1) + { (N%(2 topower bitno)) - [(2 topower bitno-1) - 1] }
Have written recursive function for it C/C++ please check. I am not sure but I think its complexity is log(N). Pass function 2 parameters, the number (no) for which we want bits to be calculated and second start count from LSB , value 1.
int recursiveBitsCal(int no, int bitno){
int res = int(no/pow(2,bitno))*int(pow(2,bitno-1));
int rem1 = int(pow(2,bitno-1)) -1;
int rem = no % int(pow(2,bitno));
if (rem1 < rem) res += rem -rem1;
if ( res <= 0 )
return 0;
else
return res + recursiveBitsCal(no, bitno+1);
}
for i in range(int(input())):
n=int(input())
c=0
m=13
if n==0:
print(c)
while n%8!=0 or n!=0:
t=bin(n)[2:]
c+=t.count('1')
n=n-1
if n!=0:
j=n//8
if j==1:
c+=m
else:
c+=m+((j-1)*7)
print(c)
int countSetBits(int n)
{
n++;
int powerOf2 = 2;
int setBitsCount = n/2;
while (powerOf2 <= n)
{
int numbersOfPairsOfZerosAndOnes = n/powerOf2;
setBitsCount += (numbersOfPairsOfZerosAndOnes/2) * powerOf2;
setBitsCount += (numbersOfPairsOfZerosAndOnes&1) ? (n%powerOf2) : 0;
powerOf2 <<= 1;
}
return setBitsCount;
}
Please check my article on geeksforgeeks.org for detailed explanation. Below is the link of the article https://www.geeksforgeeks.org/count-total-set-bits-in-all-numbers-from-1-to-n-set-2/
I know this post came in late to the party, please find logn solution below:
static int countSetBitWithinRange(int n)
{
int x = n + 1, index = 0, count = 0;
int numberOfOnesInAGroup = (int)Math.pow(2, index);
while(x >= numberOfOnesInAGroup)
{
int countOfZeroOnePairs = (x / numberOfOnesInAGroup);
int numberOfPairsOfZerosAndOnes = countOfZeroOnePairs / 2;
int numberOfSetBits = numberOfPairsOfZerosAndOnes * numberOfOnesInAGroup;
//If countOfZeroOnePairs is even then the pairs are complete else there will be ones that do not have a corresponding zeros pair
int remainder = (countOfZeroOnePairs % 2 == 1) ? (x % numberOfOnesInAGroup) : 0;
count = count + numberOfSetBits + remainder;
numberOfOnesInAGroup = 1 << ++index;
}
return count;
}
x = int(input("Any number:\n"))
y = (bin(x))
print(y)
v = len(y) -2
print(v)
The O(Log(N)) solution is based on the repetition in python is as follows. its based on the simple contribution technique.
def solve(A):
check_array = 1
output = 1
final_sum = 0
offset = 0
while(A>0):
check_array <<=1
if check_array > A:
check_array>>=1
A -=check_array
output = output + check_array * offset
final_sum += output
check_array = 1
output =1
offset +=1
add = output+ check_array//2 -1
output += add
return final_sum
solve(8) = 13
