#include <strings.h>

typedef uint64_t UINT;
const UINT one = 1;
#define SetBit(var, bit) (var |= (one << bit))

int firstMissingPositive(int* nums, int numsSize){
  
  const int uint_bytes = sizeof(UINT);
  const int uint_bits = uint_bytes*8;
  const int buffer_size = 1 + 500000/uint_bits;

  UINT bitmask[buffer_size];
  memset(bitmask,0,buffer_size*uint_bytes);
  
  int numval = 0;
  for (int i = 0; i<numsSize; i++)
  {
      numval = nums[i];
      if (numval>=1 && numval<=numsSize) {
          --numval;
          SetBit(bitmask[numval/uint_bits], (numval % uint_bits));
      }
  }
    
  UINT mask_inv = 0;
  for (int i = 0; i<1+numsSize/uint_bits; i++)
  {
      mask_inv = ~bitmask[i];
      if (mask_inv==0) continue;
      return i*uint_bits+(ffsll(mask_inv)-1)+1;
  }

  return 0;
}