Home > database >  Unsigned modulo in Java
Unsigned modulo in Java

Time:10-20

I'm porting some c code which is doing a modulo on an uint32_t. An uint32_t fits in a Java int bit-wise, but I cannot figure out how to perform a modulo operation on it without converting to a long. This is the code I have right now:

int i = 0xffffffff;
long asUnsigned = Integer.toUnsignedLong(i);
int mod = (int) (asUnsigned % 42L);

Can I perform this modulo calculation without converting to long?

CodePudding user response:

Use Integer.remainderUnsigned(int dividend, int divisor) (javadoc):

Returns the unsigned remainder from dividing the first argument by the second where each argument and the result is interpreted as an unsigned value.

CodePudding user response:

@that other guy's answer is preferred for Java 8 . I'll leave this here in case it's useful for anyone using older versions of Java.


Converting to a long is almost certainly the best way to do this.

Otherwise, you will need to branch; to get the correct result for a negative int value, you will need to adjust for the fact that the unsigned number that the int represents is offset by 232, and this offset generally won't have a remainder of 0 when you divide by the modulus. If the modulus is a constant (42 in your example) then you can hardcode the offset:

static int unsignedMod42(int x) {
    if(x >= 0) {
        return x % 42;
    } else {
        // 2**32 = 4 (mod 42)
        return ((x % 42)   42   4) % 42;
    }
}

If the modulus is a variable then you have to compute the correct offset at runtime:

static int unsignedMod(int x, int y) {
    if(y <= 0 || y * y <= 0) {
        throw new IllegalArgumentException("y = "   y);
    } else if(x >= 0) {
        return x % y;
    } else {
        // compute 2**32 mod y, by repeated squaring
        int offset = 2;
        for(int i = 0; i < 5;   i) { offset = (offset * offset) % y; }
        return ((x % y)   y   offset) % y;
    }
}

Note that because the offset here is being computed by repeated squaring, we can't allow a modulus for which the multiplication might overflow. There is presumably a better way to compute the correct offset - by repeated multiplication would allow a modulus up to Integer.MAX_VALUE / 2, for example.

  • Related