Android Random.nextInt in for loop

I'm iterating over some pixel data from a Bitmap stored in an int[]

private int[] newImage(Random r, int[] px, int w, int h)
{
    int[] pixels = new int[w * h];

    for (int i = 0; i < w * h; i++) {
        pixels[i] = (r.nextInt(100) < 50) ? (px[i] & 0xffffff) : px[i];
    }
    return pixels;
}

The Random.nextInt() method seems to be slowing things down considerably. Without the rand (just the bitwise operation) it takes about 200ms. With the rand it takes about 640ms to return the new int[]. The original int[] isn't very large and this seems painfully slow. Is there something I can do to speed things up? Ideally I'd like to get the new array back in < 50ms