Bitwise version of finding RGB in java

Question

I have the following method that gets a rgb value and classifies it using a smaller palette:

private static int roundToNearestColor( int rgb, int nrColors )
    {
        int red = ( rgb >> 16 ) & 0xFF;
        int green = ( rgb >> 8 ) & 0xFF;
        int blue = ( rgb & 0xFF );
        red = red - ( red % nrColors );
        green = green - ( green % nrColors );
        blue = blue - ( blue % nrColors );
        return 0xFF000000 | ( red << 16 ) | ( green << 8 ) | ( blue );
    }

The code that annoys me is

red = red - ( red % nrColors );
green = green - ( green % nrColors );
blue = blue - ( blue % nrColors );

I am sure there is an alternate bitwise version of it that will perform faster, but as my bitwise arithmetic is a bit rusty, I have trouble finding such an expression. Any help or comments would be appreciated.

Related: http://stackoverflow.com/questions/2661697/most-optimized-way-to-calculate-modulus-in-c — payne, Jan 24 '11 at 15:10
Provided that `nrColors` is a power of 2, you can simply mask out the lower bits of `red`. — biziclop, Jan 24 '11 at 15:10
Ye, but how do I find how many bits to mask. I need to find which power of 2 is nrOfColors. Wouldn't that slow the algorithm? — Nikola Yovchev, Jan 24 '11 at 15:19
To be perfectly honest... the algorithm seems to work as intended (unless you've found errors I don't see) and it is readable. Why change? Any efficiency improvement is going to be quite minimal. I wouldn't bother optimizing this. — robert_x44, Jan 24 '11 at 15:40

finnw · Accepted Answer · 2011-01-30T12:57:33.877

If nrColors is always a power of 2:

private static int roundToNearestColor( int rgb, int nrColors )
{
    if (Integer.bitCount(nrColors) != 1) {
        throw new IllegalArgumentException("nrColors must be a power of two");
    }
    int mask = 0xFF & (-1 << Integer.numberOfTrailingZeros(nrColors));
    int red = ( rgb >> 16 ) & mask;
    int green = ( rgb >> 8 ) & mask;
    int blue = ( rgb & mask );
    return 0xFF000000 | ( red << 16 ) | ( green << 8 ) | ( blue );
}

Bitwise version of finding RGB in java

1 Answers1

Linked