Negative integer division

Newbie & Debugging Questions
#1

Here’s a puzzler for you.

I’m designing continuous terrain exploration by dynamically loading/unloading 100x100 blocks of tiles.

Given the following coordinates (same for x or y-axis):

...|-300 ... -201|-200 ... -101|-100 ... -1|0 ... 99|100 ... 199|200 ... 299|...

Can you come up with a simple function that given an int, returns the anchor point? The anchor point is the left-hand number in the range and is a multiple of 100. For example for any value between -200 … -101 return -200. For 100 … 199 return 100.

The biggest problem for me is that integer division of negative values seems to be different from language to language! (-1 / 100) gives me -1 in python but 0 in Java. ???

Otherwise I’d use f(x) = x / 100 * 100

#2 
return (x - ( x<0 ? 99 : 0 )) / 100 * 100;
#3

Another option would be to limit the play area to +ve coordinates only.
Integer.MAX_VALUE*Integer.MAX_VALUE is a quarter the size but it’s still very, very big!

#4

… or just

return (int)Math.floor(x/100.0);

It might be slower, though, but it’s at least more readable. :wink:

#5 
	public static final int anchor(int in) {
		return (in / 100 + (in >> 31)) * 100;
	}

or

	public static final int anchor(int in) {
		return (in / 100 - (in >>> 31)) * 100;
	}

depending on if you want -100 to be -200 or -100

#6

both these examples are incorrect (partly because they are identical), loom_weaver is very clear about the spec. you’re off by one for all negative multiples of 100. there is a reason i used 99 as opposed to 100 in my solution. both -1 and -100 should result in -100.

#7

f(-250) = -400. Should be -300.

I think this is the best I can do. I was hoping for a non-branching version:

int anchor(int x) {
    if (x < 0) {
        return -((-x + 99) / 100 * 100)
    } else {
        return x / 100 * 100
    }
}
#8

I don’t know how you tested that, but it simply returns -300, as it should.


   public static final int anchor(int x)
   {
      return (x - ( x<0 ? 99 : 0 )) / 100 * 100;
   }

   public static void main(String[] args)
   {
      System.out.println(anchor(-250)); // "-300"
   }
#9

Oops… was testing in Python again. Argh. Oh well my lesson learned is be careful with division involving -ve integers.

In the old C standard it did not define what direction to round to (-ve INFINITY or 0) if dividing with a negative int. In later standards, it rounds towards zero.


#10

As you were hoping for one, here is a non-branching solution:

   public static final int anchor(int x)
   {
      return (x - ((x >>> 31) * 99)) / 100 * 100;
   }
#11

If you want the offset (relative to your anchor), in a non-branching way:

   public static final int offset(int x)
   {
      return (x%100+100)%100;
   }
#12

Dang… taking the high-order bit and multiplying by 99.

Thanks for the formulas guys!

#13

it you really want to get it ‘fast’, you can take out the multiply…


((x >>> 31) * 99) == ((x >> 31) & 99)
#14

Your example is completely incorrect :wink:

@Riven
That last one returns true or false, not a value. What is its purpose?
Hehe looked at it a bit more and realized that you mean to substitute the right-hand side for the left-hand side. Wow that is quite clever and much much faster!