Find numbers with more than k Set-Bits in their binary representations

Given an array of unsigned integers, print all the numbers that have more than k Set-Bits in their binary representation.

For example, if k = 2, and input array is:

int arr[] = {2, 1, 15, 9, 7, 14, 32, 127};

Then the output should be:

15 7 14 127

Because all of these numbers has more than 2 bits set in their binary representations:

Solution:

The brute-force solution is to use mask and check whether a bit in a number is set of not for each bit in the number. In this case, we have to check for sizeof(int) bits.

A better solution is to use the logic used in this post, where we saw how to reset the last set-bit of a number in constant time:

This is a constant-time improvement, where the loop is executed only for set-bits.

// COUNT THE NUMBER OF SET BITS IN num
int bitSetCount(int num)
{
  int cnt = 0;
  while(num >0)
  {
    num = num & (num-1);
    cnt++;
  }
  return cnt;
}
// PRINT NUMBERS WITH MORE THAN k BITS SET IN THEIR BINARY REPRESENTATION
void printNumbersForSetBits(int *arr, int n, int k)
{
  // FOR EACH NUMBER
  for(int i=0; i k)
      cout<<arr[i]<<" ";
  }
}
int main()
{
  int arr[] = {2, 1, 15, 9, 7, 14, 32, 127};
  printNumbersForSetBits(arr, 8, 2);
}