Remove all white spaces from a string
May 28, 2018
Traverse and print a linked list in forward and backward order
June 11, 2018

Find numbers with more than k-bits in their binary representations

Given an array of unsigned integers, print all the numbers that have more than k bits set 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);
}

Leave a Reply

Your email address will not be published. Required fields are marked *