Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fast tricks to determine array elements are non-negative in C?

I am writing a function

int are_non_negatives(int* start, int n) {
  ...
}

This function returns 1 if all the next n integers in the array start are non-negative. It returns 0 otherwise.

My question is if there exist tricks that do this as fast as possible (other than looping and checking every single position)?

Dirty/non-portable tricks are fine. I want to know about those as well. Thanks!

like image 309
apen Avatar asked Feb 10 '21 22:02

apen


1 Answers

One slightly "dirty/non-portable" trick you could leverage for the worst case where all elements need to be checked: In 2's complement int representation, the highest bit is set if and only if the value is negative. So, you could bitwise OR them all and check the highest bit. This could be done using vector instructions to do batches of them at a time, e.g. 8 elements at a time supposing 32-bit int and 256-bit AVX instructions.

like image 52
Pascal Getreuer Avatar answered Oct 26 '22 01:10

Pascal Getreuer