In my program, I have a statement like the following, inside a loop.

y = (x >= 1)? 0:1;

However, I want to avoid using any relational operator, because I want to use SIMD instructions, and am not sure if relational operators work well with SIMD.

I want something like the following.

a = some_operation(x) // a will be either 1 or 0
y = 1 - a

Where some_operation would convert any number equal or greater than 1 to 1, and keep 0 to 0. So, my question is, is there any some_operation that would achieve my purpose?

share|improve this question
5  
Actually, SSE has a several max/min instructions, so if you are sure that x cannot be between 0 and 1 something like x = x>1?1:x; should translate to efficient code using maxpd or something like that. – Matteo Italia Apr 29 '17 at 9:09
3  
I feel like we are talking different languages. It doesn't matter if you avoid language constructs where the > token appears or where there's no explicit if or ?, the point is if it can be translated to branchless SIMD instructions. – Matteo Italia Apr 29 '17 at 9:24
2  
That is some micro-optimization (even a nano-optimization) which you really should leave to your compiler. – Basile Starynkevitch Apr 29 '17 at 9:26
4  
This y = (x > 1)? 0:1; and the question's title are somehow not in line ... – alk Apr 29 '17 at 9:28
3  
(x >= 1)? 0:1; evaluates to 0 for all i >= 1. The title say the opposite. – alk Apr 29 '17 at 10:29
up vote 3 down vote accepted
#define INT_BITS (CHAR_BIT * sizeof(int))

int make_zero_or_one(int x) {
   return 1 - (((x-1) >> (INT_BITS-1)) & 1);
}

Like the other answers, this relies upon the MSB being the sign bit in ints. The function returns 0 for all ints <= 0 and 1 otherwise. The function will fail if x-1 overflows.

This implementation has no branches in compiled code.

share|improve this answer
1  
This invokes UB for INT_MIN. – alk Apr 29 '17 at 12:36
    
@alk yes, that's true, but for most practical situations, reaching the limits of integer representations normally brings up other issues. – adelphus Apr 29 '17 at 12:38

Is there a way to convert an integer to 1 if it is >= 1 without using any relational operator?

For unsigned integers you can simply do:

unsigned int i = 42; // ... or any other value > 0.
unsigned int j = !!i; // j is 1 here.

i = 0;
j = !!i; // j is 0 here.

Update:

For signed integers you can do

int i = ...
int j = !!(i * !((1 << ((CHAR_BITS * sizeof i) - 1)) & i)); 

The above line results in

  • 0 for any i < 1
  • 1 for any i >= 1
share|improve this answer
4  
!!x is just a complicated way to write x?1:0; it doesn't change a thing from the compiler perspective. The signed version also generates horrible code. godbolt.org/g/Kg69U6 – Matteo Italia Apr 29 '17 at 11:29
1  
@MatteoItalia: I never claimed this to be elegant. Still whether !!x or x?1:0 is more or less complicated is a matter of how you look at it, – alk Apr 29 '17 at 12:45
    
Whatever, the point is that it doesn't change the codegen. Again: a conditional remains a conditional even if you hide it under different syntax. – Matteo Italia Apr 29 '17 at 13:03

Assuming you use two's complement you can do this. (The other answer to use !!x may or may not be what you are looking for, depending on the computer's instruction set and why you want to avoid relational operators)

int x = 42; // or any integer

int test = x-1;
if(test & 1 << (CHAR_BIT * sizeof(int) -1))
{
   // integer negative or zero
}
else
{
   // integer positive
}
share|improve this answer
    
This invokes UB for INT_MAX. – alk Apr 29 '17 at 12:43
    
Actually for INT_MIN. But even x = -x is UB for that, generally we assume that integers represent something and are in range. – Malcolm McLean Apr 29 '17 at 13:20
    
Sure INT_MIN...- sry. – alk Apr 29 '17 at 13:24

I'm aware that this answer explicitly contradicts your question, but there are SIMD comparisons on all common SIMD architectures (at least all I know).

For SSE2 and int32 parameters there is pcmpgtd (intrinsic: _mm_cmpgt_epi32), assuming you have 4 integers in __m128i x, you can write

__m128i result = _mm_cmpgt_epi32(x, _mm_setzero_si128())

To get -1 (i.e. 0xFFFFFFFF) for every x>0 (i.e. x>=1) and 0 otherwise. If you need 1 instead of -1 just write

__m128i y =  _mm_sub_epi32(_mm_setzero_si128(), result);
share|improve this answer

I'm not familiar with C or using SIMD instructions, but if x is a positive integer,can't you just do this?

y = (x == 0) ? 1 : 0;
share|improve this answer
1  
I want to avoid any relational operator. – pythonic Apr 29 '17 at 9:25
    
Sorry, my bad, didn't see that stipulation. Perhaps the double not operation given by @alk? – e_i_pi Apr 29 '17 at 9:26

Use this: y= 1/(1+e^(-10000*(x-0.995)))

This will give y = 0 for x <= 0.99 and y=1 for x>= 1

I don't know what SIMD is and there could very well be a better way to do this. But I figured, if you don't want to use a condition you can use a sigmoid function that returns a 0 or a 1 according to your criteria. This function would be your some_operation(x) .Note that this function will only work for numbers with 2 decimals. That is, an input of 0.99 will return 0 but an input of 0.999 will return 1. Make sure you round your number down to the nearest 2-decimal number before doing the calculation.

I will go through step by step of my thought process below if anyone is interested:

If you want to use a function, and not a logical condition it would have to be continuous which by definition would mean that som of the values would not fit the criteria. But if those values were within a very narrow range, and your steps between numbers were bigger than that narrow range it would work.

So you could use a sigmoid function. (input it into wolfram alpha so see each change)

  y =  1/(1+e^(-x))   

And shift it one step to the right so it's centered around 1 instead of zero.

  y = 1/(1+e^(-(x-1)))

Then you can increase the slope of the function by increasing the weight.

  y= 1/(1+e^(-10000*(x-1))) 

Now the slope is really, really steep. But we still get y = 0.5 if we input x=1. So we need to shift the sigmoid a bit to the left.

y= 1/(1+e^(-10000*(x-0.995))) 

Now we will get y= 0 if x <= 0.99 and y=1 if x >= 1. If you want to use a finer resolution you would have to adjust the weight (10000 in this case) and the center point (0.995 in this case). I just checked the calculation in wolfram alpha and iterated what works. You can use a weight as low as 4000 if you are using only 2 decimals.

I'm sure there is a better way to do this, but this is how I would solve it.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.