top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Count no of bit ON in a integer value.

+4 votes
449 views

Complexity should be less than O(n);

posted Oct 15, 2013 by Anuj Yadav

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

int noOfBits = 0;

while (number)
{
noOfBits++;
number &= number - 1;
}

answer Oct 15, 2013 by Ganesh Kumar
Complexity should be less than O(n);
From careercup -
uint bit_count(uint value)
{
    printf("0x%08X has ", value, value);
    value = (value & 0x55555555) + ((value & 0xaaaaaaaa) >> 1);
    value = (value & 0x33333333) + ((value & 0xcccccccc) >> 2);
    value = (value & 0x0F0F0F0F) + ((value & 0xF0F0F0F0) >> 4);
    value = (value & 0x00FF00FF) + ((value & 0xFF00FF00) >> 8);
    value = (value & 0x0000FFFF) + ((value & 0xFFFF0000) >> 16);
    printf("%d bits set.\n", value);
    return value;
}
...