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

Question

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?

Inez

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. – Fringe

If you're only trying to avoid using >, go the other way around using ==. y = (x == 0 ? 0 : 1) – Sauveur

Are you working on a signed or unsigned variable? – Sauveur

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. – Fringe

I want to avoid using any realtional operator. – Inez

That is some micro-optimization (even a nano-optimization) which you really should leave to your compiler. – Carrycarryall

This y = (x > 1)? 0:1; and the question's title are somehow not in line ... – Millicentmillie

What does !!(x) mean in C (esp. the Linux kernel)?, What does !! (double exclamation point) mean?, What is the !! (not not) operator in JavaScript? – Sakai

The title says >= 1, but the code in the question says > 1. Which is it? – Radnorshire

(x >= 1)? 0:1; evaluates to 0 for all i >= 1. The title say the opposite. – Millicentmillie

I don’t know the first thing about C, but doesn’t the ‘old-fashioned’ way of doing this by doing y = (int) (bool) x avoid relational operators? Or can you not do that at all in C? – Newspaper

@JanusBahsJacquet: This would return 1 for negative values as well. – Millicentmillie

@Millicentmillie Ah yes, of course it will. Brain fart! – Newspaper

This is a silly question. You've been given two perfectly good SIMD suggestions (vectorizing min(x, 1) or x > 0) which you've dismissed with no underlying reason, instead accepting an answer which answers the letter but not the spirit of your request. – Stroy

To be clear, negative number should become 0 or 1 or don't care? Is x signed or unsigned? – Hook

Answer 1

#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.

Dorothi

This invokes UB for INT_MIN. – Millicentmillie

@Millicentmillie yes, that's true, but for most practical situations, reaching the limits of integer representations normally brings up other issues. – Dorothi

Answer 2

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

Millicentmillie

!!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 – Fringe

@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, – Millicentmillie

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. – Fringe

This is obviously way more complicated than >= which all mainstream SIMD ISAs do support. (x86 only for signed types directly; unsigned compare takes a range shift until AVX-512). But yeah, signed is very complicated to do "manually", unlike hardware compares that work like OF != SF (felixcloutier.com/x86/setcc). If not for the possibility of signed overflow (e.g. from INT_MIN), a logical right shift on i - 1. e.g. (i - 1U) >> 31 (or CHAR_BIT * sizeof(i)-1) would work to get the sign bit as a 0 or 1. – Oshinski

@MatteoItalia : the whole point of !!x for me is to simultaneously identifying inputs of exactly zero or one (for special processing), e.g. if (_ == !!_) { … } cuz it's either that, or if (_ == 1 || !_) { } | if (_ == _*_) { }. if (0 <= _ && _ <= 1) isn't the same at all, in case inputs are decimals. the if (_ == !!_) ensures only exactly integer of zero and one yields true. – Transmarine

Answer 3

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
}

Kapoor

This invokes UB for INT_MAX. – Millicentmillie

Actually for INT_MIN. But even x = -x is UB for that, generally we assume that integers represent something and are in range. – Kapoor

Sure INT_MIN...- sry. – Millicentmillie

Answer 4

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);

Pollard

Instead of sub-from-zero, _mm_srli_epi32(v, 31) is also good, often fewer instructions. But if you want to do something like count the true cases, matches = _mm_sub_epi32( matches, cmp_result) subtracts 0 or minus-1, i.e. increments according to the compare result. Actually creating a 1 in each SIMD element wastes instructions in most cases. – Oshinski

Also, compilers know how to auto-vectorize, so it's not necessary to use intrinsics, and the premise of the question is false (that == or <= are a problem). branching on a compare could be a problem if it's not easy for the compiler to if-convert into branchless, but branchless scalar code using a compare result is usually 100% fine. e.g. Why is processing an unsorted array the same speed as processing a sorted array with modern x86-64 clang? shows clang vectorizing the famous if (data[c] >= 128) sum += data[c]; – Oshinski

So other than silly computer tricks, the real answer to the question is this and that compilers can auto-vectorize == and <= / >. Any of the other answers, except compares in disguise like !!x, will typically compile to slower code. – Oshinski

Answer 5

int any_number_to_one = 0 || any_expression

Depends a bit on the compiler, but hey ;-)

Lapointe

What do you use for any_expression to get a non-zero for x>=1 but a zero for x<1? The OP (misguidedly) wants to avoid >=, so 0 || (x>=1) wouldn't work. And 0 || (x-1) doesn't work at all, it's non-zero for negative, and has signed-integer overflow for INT_MIN. Oh, maybe you were thinking for unsigned x, so x >= 1 is equivalent to x != 0, booleanizing like !!x or your 0 || x? – Oshinski

Answer 6

I found a very strange combo that only uses one arithmetic operator plus double-logical negate:

(this is zero-to-power-of-x, not bitwise xor) :

!! (0 ^ x)

---

!! (0 ** x)

  -3.00 1
  -2.75 1
  -2.50 1
  -2.25 1
  -2.00 1

  -1.75 1
  -1.50 1
  -1.25 1
  -1.00 1
  -0.75 1

  -0.50 1
  -0.25 1
  +0.00 1

  +0.25 0
  +0.50 0

  +0.75 0
  +1.00 0
  +1.25 0
  +1.50 0
  +1.75 0

  +2.00 0
  +2.25 0
  +2.50 0
  +2.75 0
  +3.00 0

It works because 0^0 := 1, while 0^negative yields +inf, so the double-logical negation would convert that down to a 1.

Transmarine

Answer 7

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;

Luca

I want to avoid any relational operator. – Inez

Sorry, my bad, didn't see that stipulation. Perhaps the double not operation given by @alk? – Luca

Answer 8

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.

Doge

In C, ^ is bitwise xor, which doesn't work on doubles. Even if this did work, division and exponential would be slower than just doing scalar integer compares. This answer is totally on the wrong track for performance optimization, even if you replaced e^(stuff) with exp(stuff) library function calls. – Oshinski

@PeterCordes I agree. But the question didn't mention anything about performance. – Gibeonite

The wrote because I want to use SIMD instructions, - Performance is the reason SIMD exists. en.wikipedia.org/wiki/Single_instruction,_multiple_data . If you didn't / don't know what SIMD is and didn't look it up, then you wouldn't have know when you wrote this. But it is in fact true that wanting to vectorize with SIMD (or making your code auto-vectorization friendly) is about performance. – Oshinski