@Nishant :
Don's algo :
first he is counting #of bits of all numbers from 0 to 65536 and
maintaining in an array bitCount.
Converted the input array into of type short. short range is 0 to 65536.
for the given input, he is getting the number of bits set using bitCount[]
.. its like
guys ..i got solution here
http://www.geeksforgeeks.org/program-to-count-number-of-set-bits-in-an-big-array/
plz tell how its complexity is logn.
On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
Counting the set bits in one integer is not the problem which was
asked.
However,
and how this is working
void init()
{
bitCount[0] = 0;
for(int i = 1; i 65536; ++i) bitCount[i] = bitCount[i/2] + (i1);
}
it is working fine..but plz tell the logic behind this
On Thu, May 23, 2013 at 11:12 AM, rahul sharma rahul23111...@gmail.comwrote:
@don...i got it...its complexity is
@pramidathat can be done in 0(n)..lets say int takes 4 bytes
i will make and array of first 256 numbers ...
while finding for inte i will take a char pointer pointing to first byte
and then using array of 256 int i will count in that byte and increent
array and count in it.and so
You can use this logic to find number of bits set :-
int count = 0;
foreach(int x in array){
if(x 0)
count--; //for the sign bit will be counted below.
while(x){
x = x-1;
count++;
}
}
Thanks
Monish
On Sunday, May 12, 2013 1:05:31 AM UTC+5:30, rahul sharma wrote:
I was
@don...i got it...its complexity is logn..how?
On Thu, May 23, 2013 at 11:10 AM, rahul sharma rahul23111...@gmail.comwrote:
@don..you are counting in an integer only...correct if wrng?
On Wed, May 22, 2013 at 7:28 PM, Don dondod...@gmail.com wrote:
My program works with any numbers.
Don
Hi Don,
instead of searching 1 at all places we can use this :
while(n!=0){
count++;
n = n n-1;
}
On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
Counting the set bits in one integer is not the problem which was
asked.
However, I think that something like this is both
@don..you are counting in an integer only...correct if wrng?
On Wed, May 22, 2013 at 7:28 PM, Don dondod...@gmail.com wrote:
My program works with any numbers.
Don
On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
This above program works only if the array contains
@DOn can u explain ur first algo, it would be helpful.
On Wed, May 22, 2013 at 7:28 PM, Don dondod...@gmail.com wrote:
My program works with any numbers.
Don
On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
This above program works only if the array contains consecutive
This above program works only if the array contains consecutive numbers
starting from 1 to n. What to do if the array contains random numbers?
On Fri, May 17, 2013 at 6:55 PM, Don dondod...@gmail.com wrote:
Counting the set bits in one integer is not the problem which was
asked.
However, I
My program works with any numbers.
Don
On May 22, 3:45 am, Pramida Tumma pramida.tu...@gmail.com wrote:
This above program works only if the array contains consecutive numbers
starting from 1 to n. What to do if the array contains random numbers?
On Fri, May 17, 2013 at 6:55 PM, Don
as bitwise operators are fast can count by following logic, works oly fr
+ve, just a tweak will make it to work with -ves also ..
#include stdio.h
main() {
unsigned int x=12312,a;
a=x1;
//printf(%u,a);
int count=0;
while(x0) {
a = x1;
//printf(%u \n,a);
if(ax)
count++;
x=a;
}
printf(%d\n,count
Counting the set bits in one integer is not the problem which was
asked.
However, I think that something like this is both faster and more easy
to understand than what you have written:
int bitCount(unsigned int x)
{
int result = 0;
while(x)
{
if (x 1) ++result;
x = 1;
}
I don't think that there is a shortcut, if the array contains
arbitrary data.
You'll want to create an array of bit counts for either 8 or 16 bits.
I would go with 16.
int bitCount[65536];
// Do this once at initialization time
void init()
{
bitCount[0] = 0;
for(int i = 1; i 65536; ++i)
14 matches
Mail list logo
