CODEWITHSUNDEEP
javabit-manipulationmodulounsigned-integersigned-integer
Alexander Torstling
Alexander Torstling

Reputation: 18898

Unsigned modulo in Java

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?

Upvotes: 0

Views: 806

Answers (2)

kaya3
kaya3

Reputation: 51037

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

Upvotes: 1

that other guy
that other guy

Reputation: 123410

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.

Upvotes: 6

Related Questions