how can I make branchless number cycle?

user_14243223 0
Viewed 160

I need a branchless number cycle code.

like this:

int i = 0;
i = (i + 1) % 4  //1
i = (i + 1) % 4  //2 
i = (i + 1) % 4  //3 
i = (i + 1) % 4  //0 
i = (i + 1) % 4  //1
...

But it should work in the reverse order of the code above. (3 > 2 > 1 > 0 > 3 > ...)

I first tried "i = (i - 1) % 4". But this worked differently than I wanted. (-1 > -2 > -3 > 0 > -1 > ...) However, if I use the method of adding 4 when i is negative, this code is no longer branchless.

How can I implement the functionality which I want (without additional variables or arrays)?

(This article has been translated by Google Translate.)

c algorithm c++
4 Answers

The error happens because in C89 the remainder of negative numbers was underspecified and from C99, negative % positive will result in a negative number which is unlike in some programming languages such as Python, where (-1) % 4 would indeed result in 3.

But it is easy to circumvent. When you subtract 1, it is the same as adding -1. Since 0 - 1 will get to -1, we would have a negative remainder. To stay positive, instead of adding the negative -1 we can add a positive number that's congruent to -1 (mod m). The smallest positive such number is m - 1 for an m > 1. Therefore we can use:

#define MODULUS 4  // or any other moduli > 1

int i = 0;
i = (i + (MODULUS - 1)) % MODULUS;  //3
i = (i + (MODULUS - 1)) % MODULUS;  //2
i = (i + (MODULUS - 1)) % MODULUS;  //1
i = (i + (MODULUS - 1)) % MODULUS;  //0
i = (i + (MODULUS - 1)) % MODULUS;  //3
user_9189590

You need to change your expression a bit. It should be:

i = ( i + 3 ) % 4;

In general, if you want a number in range [0,N-1] with such cycle then the equation should be:

i = (i + (N - 1)) % N;

You can see it working here(manually several times) and here (in loop):

int main() 
{
    int i = 0;
    i = ( i + 3 ) % 4;  //3
    i = ( i + 3 ) % 4;  //2
    i = ( i + 3 ) % 4;  //1
    i = ( i + 3 ) % 4;  //0
    i = ( i + 3 ) % 4;  //3
    i = ( i + 3 ) % 4;  //2
    i = ( i + 3 ) % 4;  //1
    i = ( i + 3 ) % 4;  //0
    return 0;
}
user_80134710

You can use unsigned arithmetic, then the numbers won't become negative.

unsigned i = 0;
i = (i - 1) % 4  //3
i = (i - 1) % 4  //2 
i = (i - 1) % 4  //1
i = (i - 1) % 4  //0 
i = (i - 1) % 4  //3

Also, maybe more intuitive, you can use bitwise operations to implement a 2-bit counter.

unsigned i = 0;
i = (i - 1) & 3;
i = (i - 1) & 3;
i = (i - 1) & 3;
i = (i - 1) & 3;
i = (i - 1) & 3;

On machine code level, this is identical to the code above.

user_5098680

There are two cases:

Case 1: The modulo is a power of 2

In this case, you can simply use unsigned arithmetic with a bit mask:

unsigned i = ...;

i = (i - 1) & (modulo - 1);

When i = 0, subtracting 1 will yield a value with all bits set in unsigned arithmetic, and the mask operation & will yield the value modulo - 1.

Case 2: The modulo is not a power of 2

In this case, no fancy bit tricks work. You can only avoid going negative:

i = (i + modulo - 1) % modulo;
user_24451840
Related